Главная Промышленная автоматика.

3. Шаг 2 повторяется до тех пор, пока существуют чередующиеся цепи относительно М. Если таких цепей больще нет, то М - максимальное паросочетание.

Нам осталось показать способ построения чередующихся цепей относительно паросочетания М. Рассмотрим более простой случай, когда граф G является двудольным графом с множеством верщин, разбитым на два подмножества Vi и Fj. Мы будем строить граф чередующейся цепи по уровням / = О, 1, 2, используя процесс, подобный поиску в щирину. Ераф чередующейся цепи уровня О содержит все непарные верщины из множества Vj. На уровне с нечетным номером i добавляются новые верщины, смежные с верщинами уровня i - 1 и соединенные ребром, не входящим в паросочетание (это ребро тоже добавляется в строящийся граф). На уровне с четным номером i также добавляются новые верщины, смежные с верщинами уровня / - /, но которые соединены ребром, входящим в паросочетание (это ребро тоже добавляется в граф чередующейся цепи).

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

Пример 7.10. На рис. 7.15 изображен граф чередующейся цепи, построенный для графа из рис. 7.13, а относительно паросочетания, показанного на рис. 7.14. На уровне О имеем одну непарную верщину 5. На уровне 1 добавлено ребро (5, 6), не входящее в паросочетание. На уровне 2 добавлено ребро (6, 2), входящее в паросочетание. На уровне 3 можно добавить или ребро (2, 9), или ребро (2, 10), не входящие в паросочетание. Поскольку верщины 9 и 10 пока в этом графе непарные, можно остановить процесс построения графа чередующейся цепи, добавив в него одну или другую верщину. Оба пути 9, 2, 6, 5 и 10, 2, 6, 5 являются чередующимися цепями относительно паросочетания из рис. 7.14. □


Рис. 7.15. Граф чередующейся цепи

Пусть граф G имеет и вершин и е ребер. Если используются списки смежности для представления ребер, то на построение графа чередующейся цепи потребуется времени порядка 0(e). Для нахождения максимального паросочетания надо построить не более л/2 чередующихся цепей, поскольку каждая такая цепь увеличивает текущее паросочетание не менее чем на одно ребро. Поэтому максимальное паросочетание для двудольного г{кфа можно найти за время порядка 0(пе).

Упражнения

7.1. Опишите алгоритм вставки и удаления ребер неориентированного графа, представленного списками смежности. Помните, что каждое ребро (i,j) появляется в списке смежности вершины / и вершины j.

7.2. Измените представление неориентированного графа посредством списков смежности так, чтобы первое ребро в списке смежности любой вершины можно было бы удалить за фиксированное время. Напишите процедуру удаления первых ребер, инцидентным вершинам, используя новое представление списков смежности. Подсказка: как сделать так, чтобы две ячейки, соответствующие ребру (iyj)y могли быстро находить друг друга?

МНЕНИЯ 225



7.3.

Для графа, показанного на рис. 7.16, постройте

а) остовное дерево минимальной стоимости посредством алгоритма Прима;

б) остовное дерево минимальной стоимости с помощью алгоритма Крускала;

в) остовное дерево методом поиска в глубину, начиная с вершин and;

г) остовное дерево методом поиска в ширину, начиная с вершин а ш d.


7.4.

Рис. 7.16. Граф

Пусть Г - глубинное остовное дерево и В - множество обратных ребер для связного неориентированного графа G = (V, Е).

*а) Покажите, что добавление в остовное дерево Г любого обратного ребра из множества В приводит к образованию в Г одного цикла. Назовем такой цикл базовым.

Линейной комбинацией циклов Cj, С2, С„ называется структура

Ci Д Сг А ... А С„. Докажите, что линейная комбинация двух различных пересекающихся циклов является циклом.

**с) Покажите, что любой цикл в графе G можно представить как линейную комбинацию базовых циклов.

Пусть G = (V, Е) - произвольный граф. Обозначим через R такое отношение на множестве вершин V, что uRv выполняется тогда и только тогда, когда вершины и и V принадлежат одному общему (не обязательно простому) циклу. Докажите, что отношение Д является отношением эквивалентности на множестве V.

Реализуйте алгоритмы Прима и Крускала. Сравните время выполнения ваших программ на множестве "случайных" графов.

Напишите программу нахождения всех связных компонент графа. Напишите программу с временем выполнения 0(п), чтобы определить, есть ли в графе с я вершинами цикл.

Напишите программу пересчета всех простых циклов в графе. Сколько может быть таких циклов? Какова временная сложность (время выполнения) такой программы?

Докажите, что при обходе вершин графа методом поиска в ширину каждое ребро может быть или ребром дерева, или обратным ребром.

Реализуйте алгоритм нахождения точек сочленения, описанный в разделе 7.4. Пусть G = (V, Е) - полный граф, т.е. такой, что для любой пары различных вершин существует соединяющее их ребро. Пусть G = (V, Е) - ориентированный граф, в котором множество дуг Е получено путем случайной ориентации ребер из множества Е. Покажите, что орграф G имеет путь, который проходит через все вершины графа точно один раз.

7.13. Покажите, что полный граф с л вершина имеет п" ~ остовных деревьев.

*7.5.

7.6.

7.7. 7.8.

7.9.

7.10.

7.11. "7.12.



7.14. Найдите все максимальные паросочетания для графа, изображенного на рис. 7.12.

, 7.15. Напишите программу нахождения максимального паросочетания для двудольного графа.

7.16. Пусть М - паросочетание им - число ребер в максимальном паросочетаний. Докажите, что

а) сушествуют чередующееся цепи относительно М, чья длина равна 2(м/(т - М)) -i- 1 или меньше;

б) если Р - кратчайшая чередующаяся цепь относительно М, а Р - чередующаяся цепь относительно МД Р, тогда \Р\ > \Р\ -i- \Р Л Р\.

*7.17. Докажите, что граф будет двудольным тогда и только тогда, когда он не имеет циклов нечетной длины. Приведите пример недвудольного графа, для которого способ построения графа чередующейся цепи, изложенный в разделе 7.5, не работает.

7.18. Пусть М и N - паросочетания в двудольном графе, причем \М\ < \N\. Докажите, что М А TSf имеет по крайней мере \jV\ - \М\ вершин, не входящих в чередующиеся цепи относительно М.

Библиографические примечания

Изучение методов построения минимальных остовных деревьев начато Борувкой (Boravka) еше в 1926 году [14]. Два описанных в этой главе алгоритма построения остовных деревьев взяты из [67] и [88]. В работе [57] показано, как можно использовать частично упорядоченные деревья для реализации алгоритма Прима. В [17] и [123] представлены алгоритмы построения остовных деревьев с временной сложность 0(е log logn). В [109] предлагается исчерпывающий обзор и историческая справка по алгоритмам построения остовных деревьев.

В [52] и [107] рассмотрены различные варианты применения метода поиска в глубину для алгоритмов, работающих с графами. Алгоритм нахождения двусвязных компонент взят из этих работ.

Паросочетания графов изучались в [46], а чередующиеся цепи - в [10] и [27]. В работе [51] приведен алгоритм наховдения максимального паросочетания для двудольных графов с временной сложностью 0(п-), а в [75] - с временем выполнения

0(\1\ F - \ £ I) для произвольных графов. Статья [82] содержит хорошее обсркдение

проблем паросочетаний.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 [71] 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0018