15.5. Максимальные паросочетания в двудольном графе

Задача нахождения максимального паросочетания в двудольном графе имеет широкий спектр приложений. Например, она появляется как подзадача при решении транспортной задачи Хичкока [15.1]. Далее, составление расписаний в определенных случаях включает разбиение множества ребер двудольного графа на непересекающиеся

паросочетания этого графа. Определение элемента разбиения в свою очередь требует определения максимального паросочетания в двудольном графе. Это показано, например, в работе [15.35].

Ввиду такого разнообразия приложений интересна вычислительная сложность этой проблемы. Хопкрофт и Карп [15.36] показали, как построить максимальное паросочетание в двудольном графе за число шагов, пропорциональное где п — число вершин в графе. Методология их подхода основывается на некоторых интересных положениях (сформулированных ими) в теории паросочетаний. Эти положения и их алгоритм двудольного паросочетания обсуждаются в этом разделе.

15.5.1. Методология подхода Хопкрофта и Карпа

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

Пусть М — паросочетание. Добавляющий путь Р называется кратчайшим путем по отношению к М, если Р имеет наименьшую длину среди всех добавляющих по отношению к М путей.

Лемма 15.3. Пусть М и N — два паросочетания в графе G. Если , где , то содержит по меньшей мере не пересекающихся по вершинам добавляющих по отношению к М путей.

Доказательство. Рассмотрим порожденный подграф G графа G на множестве ребер . Согласно теореме 8.19, каждая (связная) компонента подграфа G является 1) циклом четной длины, ребра которого попеременно входят в либо 2) путем, ребра которого попеременно входят в

Пусть компонентами G будут , где С - имеет множества вершин и ребер

Пусть . Тогда есть —1, либо 0, либо 1 для любого тогда и только тогда, когда С - добавляющий по отношению к k

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

Лемма 15.4. Пусть М — паросочетание. Пусть и предположим, что мощность млксимального паросочетания есть s. Тогда существует добавляющий по отношению к М путь длины не более

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

Лемма 15.5. Пусть М — паросочетание, Р — кратчайший добавляющий по отношению к М путь, а Р — добавляющий по отношению к путь. Тогда

Доказательство. Пусть . Тогда N — паросочетание и . Поэтому содержит два не пересекающихся по вершинам добавляющих пути по отношению к М.

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

Лемма 15.6.

Теорема 15.4. Для всех таких i и j, что не пересекаются по вершинам.

Доказательство. Предположим, что пересекаются по вершинам. Тогда существуют такие k и что пересекаются по вершинам, а для любого не пересекается по вершинам с . Тогда -добавляющий путь по отношению к поэтому Но . Следовательно, . Таким образом, не имеют общих ребер. Но если имеют общую вершину v, то они имеют и общее ребро, которое инцидентно v и входит в Следовательно, не пересекаются по вершинам, и мы приходим к противоречию. Главный результат этого раздела формулируется в следующей теореме:

Теорема 15.5. Пусть s — мощность максимального паросочетания. Число различных целых чисел в последовательности меньше или равно

Доказательство. Пусть Тогда и по лемме 15.4

Таким образом, для каждого есть одно из положительных нечетных чисел, меньших или равных привносят не более различных целых чисел, а поэтому общее число целых чисел в последовательности меньше или равно Результаты, сформулированные в лемме 15.6 и теоремах 15.4 и 15.5, позволяют рассматривать вычисление последовательности как состоящее не более чем из таких фаз, что добавляющие пути, находимые на каждой фазе, имеют одинаковую длину и не пересекаются по вершинам. Так как все добавляющие пути на какой-либо фазе не пересекаются по вершинам, то они являются добавляющими путями по отношению к паросочетанию, с которого началась эта фаза. Это привело Хопкрофта и Карпа к предложению следующего альтернативного пути для описания порядка вычисления максимального паросочетания.

Шаг 0. Начать с нулевого паросочетания М, т. е.

Шаг 1. Пусть — длина кратчайшего добавляющего пути по отношению к М. Найти максимальное множество путей со следующими свойства

1) для каждого — добавляющий путь по отношению к М и

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

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

15.5.2. Алгоритм Хопкрофта и Карпа для нахождения максимального двудольного паросочетания

Пусть G — связный двудольный граф, множество вершин которого разбито на подмножества X и Y. Мы будем называть вершины из X верхними, а вершины из Y — нижними.

Способ выполнения шага 1, предложенный Хопкрофтом и Карпом и упомянутый ранее, состоит из двух стадий. Если паросочетание М не максимально, то на первой стадии выполнения шага 1 строится такой ориентированный граф G, что кратчайшие добавляющие пути по отношению к М взаимнооднозначно соответствуют ориентированным путям в графе G, которые начинаются в свободной нижней вершине, а заканчиваются в свободной верхней вершине. На второй стадии строится максимальное множество таких ориентированных путей в графе G с тем свойством, что они не пересекаются по вершинам. Эти пути дают требуемые кратчайшие добавляющие пути в графе G по отношению к М.

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

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

Рассмотрим такое множество нижних вершин что существует ориентированное ребро из каждой из этих вершин по меньшей мере в одну верхнюю вершину из

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

множество свободных нижних вершин в множество ориентированных ребер, соединяющих Тогда требуемый граф G имеет множество вершин и множество ребер

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

Предположим, что мы построили множество вершин и множества ребер Рассмотрим множество таких нижних вершин которые не встречались в что каждая из них смежна по меньшей мере с одной из верхних вершин множества

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

Иначе (если не содержит свободных нижних вершин) пусть — множество ребер, соединяющих и пусть — множество напарников нижних вершин в Пусть также множество соответствующих ребер, вошедших в паросочетание. Ясно, что процедура, описанная выше, закончится одним из двух следующих способов:

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

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

Таким образом, граф G обладает следующими свойствами:

1. Для нечетного i множество состоит из нижних вершин. В противном случае оно состоит из верхних вершин.

2. Каждое ребро графа G ориентировано из вершины множества в вершину множества для некоторого .

3. Граф G не имеет ориентированных циклов.

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

Ясно, что сложность построения графа G составляет Из свойства 4 следует, что порождение максимального множества не пересекающихся по вершинам добавляющих путей в графе G по отношению к М эквивалентно порождению максимального множества не пересекающихся по вершинам ориентированных путей в графе G, которые начинаются в свободных нижних и заканчиваются в свободных верхних вершинах. Такие ориентированные пути в графе G могут быть порождены за шагов поиском в глубину в графе G, как мы увидим в алгоритме 15.6.

Представим алгоритм Хопкрофта и Карпа для максимального двудольного паросочетания. Не нарушая общности, предположим, что данный графсвязен. Алгоритм состоит из двух процедур: PROC-HOPKARP и PROC-AUGMENT.

PROC-HOPKARP — главная процедура. По данному паросочетанию М она проверяет, является ли М максимальным паросо-четанием. Если нет, то строит графв и вызывает PROC-AUGMENT. PROC-AUGMENT порождает максимальное множество не пересекающихся по вершинам ориентированных добавляющих путей в графе G и выполняет необходимые расширения. Добавляющие пути, построенные при каком-либо выполнении этой процедуры, соответствуют путям в отдельной фазе последовательности

В PROC-AUGMENT мы используем массив PATH, в котором запоминаются вершины пути по мере его порождения. Переменная POINT указывает на самый верхний элемент в массиве PATH.

Алгоритм 15.6. Максимальное двудольное паросочетание (Хопкрофт и Карп). PROC-HOPKARP.

H1. G - данный связный двудольный граф. Пусть -нулевое паросочетание, т. е. Положить

Н2. Построить из графа G ориентированный граф G, ориентируя каждое не вошедшее в паросочетание ребро (по отношению к ) графа G из нижней вершины в верхнюю и каждое вошедшее в паросочетание ребро (по отношению к ) из верхней вершины в нижнюю.

Н3. Пусть -множество свободных верхних вершин по отношению к Если не пусто, то идти к шагу Н4. Иначе HALT. (Паросочетание максимально.)

Н4. Построить последовательность подмножеств множества вершин V графа G и последовательность подмножеств множества таких ребер Е графа G, что

1)

2) для некоторого нижние вершины .

Н5. Если определено, то идти к шагу иначе HALT. (Не существует добавляющего пути по отношению к и, следовательно, максимальное паросочетание.)

Н6. Построить подграф графа G, где нижние (свободные нижние вершины).

Н7. Выполнить процедуру PROC-AUGMENT и идти к шагу PROC-AUGMENT.

А1. Положить POINT=0. (Содержание массива PATH очевидно.) Выбрать свободную нижнюю вершину у графа G, которая еще не помечена как «рассмотренная», и идти к шагу Если такой свободной нижней вершины не существует, то идти к шагу А8.

А2. Пометить у как «рассмотренную». Положить (у помещается сверху в массив PATH.)

А3. Выбрать ребро которое еще не помечено как «рассмотренное», и идти к шагу Если такого ребра не существует (мы не можем получить добавляющий путь, который включает вершину ), то выполнить следующие действия:

А4. Положить (POINT). (Удаляем сверху из массива PATH два элемента.) Идти к шагу А3.

А5. Пометить как «рассмотренное». Если уже помечена как «рассмотренная» уже встречалась в некотором кратчайшем добавляющем пути, либо такого пути, содержащего не существует), то идти к шагу АЗ. Иначе пометить как «рассмотренную» и положить помещается сверху в массив PATH).

А6. Если — свободная вершина по отношению к то идти к шагу Иначе положить у-напарник вершины и идти к шагу А2.

А7. Добавляющий путь Р по отношению к Мнайден. Вершинами Р являются вершины PATH (1), PATH (2), PATH (POINT). Положить — новое паросочетание после расширения.) Положить и идти к шагу А1.

А8. (Все кратчайшие не пересекающиеся по вершинам пути в графе G выделены и соответствующие расширения осуществлены.) Конец процедуры.

Можно показать, что сложность выполнения PROC-AUGMENT равна О Так как в любой фазе построения графа G выполнение PROC-AUGMENT производится только один раз и по теореме 15.5 существует фаз, то отсюда следует, что сложность алгоритма 15.6 равна

В качестве примера рассмотрим граф G, изображенный на рис. 15.13, а, где пунктирные линии обозначают ребра паросочетания М. В этом графе нижние вершины пронумерованы числами 1—12, а верхние вершины — числами

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

Множества получаемые в результате работы алгоритма, есть множества

Тогда Так как вершины 6 и 8 множества не являются свободными нижними вершинами, то они не входят в граф G. Граф G для паросочетания М изображен на рис. 15.13, б. Отметим, что существует только два добавляющих пути в графе G. Однако они не являются не пересекающимися по вершинам. Поэтому PROC-AUGMENT получит только один добавляющий путь для фазы, которая начинается с паросочетания М. Если ребро

полученный добавляющий путь, то после расширения мы получим новое паросочетание, в котором вновь введенными ребрами являются (-6,5) и (-9,9). Ребро (5, —9), входящее в паросочетание, удаляется из него.

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

Авторы работы [15.38] разработали О (-алгоритм для максимального паросочетания в графе общего вида. Этот алгоритм использует метод, основанный на поисках в ширину и в глубину. При разработке этого алгоритма также использовались некоторые идеи, выдвинутые ранее [15.29, 15.36].

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