Глава 3 Элементы теории графов (стр. 6 )

b.  Найти минимум из расстояний, приписанных временным вершинам. Первую из таких вершин сделать постоянной.

3.  Когда vn станет постоянной вершиной, то расстояние, приписанное ей – это и есть длина кратчайшего пути. Сам путь (в обратном порядке) можно отследить, если пройти в обратную сторону – от вершины vn к v1 – по вторым координатам меток вершин.

  Пример 3.32 

F(¥,0)

Найти кратчайший путь из вершины А в вершину F во взвешенном графе. Вершины снабжаем пометками, и в графе будут присутствовать метки (¥,0), пока не найден путь. Вершины, которые будут становиться постоянными, выделяем жирным шрифтом.
а) б) в)
Вершина А стала постоянной (рис. а), с ней смежные В и С Þ для них нашли расстояния (это 5 и 6), заменили метки на (5,А) и (6,А). Минимальное из расстояний 5 Þ вершина В(5,А) становится постоянной (рис. б). Вычисляем расстояния от нее до смежных с ней С, Е, F, D. Расстояние до С будет 5+3=8 Þ оно больше текущего (6) Þ метка вершины С не меняется. Все остальные расстояния меньше ¥ Þ метки остальных вершин заменяются. Изо всех текущих меток расстояний min{12,15,7,6} = 6 Þ вершину С(6,А) делаем постоянной (рис. в). Смежная с ней временная вершина Е, расстояние до нее через С 6+7=13>7 Þ изменений нет. Теперь из временных вершин min=7 Þ вершина Е(7,В) становится постоянной. 7+4=11<15 Þ метка вершины F меняется на F(11,E) и она становится постоянной. Алгоритм завершен, расстояние от А до F равно 11, а кратчайший путь – A, B,E, F.

Алгоритм Флойда-Уоршалла

Находит кратчайшие расстояния между всеми парами вершин графа

Идея: Строится специальная матрица D, элементы которой – кратчайшие пути между всевозможными парами вершин графа G. При определении кратчайшего пути выбирается минимум из «прямого» расстояния между смежными вершинами vi и vj и суммарного расстояния при проходе через дополнительную вершину. Затем – более длинные пути и т. д.

Обозначим через длину кратчайшего пути из vi в vj с промежуточными вершинами во множестве {v1,…,vm}. Алгоритм использует три правила:

1) – вес дуги, соединяющий вершины vi и vj (т. е. первоначально матрица D – это исходная матрица весов).

2) .

3) Длина кратчайшего пути из вершины vi в вершину vj:.

Алгоритм строит матрицу за n шагов, т. е. строится матрица D(1), …, D(n)=D.

  Пример 3.33 

2

Найдем матрицу кратчайших расстояний для графа.
v1 v2 v3

Элементы матрицы D(1) находим по правилу . Первая строка и первый столбец не меняются. Получаем . Элементы матрицы D(2) находим по правилу . Без изменений второй столбец и вторая строка. .
Элементы матрицы D(3) находим по правилу . . Каждый из элементов (i, j) матрицы D равен наименьшему расстоянию между вершинами vi и vj.

3.5.3  Минимальный остов

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

Для постановки и решения задачи дадим некоторые определения.

Вес остовного дерева взвешенного графа равен сумме весов, приписанных его ребрам. Минимальным остовным деревом называется остовное дерево графа с минимальным весом.

Математическая формулировка задачи: во взвешенном связном графе G(V, E) найти минимальное остовное дерево T(V, E’).

Рассмотрим алгоритм Краскала (Cruskal) решения этой задачи. Идея алгоритма состоит в том, чтобы постепенно формировать дерево Т(V, E’), выбирая ребра с наименьшим весом так, чтобы не возникало циклов.

Первоначально множество Е’ пустое, V – множество вершин графа, Т пустое. Два следующих действия выполняются до тех пор, пока это возможно.

1)  Выбрать ребро минимального веса в исходном графе G, не принадлежащее множеству Е’, так, что его добавление в Е’ не создает цикла в дереве Т.

2)  Добавить это ребро во множество ребер Е’.

  Пример 3.34  Найти минимальный остов во взвешенном графе.
Построение остова начнем с ребра (v1, v3). Порядок присоединения ребер к остову:
(v1, v3), (v2, v5), (v1, v2) (или (v1, v5)), (v4, v5).
Вес остова W=1+2+1+4=8.

3.5.4  Эйлеровы графы

Цикл в графе называется эйлеровым, если он содержит все ребра графа. Связный граф, в котором существует эйлеров цикл, называется эйлеровым графом. Эйлеровой цепью (или путем) является цепь (путь), которая включает все ребра (дуги) графа по одному разу. Собственная эйлерова цепь – это эйлерова цепь, которая не является эйлеровым циклом.

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

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

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

Теорема 3.5  Граф имеет собственную эйлерову цепь (путь) Û когда он связный и ровно две его вершины имеют нечетную степень.

Вершины нечетной степени являются началом и концом эйлеровой цепи.

Если снова вернуться к рассмотренному примеру, то увидим, что эйлерова цепь в нем также не существует, т. к. вершин нечетной степени в нем 4.

А теперь разберемся, как найти эйлеров цикл. Сначала вспомним еще одно определение.

Мостом (или перешейком) называется такое ребро графа G, удаление которого увеличивает число связных компонент. Если ребро r принадлежит некоторому циклу C, то оно не может быть мостом.

  Пример 3.36  В данном графе ребра r1 и r2 являются мостами.

Для нахождения эйлеровой цепи в связном графе, который имеет вершины только четной степени, используют алгоритм Флери:

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

2) В очередной вершине выбираем путь по перешейку только в том случае, если нет пути по циклу.

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

  Пример 3.37  Пусть требуется построить эйлеров цикл для графа, изображенного на рисунке. Начать построение эйлерового цикла можно с любого ребра графа. Начиная с е1, получим цикл v1, e1, v5, e2, v4 ,e3, v3 ,e4 , v4 ,e5 ,v1,e6 ,v3, e8, v2, e7 ,v1. В данном случае сразу получили эйлерову цепь.

3.5.5  Гамильтоновы графы

Гамильтонова цепь (путь) – это простая цепь (путь), которая проходит через каждую вершину (узел) графа ровно по одному разу. Соответственно гамильтонов цикл – это простой цикл, который проходит через каждую вершину графа.

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

  Пример 3.38  Гиперкуб порядка n при n ³ 3 имеет гамильтонов цикл. Этот цикл описывается кодом Грея (каждые два соседних набора отличаются ровно одним разрядом Þ на графе они соединены ребром). (000, 001, 011, 111, 101, 100, 110, 010, 000).

В отличие от эйлерова графа, не существует четкого критерия для определения, является ли граф гамильтоновым.

В качестве практического применения задачи поиска гамильтонова пути можно назвать т. н. задачу коммивояжера. В ней требуется осуществить обход всех населенных пунктов, посещая каждый по разу, и при этом постараться пройти минимальное расстояние.

3.5.6  Контрольные вопросы

1.  Что такое компонента сильной связности? Как можно найти КСС в орграфе?

2.  Какие существуют алгоритмы решения задачи поиска кратчайших путей? В чем их различие?

3.  Какие пометки вершин используются в алгоритме Дейкстры и как с их помощью можно получить кратчайший путь?

4.  Какая матрица используется в алгоритме Флойда-Уоршалла? Что представляет из себя итоговая матрица?

5.  Какое практическое применение имеет задача поиска минимального остова?

6.  Единственным ли образом можно построить минимальный остов взвешенного графа?

7.  Какой граф называется Эйлеровым?

8.  Как можно проверить наличие в графе эйлерова пути или цикла?

9.  Какой алгоритм используется при нахождении эйлеровой цепи?

10.  Что такое гамильтонов граф?

11.  Каково практическое применение задачи поиска гамильтонова пути в графе?