ПАРОСОЧЕТАНИЯ

6.14. Максимальные паросочетания

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

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

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

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

В случае, когда каждая вершина покрыта, говорят, что паросочетание — совершенно. Совершенное паросочетание иногда называют -факторным [90]. Если существует совершенное паросочетание для то, очевидно, оно является максимальным. (Заметим, что совершенное паросочетание не может существовать, если -нечетное.) Татт [90] выделил множество графов, обладающих совершенными паросочетаниями.

Основная цель данного раздела состоит в описании алгоритма, предложенного Эдмондсом [20] для нахождения максимального паросочетания в произвольном графе.

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

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

Пусть паросочетание графа Тогда простая цепь называется чередующейся цепью относительно если ее ребра (при прохождении цепи от одного конца до другого) являются поочередно ребрами паросочетания (ребрами и ребрами

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

Для иллюстрации сделанных замечаний рассмотрим паросочетание выделенное жирными линиями на рис. 6.29, а.

Рис. 6.29.

Множество показанное на рис. 6.29, с, получается при использовании чередующейся цепи С, проведенной на рис. Если, как в предшествующем примере, конечные точки чередующейся цепи С не покрыты ребрами то легко видеть, что обязательно является паросочетанием и По этой причине чередующаяся цепь, обе конечные точки которой не покрыты, называется чередующимся расширением. Существование чередующегося расширения (или просто расширения) является необходимым и достаточным условием того, что не является максимальным паросочетанием. Сказанное можно сформулировать в виде следующей теоремы, предложенной Бержем [3] и доказанной на основе идей Эдмондса [20].

Теорема 6.9. Паросочетание в графе является максимальным тогда и только тогда, когда не содержит чередующегося расширения относительно

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

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

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

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

Известно несколько эффективных алгоритмов нахождения максимальных паросочетаний в двудольных графах (см., например, [22] и [49]). Алгоритм, описанный ниже, применим для любых графов. Он основан на систематическом поиске чередующихся расширений и последовательном расширении паросочетаний. В процессе его функционирования находятся определенные области графа (соответствующие так называемым венгерским деревьям), которые могут быть удалены при

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

Перед тем как переходить к описанию алгоритма, введем несколько вспомогательных понятий. Чередующееся дерево — это дерево, вершины которого разбиты на два класса (называемые внутренними и внешними вершинами) так, что каждая внутренняя вершина имеет степень 2 и каждое ребро соединяет внутреннюю вершину с внешней. (Заметим, что все «конечные» вершины, т. е. вершины степени 1, обязательно внешние.)

Рис. 6.30.

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

Чтобы найти максимальное паросочетание чередующегося дерева, нужно выбрать любую внешнюю вершину в качестве и определить число ребер в цепи, соединяющей с любой другой вершиной Считается, что (этот процесс иллюстрируется рис. Каждая внутренняя вершина смежна в точности с одной внешней вершиной так, что (т. е. лежит «между» Множество ребер, соединяющих все такие пары образует паросочетание. Это паросочетание обязательно будет максимальным, так как

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

Упражнения

(см. скан)

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

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

Цветущее дерево есть растущее дерево вместе с ребром в соединяющим две внешние вершины Если обозначают чередующиеся цепи, соединяющие эти вершины с то называется цветком, называется стволом и называется соцветием. Введенные понятия иллюстрируются рис. 6.31. (Если корень дерева инцидентен с соцветием, то в стволе нет ребер.) Вершина, в которой ствол соединяется с соцветием, называется верхушкой ствола.

Пусть - растущее дерево графа относительно паросочетания и предположим, что некоторое ребро соединяет внешнюю вершину с покрытой

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

Рис. 6.31.

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

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

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

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

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

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

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

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

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

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

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

Проиллюстрируем алгоритм нахождения максимального паросочетания на примере графа рис. 6.32, а. Будем помечать ребра и корень текущего варианта растущего дерева утолщенными линиями, а ребра паросочетания — звездочками.

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

Рис. 6.32. (см. скан)

Таким образом, мы добавляем ребро 13 к и начинаем новое растущее дерево в вершине С, как показано на рис. Относительно нового ребра 11 и 13 удовлетворяют условиям увеличения (рис. 6.32, с). Текуйхее дерево является расширяющимся относительно ребра 10. Увеличиваем отбрасываем и начинаем новое дерево в как показано на рис. 6.32, d. Двумя расширениями

(на основе ребер 6 и 7) мы увеличиваем (рис. 6.32, е). Теперь расширяющееся относительно ребра 12. Увеличиваем и начинаем новое дерево в 1, как показано на рис. Два расширения (на основе ребер 8 и 9) образуют дерево, показанное на рис. которое является венгерским. Его внешние вершины связаны только с внутренними вершинами дерева. Теперь временно удалим дерево из рассмотрения и выделим подграф полученный удалением вершин венгер-. ского дерева и всех ребер, инцидентных его вершинам. Этот подграф показан на рис. Здесь мы выбрали новый корень А и увеличили дерево за счет ребра 1. Полученное дерево является расширяющимся по отношению к ребру 2 и дает новое паросочетание в состоящее из двух ребер Это паросочетание является, очевидно, максимальным (точнее, совершенным) в Объединяя его с найденным ранее максимальным паросочетанием венгерского дерева, получим (как будет показано далее) максимальное паросочетание для В рассмотренном примере нам не потребовалось прибегать к процедуре стягивания соцветий.

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

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

рис. 6.33, с. Растягивая соцветия в обратном порядке и восстанавливая паросочетания, удаленные при стягивании, получим максимальное паросочетание, показанное на рис.

Рис. 6.33.

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

Упражнение 6.21. Найти максимальное паросочетание для графов, показанных на рис. 6.15 и 6.17.

Итак, в предыдущих разделах мы ввели терминологию и предварительные сведения, необходимые для описания алгоритма, и проиллюстрировали его работу на небольшом частном примере. Опишем теперь алгоритм в общем виде.

Рис. 6.34.

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

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

В конечном счете, после удаления конечного числа венгерских деревьев и рассмотрения соответствующих оставшихся графов оказывается, что либо и есть пустой граф, либо содержит совершенное паросочетание для После этого восстанавливаем поочередно и их максимальные паросочетания. Если некоторые вершины являются псевдовершинами, то растянем их в соцветия. (Во избежание ошибок лучше всего это делать в порядке, обратном их стягиванию.) При этом после растягивания найдем для соответствующего соцветия максимальное паросочетание, ни одно ребро которого не инцидентно вершине, служившей верхушкой ствола в момент стягивания. После растягивания всех соцветии получим паросочетание, которое является максимальным для первоначального графа. Подробное обоснование предложенного алгоритма приводится в работе [20].

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

Легко видеть, что задача о максимальном паросочетаний соответствует частному случаю, когда для каждой вершины

Эдмондс непосредственно обобщил приведенный выше алгоритм на решение общей задачи нахождения максимального подграфа с ограниченными степенями для произвольных неотрицательных Он также рассмотрел еще одно важное обобщение задачи о максимальном паросочетаний, когда требуется найти паросочетание с максимальным общим весом при условии, что каждому ребру графа поставлено в соответствие число, называемое «весом» (исходная задача о паросочетаний соответствует случаю, когда все веса равны единице). Алгоритм решения этой задачи [18] можно объединить с алгоритмом нахождения кратчайших путей (глава 3) и решить на их основе «задачу китайского почтальона», впервые предложенную Кваном [56а]. Эта задача сводится к нахождению замкнутой цепи, в которую каждое ребро связного графа входит по крайней мере один раз и которая имеет минимальный общий вес. (Другими словами, задача состоит в том, чтобы получить уникурсальный граф за счет дублирования ребер при минимальном дополнительном весе.)