Пусть G – конечный н-граф.

Маршрутом в G называется последовательность ребер, в которой каждые два соседних ребра имеют общую вершину:

Число ребер в маршруте называется его длиной.

Маршрут М называется маршрутом общего вида цепью простой цепью – если его вершины не повторяются,

Маршрут, в котором совпадают начальная и конечная вершины, т.е. , называется циклическим (замкнутым ).

Циклический маршрут М называется маршрутом общего вида , если вершины и ребра повторяются, циклом – если его ребра не повторяются, простым циклом – если его вершины не повторяются (кроме начала и конца).

Граф, не содержащий циклов, называется ациклическим.

Вершины и называются связными , если существует маршрут с началом в и концом в .

Утверждение: Отношение связности вершин графа является отношением эквивалентности и определяет разбиение множества вершин графа на непересекающиеся подмножества .

Граф называется связным , если для любых двух различных вершин существует маршрут, соединяющий их.

Очевидно, что все подграфы G (V i ) этого графа связны и называются связными компонентами графа.

Расстоянием между вершинами a и b называется длина минимальной простой цепи, связывающей их. Расстояние обозначается d (a , b ) .

Аксиомы метрики:

1) d (a , b ) = d (b , a );

2) d (a , b ) ≥ 0, d (a , b ) = 0 ↔ a = b ;

3) d (a , b ) ≤ d (a , c ) + d (c , b )

Матрица расстояний, это симметричная квадратная матрица размерности , строки и столбцы которой соответствуют вершинам графа, а на пересечении строк и столбцов записано расстояние между вершинами .

…
…
…
… … … … … …
…

В последнем столбце матрицы указан эксцентриситет для каждой вершины: расстояние от данной вершины до наиболее удаленной вершины.

. (7.1)

Диаметр графа G – максимальное расстояние между вершинами графа. Диаметр находится по формуле:

.

Используя найденные эксцентриситеты вершин, диаметр можно найти по формуле:

. (7.2)

Радиус графа G – минимальное значение эксцентриситета. Радиус находится по формуле:

. (7.3)

Центр графа G – такая вершина, для которой .

Замечание. Центр в графе может быть не единственный.

Диаметральная цепь графа G диаметру, соединяющая наиболее удаленные вершины графа.

Радиальная цепь графа G – простая цепь, длина которой равна радиусу, соединяющая центр и наиболее удаленную от него вершину графа.

Пример 7.1.

Для н-графа, приведенного на рисунке 7.1, записать 1) маршрут общего вида, 2) не простую цепь, 3) простую цепь, 4) циклический маршрут общего вида,5) не простой цикл, 6) простой цикл.

Решение:

1) Маршрут общего вида – это маршрут, в котором начальная и конечная вершина различны, и некоторые ребра повторяются. М 1 = (1, 4 , 5, 1, 4 , 7, 3). Здесь повторяется ребро (1, 4).

2) Не простая цепь – это маршрут, в котором не повторяются ребра, но повторяются вершины. М 2 = (4, 3, 1 , 5, 6, 7 , 4, 1 ). Здесь повторяется вершина 1.

3) Простая цепь – это маршрут, в котором не повторяются вершины. М 3 = (4, 3, 7, 5, 6).

4) Циклический маршрут общего вида – это маршрут, в котором начальная и конечная вершины совпадают, и некоторые ребра повторяются. М 4 = (1, 5 , 1, 5 , 1 ). Здесь повторяется ребро (1, 5).

Рисунок 7.1. Построение маршрутов

в неориентированном графе

5) Непростой цикл – это циклический маршрут, в котором не повторяются ребра, но повторяются вершины. М 5 = (3, 4 , 5, 7, 4 , 1, 3). Здесь повторяется вершина 4.

Заметим, что непростой цикл бывает только в графах, в которых существует конфигурация типа «песочные часы».

6) Простой цикл – это циклический маршрут, в котором не повторяются вершины. М 6 = (5, 4, 3, 2, 1, 5).

Пример 7.2.

Для н-графа, приведенного на рисунке 7.1, построить матрицу расстояний. Определить диаметр и радиус графа. Указать центры графа. Записать диаметральные и радиальные цепи

Решение:

Для построения матрицы расстояний, сопоставим строки и столбцы вершинам. На пересечении строк и столбцов укажем расстояние между соответствующими вершинами.

d(a , b ) 1 2 3 4 5 6 7
1 0 1 1 1 1 2 2 2
2 1 0 1 2 2 3 2 3
3 1 1 0 1 2 2 1 2
4 1 2 1 0 1 2 1 2
5 1 2 2 1 0 1 1 2
6 2 3 2 2 1 0 1 3
7 2 2 1 1 1 1 0 2

На месте (1, 1) стоит 0, так как кратчайший маршрут между вершиной 1 и вершиной 1 – это вырожденный маршрут (без ребер) длины 0.

На месте (1, 2) стоит 1, так как кратчайший маршрут между вершиной 1 и вершиной 2 – это единственное ребро, связывающее эти вершины.

На месте (1, 6) стоит 2, так как кратчайшая простая цепь, между вершиной 1 и вершиной 6 – это цепь из двух ребер (1, 5, 6). Значит, расстояние между этими вершинами равно 2.

В последнем столбце таблицы указано расстояние от данной вершины до наиболее удаленной от нее вершины – эксцентриситет. Их значения находим по формуле (7.1).

Максимум значений последнего столбца – диаметр графа. Откуда d (G ) = 3.

Минимум значений последнего столбца – радиус графа. Откуда r (G ) = 2.

Центрами являются вершины: 1, 3, 4, 5, 7. Их эксцентриситеты равны радиусу графа.

Для построения диаметральных цепей выясним с помощью матрицы расстояний, какие вершины наиболее удалены друг от друга. Так как максимальное расстояние между вершинами – это диаметр графа, значит, найдем вершины, находящиеся на расстоянии, равном диаметру. Это вершины 2 и 6. Следовательно, все диаметральные цепи в графе связывают эти вершины. Таких цепей две:

D 1 = (2, 1, 5, 6) и D 2 = (2, 3, 7, 6).

Для построения радиальных цепей выясним с помощью матрицы расстояний, какие вершины наиболее удалены от центров.

От центра 1 на расстоянии радиуса, равного 2, находятся вершины 6 и 7. Значит можно провести радиальные цепи:

R 1 = (1, 5, 6) и R 2 = (1, 4, 7).

От центра 3 на расстоянии радиуса находятся вершины 5 и 6. Значит можно провести радиальные цепи:

R 3 = (3, 4, 5) и R 4 = (3, 7, 6).

Пусть G(V,X) – псевдограф и пусть вершины v и w (v¹w) данного графа можно соединить маршрутом. Тогда обязательно существует и минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута d(v, w). Положим также d(v, v) =0 для любой вершины vÎV; d(v, w) = ¥, если не существует маршрута, соединяющего v и w.

Определенная таким образом величина d(v,w) для любых вершин v и w графа G(V, X) называется расстоянием между v и w.

Число расстояний в графе с n вершинами равно числу сочетаний C n 2 .

Пусть граф G(V,X) связный. Определим для него следующие понятия:

Диаметр графа : d(G) = maxd(v, w).

Эксцентриситет (максимальное удаление) вершины : r(v) = maxd(v, w);

Радиус графа: r(G) = min r(v);

Центр графа : любая вершина vÎV,такая, что r(v) = r(G).

Диаметр графа, эксцентриситеты вершин, радиус графа и центры графа называются метрическими характеристиками графа.

Пример. Найти метрические характеристики графа, заданного диаграммой:

Найдем все расстояния, учитывая, что d(v, w) = d(w, v).

Число расстояний в данном графе С 5 2 = 5!/3!2! = 10: d(v 1 , v 2) =1, d(v 1 , v 3) = 2, d(v 1 , v 4) = 2, d(v 1 , v 5) = 3, d(v 2 , v 3) = 1, d(v 2 , v 4) = 1, d(v 2 , v 5) = 2, d(v 3 , v 4) = 1, d(v 3 , v 5) = 2, d(v 4 , v 5) = 1.

Диаметр графа d(G) =3.

Эксцентриситеты вершин: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3.

Радиус графа r(G) = 2.

Центры графа v 2 , v 3 , v 4 .

3. Минимальные маршруты в нагруженных графах

Граф G(V, X) называется нагруженным, если на множестве ребер графа задана функция, называемая весовой, которая ставит в соответствие каждому ребру х ÎХ графа некоторое число l(x). Значение l(x) называется длиной дуги.

Величине l(x) можно придать разный смысл: затраты на транспортировку, время проезда, расстояние между пунктами, расход бензина и т.д.

Сумма длин ребер, входящих в маршрут, называется длиной маршрута.

Заметим, что если для всех х Î Х l(x) = 1, то граф можно рассматривать как ненагруженный.

Маршрут в графе G(V, X) из вершины v в вершину w (v¹w), называется минимальным, если он имеет минимальную длину среди всех маршрутов в графе G(V, X) из вершины v в вершину w.

Ограничимся графами, для которых l(x)>0.

При поиске минимального маршрута в нагруженном графе с l(x)>0

воспользуемся таким же утверждением, что и для ненагруженного графа, а именно:

любой минимальный маршрут является простой цепью.

Рассмотрим теперь задачу поиска минимального маршрута в нагруженном графе.

Пусть граф G(V,X) нагруженный, число вершин n ³ 2, необходимо построить минимальный маршрут из v 1 в v n .


Приведем алгоритм.

Шаг 1. Каждой вершине присвоить индекс a(v i): a(v 1) = 0, a(v i) = ¥, i ¹ 1. окрасить вершину v 1 и положить v = v 1 .

Шаг 2. Для каждой неокрашенной вершины v j изменить индекс по правилу:

a(v j) = min {a(v j), a(v) + l(v, v j)}.

Окрасить ту из вершин, для которой a(v j) окажется наименьшим.. окрасить также ребро, ведущее в выбранную на данном шаге вершину v j . Положить v = v j .

Шаг 3. Если v = v j , закончить процедуру, так как кратчайший маршрут из v 1 в v n . если v ¹ v n , то перейти к шагу 2.

Замечание. Шаг 2 невозможен, если все a(v j)= ¥. В этом случае вершина v n недостижима.

Применим изложенный алгоритм к заданному диаграммой графу. Найдем в нем кратчайший маршрут из v 1 в v 6 .

Шаг 1. Окрасим вершину v 1 . Присвоим вершинам индексы: a(v 1) =0, a(v 2) = a(v 3)=…= a(v n)=¥. Полагаем v 1 = v.

a(v 2) = min {¥, 0+4} = 4,

a(v 3) = min {¥, 0+7} = 7,

a(v 4) = min {¥, 0+3} = 3,

a(v 5) = min {¥, 0+¥} = ¥,

a(v 6) = min {¥, 0+¥} = ¥.

Окрашиваем вершину v 4 и ребро {v 1 , v 4 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 4 .

a(v 2) = min {4, 3+¥} = 4,

a(v 3) = min {7, 3+¥} = 7,

a(v 5) = min {¥, 3+3} = 6,

a(v 6) = min {¥, 3+¥} = ¥.

Окрашиваем вершину v 2 и ребро {v 1 , v 2 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 2 .

a(v 3) = min {7, 4+3} = 7,

a(v 5) = min {6, 4+2} = 6,

a(v 6) = min {¥, 4+¥} = ¥.

Окрашиваем вершину v 5 и ребро {v 4 , v 5 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 5 .

a(v 3) = min {7, 6+¥} = 7,

a(v 6) = min {¥, 6+2} = 8.

Окрашиваем вершину v 3 и ребро {v 1 , v 3 }.

Шаг 3. Так как вершина v 6 не окрашена, выполняем шаг 2, полагая v = v 3 .

a(v 6) = min {8, 7+2} = 8.

Окрашиваем вершину v 6 и ребро {v 5 , v 6 }.

Так как вершина v 6 окрашена, то работу прекращаем. Получили минимальный маршрут v 1 v 4 v 5 v 6 , длина которого равна 8 .

Заметим, что это в данном случае не единственный для вершин v 1 и v 6 минимальный маршрут, т.к. в алгоритме имелась возможность окрасить вместо ребра {v 4 , v 5 } ребро {v 2 , v 5 }, тогда бы получили другой маршрут той же длины.

4. Задачи на деревьях

Ациклическим называется граф, в котором отсутствуют циклы.

Граф без циклов называется лесом.

Дерево – это связный ациклический граф.

Пусть - связный неориентированный граф. Так как любые две вершины графа и связаны, то существуют простые цепи с концами и . Таких цепей может быть несколько. Их длины являются неотрицательными целыми числами. Следовательно, между вершинами и должны существовать простые цепи наименьшей длины . Длина цепи наименьшей длины, связывающей вершины и , обозначается символом и называется расстоянием между вершинами и . По определению .

Нетрудно убедиться, что введенное таким образом понятие расстояния, удовлетворяет аксиомам метрики:

2. тогда и только тогда, когда ;

3. ;

4. справедливо неравенство треугольника:

Для фиксированной вершины графа расстояние до наиболее удаленной от нее вершины: , называют эксцентриситетом (максимальным удалением ) вершины .

Диаметром графа называют число , равное расстоянию между наиболее удаленными друг от друга вершинами графа:

.

Простая цепь, длина которой равна , называется диаметральной цепью . Очевидно, что диаметр графа равен наибольшему среди всех эксцентриситетов вершин графа. Вершина называется периферийной , если .

Минимальный из эксцентриситетов вершин связного графа называют его радиусом и обозначают :

Так как диаметр графа равен наибольшему из эксцентриситетов вершин, а радиус - наименьшему, то радиус графа не может быть больше его диаметра. Вершина называется центральной , если . Множество всех центральных вершин графа называют его центром . Центром графа может быть одна вершина или несколько вершин. Есть графы, центр которых совпадает с множеством всех его вершин. Например, центр простой цепи состоит из двух вершин при четном числе ее вершин и из одной - при нечетном, а у любого цикла все вершины являются центральными.

Для иллюстрации обратимся к графу на рис. 4.29. Здесь

Поэтому

Вершина 2 является центром графа, а все остальные его вершины - периферийные. Цепь 1, 2, 3 - одна из диаметральных цепей.

Для связного орграфа расстояние между вершинами и определяется как расстояние между вершинами и в неориентированном дубликате этого графа.

Задача нахождения центральных вершин графа постоянно встречается в практической деятельности. Пусть, например, вершины графа соответствуют небольшим поселкам, а его ребра - дорогам между ними. Требуется оптимально разместить по этим населенным пунктам, скажем, магазины. В подобных ситуациях критерий оптимальности обычно заключается в оптимизации «наихудшего» случая, то есть в минимизации расстояния от магазина до наиболее удаленного поселка. Такой подход к оптимизации предполагает размещение магазинов в поселках, которые представляют центральные вершины графа.

Обходы графов

Уже отмечалось, что начало теории графов связывают с задачей о кенигсбергских мостах. Эта знаменитая в свое время задача состоит в следующем. Семь мостов города Кенигсберга (ныне Калининграда) были расположены на реке Прегель так, как изображено на рис. 4.30. Задача состоит в том, чтобы, выйдя из дома, вернуться обратно, пройдя только один раз по каждому мосту.

Так как в задаче существенны только переходы через мосты, план города можно свести к изображению графа (точнее, мультиграфа), в котором ребра соответствуют мостам, а вершины - различным разделенным частям города, которые обозначены буквами (рис. 4.30, справа). Эйлер показал, что нельзя пройти по одному разу по всем кенигсбергским мостам и вернуться назад. В своей работе, опубликованной в 1736 году, он сформулировал и решил следующую общую проблему теории графов: при каких условиях связный граф содержит цикл, проходящий через каждое его ребро.

Цикл в графе называется эйлеровым , если он содержит все ребра графа. Связный граф, в котором есть эйлеров цикл, называется эйлеровым графом. Такой граф можно нарисовать, не отрывая карандаша от бумаги и не повторяя линий.

Например, граф, изображенный на рис. 4.31, является эйлеровым, поскольку он содержит эйлеров цикл 1, 2, 3, 4, 5, 6, 4, 2, 6, 1. В этом графе есть и другие эйлеровы циклы. Ясно, что любые два таких цикла отличаются друг от друга только порядком обхода ребер.

Теорема 4.7. (Л. Эйлер, 1736 г.) Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны.

Цепь называется эйлеровой , если она содержит все ребра графа.

Теорема 4.8 (Л. Эйлер, 1736 г.) Мультиграф обладает эйлеровой цепью тогда и только тогда, когда он связен и число вершин нечетной степени равно 0 или 2.



Несмотря на «похожесть» в определениях для эйлеровых и гамильтоновых циклов, соответствующие теории, устанавливающие критерии существования и алгоритмы поиска таких циклов, имеют мало общего. Терема Эйлера (теорема 4.7) позволяет легко установить, является ли граф эйлеровым. Разработаны алгоритмы, позволяющие достаточно просто найти эйлеровы циклы эйлерова графа. Что касается гамильтоновых графов, то здесь положение дел существенно иное. Ответить на вопрос, является ли некий граф гамильтоновым, как правило, очень трудно. Общего критерия, подобного критерию Эйлера, здесь нет. Но, как оказалось, среди множества всех графов эйлеровых графов ничтожно мало, а вот гамильтоновых графов достаточно много.

Утверждение. Если для двух вершин существует маршрут, связывающий их, то обязательно найдется минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута через d(v, w).

Определение. Величину d(v, w) (конечную или бесконечную) будем называть расстоянием между вершинами v, w . Это расстояние удовлетворяет аксиомам метрики:

1) d(v, w) 0, причем d(v, w) = 0 тогда и только тогда, когда v= w;

2) d(v, w) = d(w, v);

3) d(v, w) d(v, u) + d(u, w).

Определение. Диаметром связного графа называется максимально возможное расстояние между двумя его вершинами.

Определение. Центром графа называется такая вершина, что максимальное расстояние между ней и любой другой вершиной является наименьшим из всех возможных; это расстояние называется радиусом графа.

Пример 82.

Для графа G, изображенного на рис. 3.16, найти радиус, диаметр и центры.

Рис. 3.16. Граф для примера 82

Решение.

Чтобы определить центры, радиус, диаметр графа G , найдем матрицу D(G) расстояний между вершинами графа, элементами d ij которой будут расстояния между вершинами v i и v j . Для этого воспользуемся графическим представлением графа. Заметим, что матрица D(G) симметрична относительно главной диагонали.

С помощью полученной матрицы для каждой вершины графа G определим наибольшее удаление из выражения: для i, j = 1, 2, …, 5 . В результате получаем: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3. Минимальное из полученных чисел является радиусом графа G , максимальное – диаметром графа G . Значит, R(G) = 2 и D(G) = 3 , центрами являются вершины v 2 , v 3 , v 4 .