Дискретно-непрерывная математика (стр. 76 )

Рис. 5.30.

Число внешних вершин чередующегося дерева всегда точно на единицу больше числа внутренних вершин. Действительно, каж­дое ребро дерева инцидентно в точности одной внут­ренней вершине. Следовательно, если существует m ребер, то существуют m/2 внутренних вершин и (m+l) — m/2=m/2+l внешних вершин.

Чтобы найти максимальное паросочетание чередую­щегося дерева, нужно выбрать любую внешнюю верши­ну в качестве v0 и определить di, число ребер в цепи, соединяющей v0 с любой другой вершиной vi. Считается, что do=0 (этот процесс иллюстрируется рис. 8.30, b). Каждая внутренняя вершина vi смежна в точности с од­ной внешней вершиной vj так, что dj=di+1 (т. е. vi ле­жит «между» v0 и vj). Множество ребер, соединяющих все такие пары vi и vj, образует паросочетание. Это па­росочетание обязательно будет максимальным, так как только одна вершина v0 не покрыта. Соответственно для каждой внешней вершины существует максимальное паросочетание, оставляющее только эту вершину непо­крытой, и каждое максимальное паросочетание череду­ющегося дерева принадлежит к названному типу.

Упражнения

18. Доказать, что множество ребер, определенных в предыду­щем абзаце, образует паросочетание.

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

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

Если М — паросочетание в графе G, то растущее де­рево в G есть чередующееся дерево Т в G такое, что все ребра паросочетания, которые инцидентны вершинам T, являются ребрами дерева и эти ребра образуют максимальное паросочетание для Т. Единственная не­покрытая вершина Т называется корнем растущего де­рева Т.

Пусть Т будет растущее дерево в G относительно па­росочетания М и v0 — его корень. Если существует реб­ро е графа G, соединяющее внешнюю вершину Т с не­покрытой вершиной в G, отличной от v0, то Т называет­ся расширяющимся относительно е. Очевидно, что существует чередующаяся цепь, соединяющая две непо­крытые вершины, и М может быть увеличено описанным ранее способом.

Цветущее дерево есть растущее дерево Т вместе с ребром в G, соединяющим две внешние вершины Т. Если С1 и С2 обозначают чередующиеся цепи, соединя­ющие эти вершины с v0, то C1 C2 называется цветком, C1∩C2 называется стволом и С1 С2 называется соцве­тием. Введенные понятия иллюстрируются рис. 5.31.

Pис. 5.31

(Если корень дерева инцидентен с соцветием, то в ство­ле нет ребер.) Вершина, в которой ствол соединяется с соцветием, называется верхушкой ствола.

Пусть Т—растущее дерево графа G относительно паросочетания М, и предположим, что некоторое ребро е соединяет внешнюю вершину

v T с покрытой вершинйй w T. Тогда ребро f, которое покрывает w вме­сте со своей другой граничной точкой х, не принадлежит Т (почему?). В этом случае мы можем увеличить Т, до­бавляя ребра е и f и вершины w и х (как внутреннюю и внешнюю соответственно).

Заметим, что все три при­веденных понятия (расширя­ющееся дерево, цветущее дерево и дерево, которое может быть увеличено) связаны с рас­смотрением растущего дерева и ребра, инцидентного одной из его внешних вершин. Они различаются в зави­симости от типа другой конечной точки рассматриваемо­го ребра (принадлежит дереву, покрыта или не покрыта). Естественно одно и то же растущее дерево может удов­летворять нескольким из этих условий относительно раз­личных ребер. Если оно не удовлетворяет ни одному из названных условий при рассмотрении любого ребра, ин­цидентного любой внешней вершиной, то мы приходим к понятию венгерского дерева. Растущее дерево Т в G называется венгерским деревом, если каждое ребро G, которое инцидентно некоторой внешней вершиной Т, соединяет ее с внутренней вершиной Т. Таким образом, Т не является расширяемым или цветущим деревом отно­сительно произвольного ребра е графа G и его нельзя увеличить, как делалось в предыдущем абзаце.

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

Теорема 5.10. Растущее дерево Т в G может быть увеличено до расширяющегося дерева, до цветущего де­рева, либо до венгерского дерева.

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

Перейдем теперь к описанию алгоритма нахождения максимального паросочетания. Возьмем любое паросочетание М в G и любое растущее дерево Т относительно М. (В качестве М можно взять пустое множество, а в качестве Т — любую вершину.)

1. Если Т - расширяющееся дерево относительно не­которого ребра е графа G, то, используя чередующуюся цепь, увеличим М до паросочетания М', имеющего на одно ребро больше. Если М'— не совершенное паросочетание, то выбираем новое растущее дерево Т (например, с началом в любой непокрытой вершине).

2. Если Т—цветущее дерево относительно некоторо­го ребра е, то стянем вершины и ребра цветения в но­вую псевдовершину и удалим получившиеся петли.

3. Если Т может быть увеличено добавлением двух новых вершин и ребер, как это было описано выше, то увеличим Т.

4. Повторим шаги 1—3 до тех пор, пока не будет найдено либо венгерское дерево, либо максимальное паросочетание (в преобразованном графе, где ряд соцве­тий может быть стянут).

В результате, если венгерское дерево Т содержит все вершины преобразованного графа G*, то текущее паросочетание М, очевидно, является максимальным в G*. Если это не так, то удалим из G* вершины Т и все реб­ра, инцидентные с этими вершинами, и повторим шаги 1—3 для оставшегося графа. Таким образом, мы посте­пенно удаляем одно венгерское дерево за другим до тех пор, пока не получим совершенное паросочетание в оставшейся части графа или оставшаяся часть графа оказывается венгерским деревом.

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

Проиллюстрируем алгоритм нахождения максималь­ного паросочетания на примере графа рис. 5.32, а.

Рис. 5.32.

Бу­дем помечать ребра и корень текущего варианта расту­щего дерева утолщенными линиями, а ребра паросочетания — звездочками.

Возьмем сначала в качестве М пустое множество и выберем в качестве начала растущего дерева Т любую непокрытую вершину, скажем F. Дерево Т является рас­ширяющимся относительно ребра 13. Таким образом, мы добавляем ребро 13 к М и начинаем новое растущее дерево в вершине С, как показано на рис. 5.32, b. Отно­сительно нового Т ребра 11 и 13 удовлетворяют усло­виям увеличения Т (рис. 5.32, с). Текущее дерево явля­ется расширяющимся относительно ребра 10. Увеличи­ваем М, отбрасываем Т и начинаем новое дерево в Н, как показано на рис. 5.32, d. Двумя расширениями (на основе ребер б и 7) мы увеличиваем Т (рис. 5.32, е). Теперь Т расширяющееся относительно ребра 12. Увели­чиваем М и начинаем новое дерево в 1, как показано на рис. 5.32, f. Два расширения (на основе ребер 8 и 9) образуют дерево, показанное на рис. 5.32, д, которое яв­ляется венгерским. Его внешние вершины (С, Н и I) связаны только с внутренними вершинами дерева. Те­перь временно удалим дерево из рассмотрения и выде­лим подграф G1, полученный удалением вершин венгерского дерева и всех ребер, инцидентных его вершинам. Этот подграф показан на рис. 5.32, h. Здесь мы выбрали новый корень А и увеличили дерево за счет ребра 1. Полученное дерево является расширяющимся по отно­шению к ребру 2 и дает новое паросочетание в G1, со­стоящее из двух ребер (рис. 5.32, i). Это паросочетание является, очевидно, максимальным (точнее, совершен­ным) в G1. Объединяя его с найденным ранее макси­мальным паросочетанием венгерского дерева, получим (как будет показано далее) максимальное паросочетание для G (рис. 5.32, j). В рассмотренном примере нам не по­требовалось прибегать к процедуре стягивания соцветий.