Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 43
Текст из файла (страница 43)
Обе задачи вызвали большой интерес исследователей в последние два десятилетия. Они легко формулируются, апеллируют к интуиции и имеют много пРиложений Кроме того, имеются некоторые очень интересные алгоритмы, эффективно решающие эти задачи. Эти алгоритмы можно рассматривать как дальнейшие примеры использования идеи увеличения, знакомой нам по решениям задачи о максимальном потоке, обсуждавшимся в гл. б н9. Однако в случае задачи о паросочетании эффективное обнаружение и выполнение увеличений может оказаться непростым делом. Как в невзвешенном, так и во взвешенном вариантах задачи о паросочетании все эти вопРосы существенно упрощакзтся, если рассматриваемый граф является двудо.гьным В этой и следующей главах мы приведем и проанализируем алгоритмы для задач о паросочетанни и взвешенном паросочетаннн В обеих задачах вначале будет рассматриваться двудольный случай, поскольку этот случай — значительно более простой по структуре — помогает проиллюстрировать основные идеи, используемые при решении общей задачи.
10.1 Задача о паресечетании Подмножество М ребер графа 6=(г', Е) называется паросочетонием, если никакие два ребра из М не имеют общей вершины. Например, в графе, представленном на рис. !0.1, множества М, (Ь„о,1, Ь„о,1, Ь„, о,1,!о„о„)) (выделено на рис. !О.! жирными линиями) н М2 — (1оь ог1, !ом о,1, Ь,, о,), 1о„, о,), Ь„оы1) являются паросочетапиями.
При этом М, — максимальное паросочетание, 'поскольку, очевидно, паросочетание в 6 не может иметь больше, чем 1)гР2 =5 ребер. Задача о паросочетании состоит в нахождении в данном графе 6=('г', Е) максимального паросочетания М. Если мощность паросочетания равна ~1Р)у2 1, наибольшему возможному 224 Гм 10. Алгаров<ми длл задача о парасачеманпи значению в графе с [[<! вершинами, то паросочетание называется полныл<, или совершенным.
Рассмотрим граф 6 вместе с фиксированным паросочетанием М в 6. Ребра, входящие в М, называются ребрами паросочетания; остальные ребра называются свободными. Если [о, и) — ребро паросочетания, то и называется напарником о. Вершины, не инцидентные никакому ребру паросочетания, называются свободно<ми;остальные вершины обьединены в пары. Путь р=[и„и„..., ид1 называется чередующимся, если ребра [и,, и,1, [из ич! [иту Ю4 и< т а<а ат Рвс. )О.1. им[,... свободны, в то время как ребра [и„ив[, [и„и,[,, [ию, и,,[,... являются ребрами паросочетания. Вершины, стоящие на нечетных местах в некотором чередующемся пути, начинающемся со свободной вершины, называются внешними Вершины, стоящие на четных местах, называются внутренними ).[ля графа 6 и паросочетания М„представленных на рис. 1О.1, пути р<=[о„ом о„о„ о„о,1 и р,=[о„о4, о„о„о„о„о,е, о,! являются чередующимися.
Из существования этих чередующихся путей следует, что вершины о„о,, о, и о„о,, о„являются внешними, так как каждая из них стоит на нечетном месте в одном из этих путей и вершина о, свободна. Это не все внешние вершины графа 6 относительно М,: о„ и о, тоже являются внешними, поскольку рт=[о„о„о,! также чередую<цийся путь. Чередующийся путь р=[и„и„..., и„[ называется увеличивающим, если обе вершины и, и иь свободны.
На рис. 10.! путь ре=[о„о„о„о„о„о„ото, о,!является увеличиваю. щим. Большое значение увеличивающих путей для задачи о паросочетании вытекает из следующего факта. Лемма 10.1. Пусть Р— множество ребер увеличивающего путь р = [и,, и,, и,„[ в графе 6 относительно паросочетания М. Тоед< М' МЯР<1 — паросочетание мощности [М!+1. '] Если 5, Т вЂ” множества, то ВКЗТ обовивчвет симметрическую равно<по 3 в Т, определяемую равевствов 3<а)Т.= (Ю вЂ” Т) Ц [Т вЂ” ь). !О.!. Задача о парссвчетавви Доказательство. Покажем вначале, что МфР— паросочетание, т. е. никакие два ребра из МЯР не имеют общей вершины в 6.
Допустим, что два ребра е, е' из М(т)Р инцидентны одной и той же вершине. Так как МЯР= (М вЂ” Р) () (Р— М), то возможны три случая: 1) е, е'ЕМ вЂ” Р; 2) е, е'РР— М; 3) АМ вЂ” Р, е'РР— М. В первом случае получаем, что два ребра в М имеют общую вершину — противоречие. Во втором случае заметим, что ребра в Р— М имеют вид [из „и„), и, следовательно, никакие два из них не могут быть инцидентны одной и той же вершине. В третьем случае предположим, что ребро е'=[им „и„1 из Р— М имеет общую вершину с ребром еЕМ вЂ” Р. Без потери общности можно считать, что эта вершина им. Но и,! — вершина ребра е"=[ими и„„1Е!И, и, следовательно, два ребра е" и е из М имеют общую вершину — противоречие. Таким образом, М' — паросочетание.
Путь Р содержит 2(з — 1 ребер; й из них свободны ([и„и,[, (из, и,1,, [и«ь „и«к1) и (г — 1 принадлежат М. Следовательно, М'=МЯР содержит [М1-[-! ребер. П Например, увеличивающий путь р«=[оп о„о„о„о„о„оы, о,1 относительно паросочетания М„представленного па рис. 10.1, можно использовать для увеличения М, до М«=МЯР,=([оь о«1, [о«, оз1, [о„о,1, [о„о„1, [о«, о„1).
Поскольку М, — максимальное паросочетание (оно содержит [У1!2=5 ребер), то нет смысла искать увеличивающие пути в 6 относительно М;, не можетсуществовать увеличивающих путей относительно максимального паросочетания, поскольку такой путь, согласно лемме 10.1, можно было бы использовать для увеличения этого паросочетания. Оказывается, что обратное утверждение также верно. Теорема 10.1. Паоосочетание М в графе 6 максимально тогда и только иногда, когда в 6 не сушествует увеличивающего пути относительно М, Доказательство.
В одну сторону утверждение следует из леммы 10.1, Для доказательства обратного утверждения предположим, что в 6 не существует увеличивающего пути относительно М, но М не максимально, т. е. существует такое паросочетание М' в 6, что [М'1) [М[. Рассмотрим ребра, входящие в М®М', эти ребра образуют подграф графа 6 (этот подграф может быть несвязным). 'Так как никакие два ребра паросочетания не могут быть инцидент'пы одной и той же вершине, то подграф 6' =()', МЯМ') имеет специальную структуру — все его вершины имеют степень 2 или меньше.
Если степень вершины равна 2, то одно из инцидентных :,ей ребер входит в М, а другое — в М'. Поэтому все связные ком«й м зьзз 226 Гл. 1О. Алгоритмы длл задачи о ааротчетании поненты в 6' должны быть либо путями, либо циклами четной длины. Во всех циклах имеется одинаковое число ребер как из М, так и из И'.
Поскольку 1гИ'() 1М~, то хотя бы один из путей должен содержать больше ребер из М', чем из М, и, следовательно, этот путь является увеличивающим путем. Это, однако, противоречит нашему предположению о том, что в б не существует увеличиваю. щих путей относительно гИ. Д Характеризация максимальных паросочетаний, данная в теореме 1О.1, не сильно отличается от характеризациимаксимальных потоков в терминах увеличивающих путей (теорема 6.3).
Поэтому возникает соблазн построить для задачи о паросочетаиии аналог алгоритма построения максимального потока; начать с произвольного паросочетаиия (например, с пустого) и многократно находить увеличивающие пути, На ямом деле все известные алгоритмы для построения паросочетаний основаны в точности на этой идее. Тем не менее в этих алгоритмах имеется множество деталей. Более или менее непосредственно указанные идеи применяются в задаче о паросочетании в двудольных графах. В этом случае также наиболее понятна аналогия.
с задачей о максимальном потоке. 10.2 Алгоритм построения паросочетания а даудопьном графе Поскольку задача о паросочетании в двудольных графах является частным случаем задачи о пар<кочетании, обсуждавшейся в предыдушем параграфе (и, следовательно, к ней применима теорема 10.1), будем решать ее путем многократного нахождения увеличивающего пути р относительно текущего паросочетания М и увеличения текущего паросочетания до МфР. Кзк организовать поиск увеличивающих путей относительно паросочетания М в двудольном графе В=-(У, У, Е) систематическим и эффективным способом? Рассмотрим граф В и паросочетание М, представленные на рис. 10,2(а) Естественно, поиск увеличивающих путей должен начинаться с построения чередующихся путей из свободных вершин.
Так как один конец увеличивающего пути должен находиться в )г, а другой в (л', то, не теряя общности, можно начинать увеличивающие пути только из свободных вершин множества Р (в нашем примере п,) При этом можно искать всевозможные чередующиеся пути из а, одновременно, по принципу поиска в ширину. Начав из вершины гм можно искать увеличивающие пути, рассматривая все вершины, смежные с пм а именно ие и и„рис. 10.2(б)). Так как вершина о, свободна, все инцидентные ей ребра также свооодны По определению чередующегося пути мы должны теперь рассматривать ребра паросочстания, исходящие из и, и и„. Этот шаг однозначен, поскольку любая вершина имеет не более одного напарника. Естественно, если бы одна из вершин ие или ие былз 10,е.
Алеорипбм поспброеиип паробочелбипия об об и, и~ о, и. иб об об об об О О об о. б О о~ об О еб (в) иб оз об об (д) Рис, 10,2. 22Я Гл. 10. Алгоритмы для эадьчи о нароиметании свободной, то наша задача была бы выполнена, мы нашли бы увеличивающий путь. Однако это не так, и поэтому мы добавляем вершины и, и и, к нашему множеству чередующихся путей. По построению о, и о, — внешние вершины. Продолжаем далее увеличивающие пути из и, и о,. Заметим, что ребро [о„и,] (пунктирная линия на рис. 10.2(б)) опущено, поскольку и,, достигается из о, до просмотра вершины о,. Очевидно, поступая так, мы теряем только излишние увеличивающие пути.
В результате находим новые внешние вершины о„о, и о, (рис. 10.2(б)) и, наконец, замечаем, что внешняя вершина и, смежна со свободной вершиной и,. Таким образом, мы нашли увеличивающий путь и, используя его, можем увеличить М (рис. 10.2(д)). Процесс поиска увеличивающих путей сильно напоминает поиск в ширину.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
