Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 47
Текст из файла (страница 47)
Найдем вершину цветкаЬ', смежнуюсо, в графе, который был до стягивания Ь'. Это не всегда просто, по- !О.В..Парооочетание в проиэвольном графе. Алгоритм 243 скольку вместо о, у нас могла быть другая вершина, полученная из цветка. При анализе эффективности алгоритма (см. доказательство теоремы 10.6) мы точно укажем, как производить этот поиск эффективно. После того как найдена такая вершина цветка Ь' (о, или о,; пусть, например, о,), находим единственный путь из основания цветка Ь' в вершину оо оканчивающийся ребром паросочетания (в нашем примере [оь, о„о,!).
Затем заменяем оь, в р этим путем, в результате чего получаем путь р'=-[ого, о„о„о„оь, о„о„о,!. Теперь нужно повторить тот же процесс для замены в р' вершины оь. На этот раз о, — вершина, соединенная с оь свободным ребром. Находим, что это ребро соответствует ребру [о„оа! в 6, Находим единственный путь внутри Ь из основания о,в о„оканчивающийся ребром паросочетания, именно [о„о„о,!.
Наконец, заменяем оь в р' этим путем, в результате чего получаем окончательный увеличивающий путь р"= — [ого, о„о„о„о„о,, о„о„о„о,!. Описанные выше идеи реализуются в процедуре УВЕЛИЧЕНИЕ, не показанной явно на рис. 1О.!3. Полный алгоритм представлен иа рис. 10.13. Теорема 10.6.
Алгоршпм, представленный на рис. 10.! 3, корректно находит лшксимпльное ппросочетпние в грггфе 6= (У, Е) за время О(!У[4) Доказательство. Алгоритм останавливается после неудачных попыток найти увеличивающие пути из всех свободных вершин графа 6. Учитывая теорему 10А, можно заключить, что в тот момент, когда производилась каждая такая попытка, не существовало увеличивающего пути из рассматриваемой вершины в исходном графе 6. Отсюда по теореме 10.5 не существует увеличивающего пути в 6, и, следовательно, по теореме 10.! текущее паросочетание оптимально.
Так как цикл с меткой этап выполняется не более !У! раз (по одному разу для каждой вершины), то для получения времеинбй оценки достаточно показать, что каждый этап можно выполнить за время 0([У!'). Построение вспомогательного орграфа можно выполнить за время 0 (!У[г) и за такое же время вычислить массив свободная. При каждом поиске будет не более !У! выполнений процедуры ЦВЕТОК, так как при каждом таком выполнении число вершин текущего графа уменьшается по крайней мере на два. Покажем теперь, что процедуру ЦВЕТОК можно выполнить за время 0([У[о).
Обратный просмотр по пометкам и нахождение самой последней общей вершины, очевидно, можно выполнить за время 0([У!л). Преобразование вспомогательного орграфа можно произвести за время 0([А!)=О(!Е!) — 0([У!г); новые значения массивов поыеткп и 9 могут быть вычислены за время 0([У!). Поэтому всю процедуру ЦВЕТОК можно выполнить за время 0([У!') Процедура УВЕЛИЧЕНИЕ выполняется не более одного раза при каждом поиске. При каждом ее выполнении может потребоваться 244 Гл. 10. Алгоритмы для задача а парасочеаганнн до 0(]р|) расширений цветков (вспомните обсуждение процедуры УВЕЛИЧЕНИЕ, перед теоремой). Каждое расширение сводится по существу к нахождению вершины иу данного цветка, связанной с ш АЛГОРИТМ ПОСТРОЕНИЯ НЕДВУДОЛЪНОГО ПАРОСОЧЕТАНИЯ Вход. Граф С=(Н, Е).
Выход. Максимальное паросочетание в С, представленное массивом напарник. Ьеа!п |ог ап чЕН до нанарник[ч[:= О, рассматрено[ч1:= О; этап: хчЛИе имеется и ЕН, для которого рассмоагрена[и] =.О и налар. ник] и) = О до Ьеа[п рассло~нрена[и): = 1, А: = аи| |ог ап ч Е Н йа свабадная[ч]:= О (соттеп1: ног троение вспомогательного орграфа) !ог ан [ч, хе[ЕЕ бо (соттепп повторить как для [ч, чг), так и для [чч, ч)) и налаРник[чг] =О апд хч Ф и |иеп свободнал[ч] . чг е1зе и нттрнак[п] ~ ч, О гьеп А:= А0((ч, нанарник[хч))); |ог ап ч ~Н г)о видна[ч]:= О О '= — (и»; нахгвтка[и[;= О; И свободная[и] Ф О |иеп УВЕЛИЧЕНИЕ(и), ао |о этап; (соинпеп|; задание начальных значений для поиска) м|П1е О Ф в бо Ьеа)п пусть ч — вершина из О.; (сопипепн Π— очередь) улалить ч пз О; |ог а|! непомеченных вершин чгЕН, таких, что (ч, и) ЕА до ! Ьеа|п 1 О:= О()(чг», наметка[и]: ч| видна[напарник[а]] .= 1; И свободная~а] Ф О тнеп УВЕЛИЧЕНИЕ(гч).
Со |о этап; И видна[чч] = 1 |иеп ЦВЕТОК(чд ] епд епд епб епд Рис. !О„|3. Алгоритм построения паросочетания в произвольном графе. в исходном графе. Это можно осуществить, просматривая все вер. шины, стянутые в 6 (и в гп, если гп — также цветок), и находя комбинацию, являющуюся ребром из Е. Первую часть можно выполнить за время О(']]г]а), начиная с каждой вершины и и находя цветок Ы, затем цвепчок]цеечлок(о]] и т. д. не более 0 (]]А]) раз, до тех пор, пока не придем соответственно к 6 или гп.
Вторую часть можно выполнить за время| 0(]Е]), проверяя для каждого ребра [и, н]сЕ, верно ли, что и стянуто в Ь и и стянуто в гп. Оставшуюся часть процедуры УВЕЛИЧЕНИЕ можно выполнить за время 0(]]г]) для 1О.о. Паросоиеаэание в проээовольном гра4е. Алгорнаэн 246 еи еа е оэ гээ еэе еээ л46 Гл. !О. Алгоритма длл задачи о пароеочетаиии каждого расширения цветка; следовательно, увеличение, производимое после каждого поиска, можно произвести за время О(1)г[е), (3 Пример 1О.1. Применим алгоритм, представленный на рис.
10.13, к графу, показанному вверху на стр, 245. Первые семь этапов тривиальны. Увеличивающие пути, состоящие из единственного ребра, моментально находятся, и в результате следующие ребра становятся ребрами паросочетания: Ьо ое1, Ь, о,1, Ь„о,1, Ь„ое), Ь„оге1, Ьио о„1, [ое„о„1. Полученное паросочетание приведено внизу на том же рисунке.
На следующем этапе выбираем свободную и не рассмотренную вершину о„и строим вспомогательный орграф относительно текущего парасочетания, Вершинами, для которых свободная[о) ~ О, будут вершины о„о„о„, о„и оьо о! и, "и оо Следующий рисунок иллюстрирует поиск из вершины о;, [дуга из и в и означает, что полгеткп [о1=-и; она прогпивоположпо дуге вспомогательного орграфа). 10.5. 11ороеоеетоние е ороиэеольном графе. Авгорити 247 из» О из На этом месте поиск прерывается, не дав никакого результата (т. е. не найден увеличивающий путь или цветок, и Я пусто). Поэтому вершина и„выбрасывается; мы никогда больше не будем начинать с нее поиск. Следующей не рассмотренной свободной вершиной является оим Поэтому мы начинаем поиск по орграфу из о„с целевыми вершинами (т. е. вершинами, для которых значение функции свободная отлично от нуля) о„ое, ом и о,е Удаляя о„из Я, вставляем в Я вершины о„, о„и оз„одновременно придавая элементам массива видна, соответствующим и„, о, и ого значение 1, поскольку напарники этих вершин помечаются.
Затем удаляем из (,> вершину о. При этом к (з добавляется о, и производится присвоение вадна1и,1="-!. Затем рассматривается вершина и,. Соответствующая ситуация выглядит там и!6 из С> = (ив и~з из и>1 На этом месте обнаруживаем, что видна(и,!=:-1; следовательно, о, — напарник некоторой вершины, уже являющейся внешней (о,), и цветок обнаружен.
Для нахождения всех вершин цветка проходим назад по массиву пометка одновременно из вершины о, и ее напарника о„. Первая общая вершина на этих обратных путях— оем поэтому о,„— основание цветка. Все вершины, встретившиеся на этих обратных путях, и их напарники образуют множество верхцин цветка. Припишем этому цветку новый индекс, изм заменим все Элементы массивов () и пометка, являющиеся вершинами цветка, 248 Гл. !О. Алгоритмы для задачи о аарооочетаиии па о и возобновим поиск. Модифицированный вспомогательный зв граф имеет такой внд: оз о, о„ Поиск продолжается начиная с состояния о|в о~з ез= ~о~в оп оз1 Далее из очереди удаляется ом и добавляется о„— - вершина, для которой свободная[о,„1г пм Ф О. е0.5.
Пауоеонетапие в пуоооюеопон гуаеуе. Алгоуотн оч г~о Увеличивающим путем в текущем графе будет путь р' — ]о„, напарник Ь„], опь свободнан Ь„Ц=-Ь,„, о„о„„о, 1. Чтобы заменить р' путем в исходном графе, просматриваем все ребра, инцидентиые о„и обнаруживаем, что ребро ]ооо о,] соответствует исходному ребру Ь„о,1 и, кроме того, путем, идущим из основания о,„в о„, оканчивающимся ребром паросочетаиия, является путь Ьоо о„ о„]. Поэтому заменяем о„ в р' на Ьет о„ о„! и получаем окончательный увеличивающий путь р=Ь,т о„о„о„, оои о„1, с помощью которого текущее паросочетаппе увеличивается, как показано пп рисунке. о> оп оы Далее обнаруживаем, что в графе С нет вершин, не входящих в паросочетание и не рассмотренных, и, следовательно, текущее паро- сочетание оптимально.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
