Структуры данных и алгоритмы (1021739), страница 56
Текст из файла (страница 56)
Пусть М — паросочетание в графе G. Вершину v будемназывать парной, если она является концом одного из ребер паросочетания М. Путь,соединяющий две непарные вершины, в котором чередуются ребра, входящие и невходящие в множество М, называется чередующейся (аугментальной) цепью относительно М. Очевидно, что чередующаяся цепь должна быть нечетной длины, начинаться и заканчиваться ребрами, не входящими в множество М. Также ясно, что,7.5. ПАРОСОЧЕТАНИЯ ГРАФОВ223имея чередующуюся цепь Р, мы можем увеличить паросочетание М, удалив из неготе ребра, которые входят в цепь Р, и вместо удаленных ребер добавить ребра из цепиР, которые первоначально не входили в паросочетание М.
Это новое паросочетаниеможно определить как М Л Р, где Д обозначает симметрическую разность множествМ и Р, т.е. в новое множество паросочетаний войдут те ребра, которые входят или вмножество М, или в множество Р, но не в оба сразу.Пример 7.9. На рис. 7.13,а показаны граф и паросочетание М, состоящее из ребер(на рисунке они выделены толстыми линиями) (1, 6), (3, 7) и (4, 8).
На рис. 7.13,6представлена чередующаяся цепь относительно М, состоящая из вершин 2, 6, 1, 8, 4,9. На рис. 7.14 изображено паросочетание (1, 8), (2, 6), (3, 7), (4, 9), которое получено удалением из паросочетания М ребер, входящих в эту чередующуюся цепь, и добавлением новых ребер, также входящих в эту цепь. ПРис. 7.14.четаниеУвеличенноепаросо-Паросочетание М будет максимальным тогда и только тогда, когда не будет существовать чередующейся цепи относительно М. Это ключевое свойство максимальных паросочетаний будет основой следующего алгоритма нахождения максимального паросочетания.Пусть М и N — паросочетания в графе G, причем \М\ < \N\ (здесь \М\ обозначаетколичество элементов множества М). Для того чтобы показать, что М Л N содержитчередующуюся цепь относительно М, рассмотрим граф G = (V, М Д N), где V —множестве концевых вершин ребер, входящих в М Д N.
Нетрудно заметить, что каждая связная компонента графа G" формирует простой путь (возможно, цикл), в котором чередуются ребра из М и N. Каждый цикл имеет равное число ребер, принадлежащих М и N, а каждый путь, не являющийся циклом, представляет собой чередующуюся цепь относительно или М, или N, в зависимости от того, ребер какогопаросочетания больше в этой цепи.
Поскольку \М\ < \N\, то множество MAN содержит больше ребер из паросочетания N, чем М, и, следовательно, существует хотя быодна чередующаяся цепь относительно М.Теперь можно описать алгоритм нахождения максимального паросочетания Мдля графа G = (V, Е).1.2.224Сначала положим М = 0.Далее ищем чередующуюся цепь Р относительно М, и множество М заменяетсяна множество MAP.ГЛАВА 7. НЕОРИЕНТИРОВАННЫЕ ГРАФЫ3.Шаг 2 повторяется до тех пор, пока существуют чередующиеся цепи относительно М. Если таких цепей больше нет, то М — максимальное паросочетание.Нам осталось показать способ построения чередующихся цепей относительно паросочетания М. Рассмотрим более простой случай, когда граф G является двудольным графом с множеством вершин, разбитым на два подмножества Vl и V2.
Мы будем строить граф чередующейся цепи по уровням i = О, 1, 2, ..., .используя процесс,подобный поиску в ширину. Граф чередующейся цепи уровня 0 содержит все непарные вершины из множества Vi. На уровне с нечетным номером i добавляются новыевершины, смежные с вершинами уровня i - 1 и соединенные ребром, не входящим впаросочетание (это ребро тоже добавляется в строящийся граф). На уровне с четнымномером i также добавляются новые вершины, смежные с вершинами уровня i - 1,но которые соединены ребром, входящим в паросочетание (это ребро тоже добавляется в граф чередующейся цепи).Процесс построения продолжается до тех пор, пока к графу чередующейся цепиможно присоединять новые вершины. Отметим, что непарные вершины присоединяются к этому графу только на нечетном уровне. В построенном графе путь от любойвершины нечетного уровня до любой вершины уровня О является чередующейся цепьотносительно М.Пример 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 имеет п вершин и е ребер. Если используются списки смежностидля представления ребер, то на построение графа чередующейся цепи потребуетсявремени порядка О(е). Для нахождения максимального паросочетания надо построить не более л/2 чередующихся цепей, поскольку каждая такая цепь увеличиваеттекущее паросочетание не менее чем на одно ребро.
Поэтому максимальное паросочетание для двудольного гр^фа можно найти за время порядка О(пе).Упражнения7.1.7.2.Опишите алгоритм вставки и удаления ребер неориентированного графа, представленного списками смежности. Помните, что каждое ребро (i, j) появляетсяв списке смежности вершины i и вершины j.Измените представление неориентированного графа посредством списковсмежности так, чтобы первое ребро в списке смежности любой вершины можно было бы удалить за фиксированное время. Напишите процедуру удаленияпервых ребер, инцидентным вершинам, используя новое представление списков смежности.
Подсказка: как сделать так, чтобы две ячейки, соответствующие ребру (i, j ) , могли быстро находить друг друга?7.3.Для графа, показанного на рис. 7.16, постройтеа) остовное дерево минимальной стоимости посредством алгоритма Прима;б) остовное дерево минимальной стоимости с помощью алгоритма Крускала;в) остовное дерево методом поиска в глубину, начиная с вершин а и d;г) остовное дерево методом поиска в ширину, начиная с вершин а и d.Рис. 7.16. Граф7.4.Пусть Т — глубинное остовное дерево и В — множество обратных ребер длясвязного неориентированного графа G = (V, Е).*а) Покажите, что добавление в остовное дерево Т любого обратного ребра измножества В приводит к образованию в Т одного цикла.
Назовем такойцикл базовым.**б) Линейной комбинацией циклов Сь С2, .... С„ называется структураCi Д С2 А ... А С„. Докажите, что линейная комбинация двух различных пересекающихся циклов является циклом.**с) Покажите, что любой цикл в графе G можно представить как линейнуюкомбинацию базовых циклов.*7.5.Пусть G = (V, Е) — произвольный граф. Обозначим через R такое отношениена множестве вершин V, что uRv выполняется тогда и только тогда, когдавершины и и v принадлежат одному общему (не обязательно простому) циклу. Докажите, что отношение Д является отношением эквивалентности намножестве V.7.6.
Реализуйте алгоритмы Прима и Крускала. Сравните время выполнения вашихпрограмм на множестве "случайных" графов.7.7. Напишите программу нахождения всех связных компонент графа.7.8. Напишите программу с временем выполнения О(п), чтобы определить, есть лив графе с п вершинами цикл.7.9. Напишите программу пересчета всех простых циклов в графе. Сколько можетбыть таких циклов? Какова временная сложность (время выполнения) такой•программы?7.10. Докажите, что при обходе вершин графа методом поиска в ширину каждоеребро может быть или ребром дерева, или обратным ребром.7.11. Реализуйте алгоритм нахождения точек сочленения, описанный в разделе 7.4.*7.12. Пусть G = (V, Е) — полный граф, т.е. такой, что для любой пары различныхвершин существует соединяющее их ребро.
Пусть G' = (V, Е') — ориентированный граф, в котором множество дуг Е' получено путем случайной ориентацииребер из множества Е. Покажите, что орграф G' имеет путь, который проходитчерез все вершины графа точно один раз.2*7.13. Покажите, что полный граф с л вершина имеет п" ~ остовных деревьев.226ГЛАВА 7. НЕОРИЕНТИРОВАННЫЕ ГРАФЫ7.14. Найдите все максимальные паросочетания для графа, изображенного нарис. 7.12., 7.15. Напишите программу нахождения максимального паросочетания для двудольного графа.7.16.
Пусть М — паросочетание и т — число ребер в максимальном паросочетании.Докажите, чтоа) существуют чередующееся цепи относительно М, чья длина равна2(\М\/(т - \М\)) + 1 или меньше;б) если Р — кратчайшая чередующаяся цепь относительно М, а Р" — чередующаяся цепь относительно М Д Р, тогда \Р"\ > \Р\ + \Р Л Р'\*7.17. Докажите, что граф будет двудольным тогда и только тогда, когда он не имеетциклов нечетной длины. Приведите пример недвудольного графа, для которогоспособ построения графа чередующейся цепи, изложенный в разделе 7.5, неработает.7.18. Пусть М и N — паросочетания в двудольном графе, причем \М\ < \N\. Докажите, что MAN имеет по крайней мере \N\ - \M\ вершин, не входящих в чередующиеся цепи относительно М.Библиографические примечанияИзучение методов построения минимальных остовных деревьев начато Борувкой(Boruvka) еще в 1926 году [14].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
