Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 46
Текст из файла (страница 46)
ми вершинами и н ю, а вторая часть — путь р' с концевыми вершинами ы и и. Вы. Г ажение (р, в) обозначает конкатенацию двух путей без указания концевых точек. ели р — путь, то ря обозначает обратный путь. 2зв Гл. /О. Ллгоратмы для задачи о аарооочетанаа если р не проходит ни через одну вершину цветка Ь, то все в порядке.
Если же это не так, то возможны два случая. Случай /, Пусть р входит в цветок Ь через основание и, по ребру паросочетания (рис. 10,!0(а)). Пусть г0 — последняя вершина цветка Ь в этом пути. Если из — — и,, то все в порядке, поскольку после замены ич на о, путь р будет также увеличивающим путем в 6/Ь. оо и а, Рис.
!0.9. В противном случае р ---1и, р', и,, р", иь ш, р"'! и !и, ш)(М. Тогда (и, р', в, го, р"'! — увеличивающий путь в 6/Ь. Случай 2. Пусть р входит в цветок Ь по свободному ребру. Рассмотрим два подслучая, Поослучий (а). Пусть р выходит из цветка Ь через его основание по ребру паросочетания. Этот случай аналогичен случаю 1.
Подслрчий (б). Пусть теперь р выходит из цветка Ь по свободному ребру. Тогда р — — !и, р', и,, р", иь ш, р'"! (Рис. 10.10(б)). По лемме 10.3 существует чередующийся путь ч/ из вершины и в основание ио цветка Ь, оканчивающийся ребром паросочетания. Необходимо рассмотреть три возможности. 1.
Предположим вначале, что р"' и д не пересекаются. Тогда !и, ч/, в,, ги, р"'! — увеличивающий путь. 2. Предположим теперь, что р"' и ч/ пересекаются (рис. 10.10(в)). Тогда й=(и, г/', х, ч/", ич! и р"'=(р'", х, р"'), где р"-' не имеет общих вершин с г/. В этом случае путь !и, р', оь, г/"л, х, р"'! является увеличивающим путем в предположении, что ч/" и р' не имеют общих вершин. 3. Этот случай совпадает с (2) за исключением того, что теперь р' и; ч/" пересекаются (рис. !0.10(г) и 10.10(д)). Пусть у — последняя из вершин пути а", лежащих либо на р', либо на р'".
Если д лежит на р"', то для построения увеличивающего пути в 6/Ь используем р до вершины оь, затем д в обратном направлении до д и затем р'" до конца (рис, !О.!0(г)). Если у лежит на р', тогда используем р' ао вершины у, затем д до оа и затем р'" до конца (рис. 10.10(д)), 10.4. Пароеонетание в произвольном графе. Цветки 239 (а) (б) (о) , 5 Рис. (0.10. 240 Гл. 10, Алгоритмы для вадача о аароеочетапаа ~ел Паросочетаиме в произвольном графе. емлгорлтм В этом параграфе будет приведен алгоритм со сложностью О (!)е!') для задачи о паросочетании.
Этот алгоритм (см, рис. 10.13)— это тот же алгоритм, который был использован в двудольном случае, но с некоторыми особенностями, необходимыми для того, чтобы справиться с цветками. Алгоритм начинает работу с пустого паросочетания и многократно выбирает свободную вершину для поиска увеличивающего пути из нее. Для простоты будем искать увеличивающие пути из каждой свободной вершины по очереди, а не из всех свободных вершин сразу, как мы делали в двудольном случае. При поиске опять будет использоваться вспомогательный орграф. Предположим, что на некотором этапе нам не удалось найти увеличивающий путь из свободной вершины и.
Очевидно, и ничем не может нам помочь на этом этапе. Следующая теорема утверждает, что и также не следует выбирать в качестве начальной точки в нашем поиске на всех последующих этапах, Теорема 10,5. Пусть в графе 6 не существует увеличивающего пути, начинающегося из свободной вершины и, относительно парвсв. четания М. Пусть р — увеличивающий путь, концами которого являются две другие свободные вершины и и ш. Тогда также не существует увеличивающего пути из и относительно М(+)Р.
Доказательство. Предположим, что существует увеличивающий путь а из и относительно М~+~Р. Если д не имеет оощих вершин с р, то увеличение с помощью р не изменяет ничего, связанного с д, и, следовательно, путь д был увеличивающим путем из и до увеличения, что противоречит условию теоремы. Пусть теперь д=-(и,==и, и„..., и,= —.и'), и пусть и; — первая вершина на пути д, принадлежащая также путн р (рис. 10.11). Одна из двух частей, на которые ив делит р, должна оканчиваться в вершине ие ребром из М; эта часть вместе с частью пути д до вершины еб образует увеличивающий путь из и относительно М, что противоречит условию теоремы. Следствие. Если на некотором этапе нет увеличиваюи(его пути из вершины и, тв увеличивающего пути из втой вершины и не будет никогда.
Доказательство. Легко показать индукцией по й с использованием теоремы !0.5, что с того момента, когда нам не удалось найти увеличивающий путь из и, после любых и увеличений также не будет увеличивающего пути из и. (й 10,5. Поросочгтоног в произвольном графе. Алгоромм 24! Следовательно, если хотя бы раз поиск увеличивающего пути из вершины и не дал результата, то и никогда не будет в дальнейшем рассматриваться алгоритмом в качестве потенциальной начальной вершины увеличивающего пути. В нашем алгоритме это обеспечивается хранением массива рассмотрена, вначале являющегося нулевым.
Если вершина и используется в качестве начальной вершины в процессе поиска, полагаем рассмотрена(а1=-1, указывая этим, что и никогда не будет больше рассматриваться. Н Как и в двудольном случае, основную помощь при осуществлении поиска нам будет оказывать вспомогаг1 1 тельный орграф ()1, Л). Кро- О-~ ме того, снова будет исполь. зоваться массив свободная для выделения целевых вершин — т. е. вершин, смежных 1 со свободными вершинами, отличными от рассматриваемой.
Чтобы была возможность обнаруживать цветки, ! используется массив видна с 1 1)1~ элементами, первоначально нулевыми, где видна(п1=! означает, что о — напарник некоторой внешней вершины' Рке. !О.!!. доказательство теоремы !0.5 если в в процессепоиска ока- Жирными линиями выделены ребра кз жется внешней вершиной, то М ЮР. оба конца ребра (о, напарник (оП являются внешними и, следовательно, цветок обнаружен.
Как только обнаруживается первый цветок, он стягивается. Согласно теореме !0.4, это допустимая операция, так как при ее выполнении остаются увеличивающие пути из рассматриваемой вершины. Этому текущему цветку присваивается некоторое имя Ь вЂ” например, очередное целое число начиная с ~1Ч+1, поскольку первые ~)11 целых чисел использованы в качестве индексов вершин из и текущий граф превращается из 0 в ОЪ (рис. 10.7(б)). После этого мы можем обнаружить в процессе поиска другой цветок Ь' (рис. !0.7(б)). Стягивая его, получим в качестве текущего гоафл б/ЫЬ' (рис. 10.7(в)) и т, д.
После каждого обнаружения цветка Ь мы должны записать некоторую полезную информацию (эффективно стянуть Ь). Это выполняется с помощью процедуры ЦВЕТОК, использованной на рис. 10.13 (явно не приведена). Процедура ЦВЕТОК проделывает следующее. 1. Находит все вершины цветка Ь обратным просмотром с ис- 242 Гл. 1О Алгоритмог длл эадани о аарогонгтании пользованием массива полгегпкп до тех пор, пока не встретится первая общая вершина на рассматриваемых двух путях — основание цветка Ь (рис.
10.12). Вершинами Ь являются в точности вершины зтих двух путей и их напарники. Мы отмечаем тот факт, что о принадлежит цветку 6, положив цвегпок(о)=6 (заметим, что вершина о сама может быть получена из цветка). Мы также записываем для дальнейших ссылок основание цветка Ь и точный циклический порядок, в котором появляются вершины 6. Рис. 10.12 Идентифицировав все вершины пветка Ь, нужно проверить, существует ли среди них такая вершина и,, что свободная(и,]чьО. Если существует, то нужно увеличивать паросочетание из оо, как объяснялось в нескольких предыдущих параграфах. 2. Заменяем каждое вхождение вершины х цветка Ь во вспомогательном графе А, очереди Я и массиве полгегпка новой вершиной оо.
Это соответствует «стягиванию» вершин цветка 6 в одну вершину оы Процедура поиска, обнаружения и стягивания цветков продал. жается до тех пор, пока в текущем графе не будет найден увеличи. вающий путь из вершины и (или из о„где оо — самый последний стянутый цветок, содержащий и) нлн не окажется, что такого пути или еще одного цветка в процессе поиска по вспомогательному гра. фу найти нельзя.
Если в текущем графе обнаруживается увеличивающий путь р, то нужно построить по нему увеличивающий путь в исходном графе О. Это может оказаться нетривиальным, так как р может содержать несколько вершин, полученных из цветков, и, следовательно, его нельзя использовать для увеличения в том виде, как он есть. Рассмотрим, например, увеличивающий путь р=(ого, о„о„о„ого о,) на рис, 10 7(в).
Для нахождения пор увеличивающего пути в исходном графе можно несколько раз применить конструкцию из доказательства теоремы 1ОА (достаточность), которая устанавливает существование такого пути. Проиллюстрируем простой принцип такого построения на примере из рнс. 10.7. Путь р=[ооп о„о„о„ о,„о,) содержит одну вершину о„, полученную из цветка. Найдем в пути вершину, соседнюю с оо„соединенную с ом свободным ребром (в нашем примере о,).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
