Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 45
Текст из файла (страница 45)
цветки 233 Дуги вспомогательного графа снова будут представлять основную информацию: дуга (о, и) будет обозначать, что и может быть следующей внешней вершиной после и на чередующемся пути, на котором и является внешней. Таким образом, увеличивающие пути соответствуют путям во вспомогательном графе из свободной вершины в некоторую целевую вершину (т.
е. вершину о, для которой свободнаяЫФО) точно так же, как в двудольном случае. Однако общая задача о паросочетании оказывается существенно сложнее, поскольку обратного соответствия может яе бьипь, Иначе говоря, во вспомогательном графе могут быть пути, ведущие из свободных вершин в целевые вершины, но не соответствующие увеличивающим путям относительно текущего паросочетания. Покажем это на примере. Рассмотрим граф 6, приведекный на рис. 10.5(а), и выделенное в нем паросочетание М. Здесь М не максимально, поскольку в 0 существует увеличивающий путь относительно М, а именно р=[о„о„о„о„о„о„о„о,, о„о„). Естественно, р соответствует пути р'=(о,, о„о„о„о,) во вспомогательном орграфе относительно М, приведенном на рис. 10.5(б).
Тем не менее во вспомогательном орграфе сущес1вуют пути, которые не соответствуют правильным увеличивающим путям. Рассмотрим, например, путь д'=(о„о„о„о„о„о,). В графе О нет увеличивающего пути, в котором последовательность внешних вершин совпадала бы сд'. Если мы воспользуемся соответствием (и„и„..., ие)е-» е-е(ио напарник(и,), и„..., напарник(ин), ию свободная(ин)), с помощью которого нам удавалось находить увеличивающий путь в двудольиом случае, то получим маршрут д=Ь„о„о„о„о„, о„ о„о,, о„о„, о„о„). Естественно, д не является увеличивающим путем; на самом деле это вообще не путь. Некоторые вершины и ребра в нем повторяются, например ребра паросочетания !о,, о,) и Ь„, о,). Эти повторения не отражены в о', так как каждый раз различные каппы ребер используются в качестве «внешних» вершки. Плюс ко всему М~+Я (где 1е — множество ребер маршрута о) не является паросочетанием.
Так как наш метод использования вспомогательных орграфов успешно работает для двудольных графов и единственной чертой, отличающей двудольные графы, является отсутствие циклов нечетной длины (вспомните предложение 1.1), можно предположить, что плохая ситуация в общем случае связана именно с наличием циклов нечетной длины. И это действительно так. До появления цикла нечетной длины С=-(ое, о„о„о,) (см. рис. 10.5) о является абсолютно правильным чередующимся путем.
Затем о замыкает этот цикл и начинает «накладываться» на себя, что приводит к отмеченным выше бедственным последствиям. Не все циклы нечетной длины могут порождать такую нежелательную ситуацию. Например, цикл из девяти вершин в графе, представленном на рис. !0,6(а), не может помешать алгоритму, использующему вспомогательный орграф, Интуитивные соображе- Гл.
10. Алгориммы длл задачи о оарогочетаиии оа и~ (а) им иге-ц им-з ич,( ии и~ и, иЗ и2/ — 3 ил-е (б) ам 1 иге из -! иа 4 (в) Рис. !ом. ния здесь следующие; так как данный цикл слишком «разрежен» относительно ребер паросочетания, то увеличивающий путь не может пройти по нему и наложиться на себя. Подозрительными циклами нечетной длины являются те, в которых плотность ребер паросочетания достигает максимальной величины; т. е.
циклы с 2й+1 вершинами, содержащие й ребер паросочетания (рис. 10.6(б)). Такие циклы называются цветками и играют важную роль в теории !ОА. Паросокетание в нроиевовеном графе. Цветки 235 паросочетаний, Отметим, что, подобно большинству терминов, связанных с паросочетаниями, цветки определяются только по отношению к некоторому фиксированному паросочетанию. Таким образом, мы поняли, почему здесь не годится метод вспомогательных орграфов: из-за цветков. Если в графе нет цветков относительно текущего паросочетания, тогда он эффективно двудолен (даже несмотря на то, что может содержать циклы нечетной длины, не являющиеся цветками, подобно графу на рис.
10.6(а)), н поиск увеличивающих путей можно проводить так же, как в двчдольном случае. Следовательно, нам нужно модифицировать наш алгоритм так, чтобы (1) он мог чувствовать наличие цветков и (2) находить правильные увеличивающие пути даже при наличии цветков. Для упрощения алгоритма будем производить поиск увеличивающих путей из каждой свободной вершины по очереди, а не одновременно нз всех свободных вершин, как мы делали в алгоритме поиска паросочетания в двудольном графе. Обнаружить наличие цветков не очень трудно.
Цветок становится существенным для нашего алгоритма, когда он впервые обнаруживается алгоритмом, т. е. когда все его вершины оказываются либо внешними, либо напарниками внешних вершин. Зта ситуация изображена на рис. 10.6(в) для цветка, представленного на рис. 10.6(б). В этот момент мы впервые замечаем необычное явление.
Следующая вершина в процессе нашего поиска, а именно иы (см. пунктирную дугу на рис. !0.6(в)), оказывается напарником вершины ц, „которая уже была внешней. Зто означает, что мы пытаемся использовать ребро паросочетания (иы, и„;) дважды, и наличие цветка таким образом установлено. Ненамного труднее действительно найспи этот цветок. Мы возвращаемся назад из им и и;,, находя два пути, ведущие из свободной вершины и в этн вершины.
Находим самую последнюю внешнюю вершину, общую для этих путей. Зта вершина (ц, в нашем примере на рис. !0.6(б) и !0.6(в)) является основанием цветка, т. е. единственной вершиной цветка, не объединенной в пару ни с какой другой вершиной цветка. Тогда цветок состоит из всех внешних вершин на отрезках путей от ц, до им и и„., вместе с напарниками всех этих вершин, исключая ие, Проведенный анализ обеспечивает одно из двух указанных выше расширений алгоритма вспомогательных орграфов, необходимых для того, чтобы алгоритм работал для произвольных, недвудольных графов: обнаружение цветков. Остается еще понять, что дслать с обнаруженным цветком для того, чтобы продолжить поиск правильных увеличивающих путей. Для этого используется поразительно простая идея — избавиться от цветка, стягивая его, т.
е. заменяя его одной вершиной. Формализуем понятие стягивания. Если Ь— цветок в графе 6=(1', Е) относительно паросочетания сг(, то граф, полученный из 6 стягиванием Ь, имеет вид 6УЬ=-(ИЬ, Е/Ь), где У/Ь получается из У выбрасыванием всех вершин цветка Ь и добавлением новой вершины ое вместо Ь; ЕуЬ получается из Е выбрасы- Гл. !О. Алгорааваы для задачи о аароеочелванаи 236 ванием всех ребер, у которых обе концевые вершины лежат в Ь, п заменой каждого ребра (о, и), такого, что и лежит в Ь, а и не лежит в Ь, на ребро (о, оь). В качестве примера на рис.
!0.7(б) приведен граф бУЬ для графа вл и цветка Ь, представленных на рис, 10.7(а). Естественно, для того чтобы стягивание являлось ь)о ов ов оз ав (а) о 9 а~а в от ов а„ (в) (б) Рис. !0.7. допустимой операцией в процессе нашего поиска увеличивающих путей, необходимо показать, что при стягивании цветка в нашем графе не добавляются и не пропадают увеличивающие пути. Лемма !0.3. Пусть во время поиска увеличивающего пути из свободной вершины и в графе 6 относительно паросочетания М обнарузкивается цветок Ь. Тогда суи!ествует чередующийся путь из ив любую вершину цветка Ь, оканчивающийся ребром паросочетания.
Доказательство. Так как цветок Ь был обнаружен при поиске из и, то существует чередующийся путь из и до основания цветка Ь, как показано на рис. 10.8. Тогда вершина о цветка Ь достижима из и по двум чередующимся путям (рис. 10.8)„Один из них обязан оканчиваться ребром паросочетания. 237 )0.4. Парогочетанив в произвольном графе.
Цвеглки Пусть 6 — граф, М вЂ” паросочетание и Ь вЂ” цветок в графе 6 относительно М. Тогда М)Ь вЂ” паросочетание, получающееся из М, если удалить все ребра паросочетания, входящие в Ь, и заменить Рис. !О.В. любое ребро паросочетания вида (о, и1, где и — вершина цветка Ь, на ребро (о, о,). Теорема 10.4. Пусть при поиске увеличившощего пути из вершины и графа 6 относительно паросочетанил М обнаружен цветок Ь. Тогда существует увеличивиющий путь из вершины и в графе 6 относительно М в том и только гном случае, если существует увеличившощий путь из и (оь, если и — основание цветка Ь) в графе 6!Ь относительно М)Ь, Доюззательство.
Докажем сначала достапючность. Предположим, что существует увеличивающий путь р из вершины и в 6/Ь относительно МУЬ. Если р не проходит через ое, то р сам является увеличивающим путем в 6. Если р проходит через оь, можно записать р=(и, р', гв, ою гв', р" Р), где р' и р" — некоторые пути. Одно из ребер, (ш, пь) или Ы, о„1, входит в паросочетание. Допустим, что ребро (гп, оь1 входит в паросочетание (второй случай аналогичен).
Тогда (ьв, и,1Е М и (из', ит)ЕŠ— М для основания и, и некоторой другой вершины ит цветка Ь (рис. 10.9). Отсюда следует, что путь (и, р', гв, и„р'", иь ш'„р ), где рьы — путь из и, в им оканчивающийся ребром паросочетания (пустой путь, если и,=из), является увеличивающим путем из вершины и в графе 6. Если и=о,, рассуждения совершенно аналогичны. Докажем теперь необходимость. Предположим, что существует увеличивающий путь р из и в графе 6 относительно М. Опять ') Мы используем выражения вида (и, р, ы, р', о), где и, ю и о — вершины, для обозначения пути, первая часть которого (в данном случае) есть путь р с концевы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
