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

В этом разделе мы рассмотрим задачу построения максимального паросочетания в графе. Сначала мы обсудим основной подход к построению такого паросочетания, предложенный в работе [15.28].

Затем опишем алгоритм Габова [15.29], который является эффективной реализацией подхода Эдмондса.

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

15.4.1. Подход Эдмондса

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

Найдем добавляющий путь Р по отношению к М. Получим паросочетание , которое имеет на одно ребро больше, чем М. Находим добавляющий путь по отношению к этому новому паросочетанию и т. д. Повторяем эту операцию до тех пор, пока мы не получим паросочетания, по отношению к которому не существует добавляющих путей. Тогда по теореме Бержа такое паросочетание максимально. Таким образом, задача в основном сводится к эффективному нахождению добавляющего пути по отношению к данному паросочетанию. Наиболее важной идеей в данном контексте является понятие «цветок», введенное Эдмондсом, которое описывается ниже.

Рис. 15.10.

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

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

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

Рис. 15.11. Образование «цветка».

Другими словами, предположим, что «1 не смежна ни с одной из выбранных вершин. Если — такие вершины, смежные с что для любых i и то их напарники также присоединяются к выбранной группе вершин. Если мы при рассмотрении вершины в выбранной группе обнаружим, что она смежна с другой вершиной, уже принадлежащей выбранной группе, то это означает, что получен нечетный цикл, т. е. цикл нечетной длины. Этот цикл, являющийся замкнутым чередующимся путем нечетной длины, называется «цветком». Например, на рис. 15.11 добавление ребра создает «цветок» . До добавления этого ребра выбранная группа состоит из вершин . Если образуется «цветок», то вершины также присоединяются к выбранной группе, поскольку мы можем найти чередующийся путь четной длины из вершины и к этим вершинам. Например, на рис. 15.11 — чередующийся путь четной длины к вершине Как только образовался «цветок», мы заключаем, что все вершины этого «цветка» присоединяются к выбранной группе.

Если в алгоритме Эдмондса образуется «цветок», то все его вершины заменяются одной. Новая вершина называется псевдовершиной.

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

Сжатие и восстановление «цветков», требуемые в алгоритме Эдмондса, могут привести к сложности выполнения алгоритма где п — число вершин в графе.

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

15.4.2. Метод Габова

Вначале мы обсудим главную стратегию и определим различные массивы, используемые в алгоритме Габова.

Пусть дан граф, имеющий вершин и ребер. Алгоритм начинает свою работу с определения нумерации вершин и ребер графа. Вершины нумеруются числами от 1 до , а ребра — числами . Номер ребра обозначается через . В алгоритме используется номинальная вершина, отмеченная числом 0. В массиве END элементы пронумерованы от до Для каждого ребра массива END имеется два элемента, расположенные последовательно и содержащие номера вершин, инцидентных этому ребру. Таким образом, если ребро имеет номер k (где для некоторого ), то , т. e. по данному номеру ребра с помощью этого массива можно легко определить вершины, инцидентные этому ребру.

Алгоритм Габова строит множество паросочетаний, начиная с начального, которое может быть пустым. Он завершается получением максимального паросочетания. Паросочетание хранится в массиве МАТЕ. Этот массив имеет по одному элементу для каждой вершины. Ребро входит в паросочетание, если MATE

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

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

Начальная метка. Начальная вершина и имеет начальную метку. В этом случае LABEL устанавливается равным 0. Чередующийся путь

Метка вершины. Если LABEL , где то говорят, что v имеет метку вершины. В этом случае у является внешней вершиной и элемент LABEL равен номеру другой внешней вершины. Путь определяется как

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

LABEL , когда у не является внешней вершиной. Вначале, когда все вершины являются невнешними, мы полагаем, что значения LABEL для всех вершин равны —1.

Алгоритм использует также массив FIRST. Если у — внешняя вершина, то FIRST — первая невнешняя вершина в Если путь не содержит невнешних вершин, то FIRST полагается равным 0. FIRST если у — невнешняя вершина.

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

Алгоритм Габова (как он представлен ниже) состоит из трех процедур: PROC-EDMONDS, PROC-LABEL и PROC-REMATCH.

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

При обнаружении добавляющего пути (шаг ЕЗ в алгоритме 15.5) вызывается PROC-REMATCH. Эта процедура вычисляет новое паросочетание, которое имеет на одно ребро больше текущего паросочетания.

Если при рассмотрении ребра образуется «цветок» (шаг ), то вызывается PROC-LABEL. В этом случае вершины х и у являются внешними. PROC-LABEL выполняет следующие операции:

1. Значением переменной JOIN является первая невнешняя вершина, которая принадлежит как так и

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

3. После этого JOIN — первая невнешняя вершина как в Р так и в Поэтому элементы массива FIRST, соответствующие вершинам, предшествующим JOIN в или , полагаются равными JOIN.

Опишем алгоритм Габова. Комментарии и объяснения, соответствующие каждому шагу, приводятся в скобках.

Алгоритм 15.5. Максимальное паросочетание (Габов).

PROC-EDMONDS.

ЕО. (Инициализация.) Пусть G — данный граф. Пронумеровать вершины графа G числами от 1 до , а ребра — числами Создать номинальную вершину 0. Для положить LABEL (Вначале все вершины являются невнешними и ненасыщенными.) Положить .

Е1. Нахождение ненасыщенной вершины.) Положить Если то HALT и МАТЕ содержит максимальное паросочетание. Иначе если и — насыщенная вершина, то повторить шаг Если и — ненасыщенная вершина, то добавить и в массив OUTER. Положить LABEL (Помечаем вершину и начальной меткой и начинаем новый поиск.)

Е2. (Выбор ребра.) Выбрать ребро — внешняя вершина), которое еще не рассматривалось в х.

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

Е3. (Обнаружить добавляющий путь.) Если у не входит в паросочетание и , то выполнить PROC-REMATCH и идти к шагу

Е4. (Образовать «цветок».) Если у — внешняя вершина, то выполнить PROC-LABEL и идти к шагу Е2.

Е5. (Пометить вершину.) Положить . Если v — внешняя вершина, то идти к шагу . Если v — невнешняя вершина, то положить и добавить вершину v к массиву OUTER. (Вершина у встречается в этом поиске впервые; ее напарник v является новой внешней вершиной. Этот факт отмечается в массиве OUTER.) Идти к шагу Е6.

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

Е7. (Прекратить поиск.) Положить LABEL для Затем идти к шагу (Все вершины полагаются не внешними для следующего шага.) PROC-LABEL.

L0. (Инициализация. Положить ) Если то идти к шагу (Нет ни одной невнешней вершины в «цветке».) Иначе пометить вершины и s. (Шаги определяют JOIN при попеременном движении вдоль путей ) Метки приписываются невнешним вершинам этих путей. Это выполняется посредством помещения в LABEL отрицательного номера ребра, т. е. LABEL Таким образом, при каждом вызове процедуры PROC-LABEL используются различные значения меток.)

L1. (Переключение путей.) Если то поменять местами и s ( — не внешняя помеченная вершина в ) попеременно.)

L2. (Взять не внешнюю вершину.) Положить ( полагается равной следующей не внешней вершине в ) или Если не помечена, то пометить и идти к шагу Иначе положить (Мы определили JOIN.) Идти к шагу L3.

L3. (Пометить вершины в ) т. е. всем невнешним вершинам между и JOIN или у и JOIN будут приписаны метки ребра, а именно Положить и выполнить

L4. Затем положить и выполнить шаг Затем идти к шагу L5.

L4. (Пометить не внешнюю вершину и.) Если то положить LABEL и добавить v в массив OUTER. Затем положить (LABEL (МАТЕ ). (Получаем следующую не внешнюю вершину.) Повторить шаг Иначе (т. е. и, следовательно, мы должны приписать метки ребер всем невнешним вершинам в рассматриваемом пути) продолжить действия, определенные в шаге (т. е. возвратиться к шагу )

L5. (Изменить FIRST.) Для каждой внешней вершины i, если FIRST — внешняя вершина, положить FIRST (т. е. JOIN — новая первая не внешняя вершина в ).

L6. (Расстановка реберных меток завершается.) Конец процедуры. PROC-REMATCH.

R0. (Получить добавляющий путь.) Вычислить как описано ниже:

1. Если имеет реберную метку то вычислить Если принадлежит то

Иначе

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

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

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

Рис. 15.12.

Эдмондс [15.28] показал, что мы можем игнорировать венгерский подграф И после выделения и модифицировать алгоритм 15.5, изменяя шаг следующим образом:

Е2. (Выбрать ребро.) Выбрать ребро... Если такое ребро не существует, то идти к шагу

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

Вопросы, касающиеся сложности и корректности алгоритма 15.5

обсуждаются в работе [15.29]. Проиллюстрируем работу алгоритма Габова.

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

Начальной вершиной является вершина 10. После завершения поиска во внешних вершинах 10, 16, 13, 11 и 2 граф поиска будет таким, как показано на рис. 15.12, б. Элементы массивов LABEL и FIRST на этом этапе приведены в табл. 15.2. Массив OUTER содержит вершины 10, 16, 13, 11,2, 12, 6 и 9 в указанном порядке.

Таблица 15.2

Таблица 15.3

Когда мы осуществляем поиск в вершине 12, то рассматриваем ребро (12.6) и получаем «цветок» (13, 5, 12, 6, 8, 13). Элементы массивов LABEL и FIRST изменяются следующим образом: LABEL . Вершины 5 и 8 помещаются в массив OUTER. Затем, когда мы осуществляем поиск в вершине 6, мы рассматриваем ребро (6, 5), которое образует другой «цветок» (6, 5, 12, 6). Но все вершины этого «цветка» внешние, и поэтому никаких изменений не производится.

Затем мы осуществляем поиск в вершине 9. При рассмотрении ребра (9, 5) образуется «цветок» (9, 7, 11, 4, 16, 1, 13, 8, 6, 12, 5, 9). Вновь изменяем значения элементов массивов LABEL и FIRST для некоторых вершин. Полученные значения приведены в табл. 15.3.

В этот момент массив OUTER содержит вершины 10, 16, 13, 11, 2, 12, 6, 9, 5, 8, 1, 7 и 4 в указанном порядке.

Во всех вершинах массива OUTER вплоть до 9 поиск уже был произведен. Поэтому он продолжается в оставшихся вершинах. Поиск в вершинах 5 и 8 не добавляет каких-либо новых вершин в массив OUTER. При поиске в вершине 1 мы рассматриваем ребро (1, 15) и обнаруживаем, что вершина 15 ненасыщена. Получен добавляющий путь. Этим добавляющим путем является путь

Используем процедуру, составляющую шаг для вычисления . Вершина 1 имеет метку ребра Поэтому для вычисления нам необходимо иметь пути Далее, так как вершина 5 имеет метку ребра то нам необходимо иметь пути Р (12) и для вычисления пути Вершина 12 имеет метку вершины. Поэтому

Аналогично

Так как вершина 5 лежит на пути Р (12), то . Мы обнаруживаем, что вершина 1 принадлежит пути Р (5). Поэтому .

Таким образом, добавляющий путь имеет вид .

После дополнения мы получаем новое паросочетание, состоящее из ребер (15, 1), (13, 8), (6, 12), (5, 9), (7, 11), (4, 16), (3, 10) и (14,2). Так как все вершины графа насыщены в этом паросочетании, то это — максимальное паросочетание. (Фактически это совершенное паросочетание.)

Эдмондс [15.33] и Габов [15.34] рассмотрели эффективный алгоритм для задачи выделения взвешенного паросочетания. Лоулер [15.9] обсуждает детально паросочетание и связанные с ним задачи.