В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов, страница 66

Утверждение 77.4. Множество 2 является наимюсьшим верши>ьным покрытием графа 6. с Утворждепие достаточно доказать для связных графов. Пусть (а, Ь) — произвольная дуга графа 6. Если а си У, Ь ее Х, то эти вершины либо обе помечены, либо пот. В обоих случаях дуга (а, Ь) ипцндгптна вершине множества /. Пусть а ~ Х, Ь еэ У. Тогда, если вершина а не помочепа, то а си/. Если же а помечена, то и вершина Ь помечена п, следовательно, Ь ~ 2.

Итак, всякая дуга графа 6 ипцидентна некоторой вершине множества 7, т. е, Я вЂ” покрытие графа 6. Кроме того, легко видеть, что ~l! =-!Т~, где Т вЂ” мпонсество всех дуг графа С, ведущих из множоства У. Мполсеству Т в графе 6 соответствует наибольшее паросочетапие. Поэтому из теоремы 32.2 следует, что вершинное покрытие Я является навмопьшим. З Использованный здесь метод чередующихся цепей играет важную роль и при решении более общих задач.

Одну из пих мы сейчас рассмотрим. Пусть С = (Х, У, Е6) — полный двудольный взвешенный граф, !Х! =!У! = п. Требуется найти в графа 6 совершенное паросочетание, вес которого минимален. Легко видеть, что это — упоминавшаяся ранее задача о назначениях (см. гл. 1Ъ', 3 30). Совершенное паросочетание минимального веса назовем для краткости оптимальным решением. Задача о назначениях обладает двумя простыми свойствамн: 1. Поскольку для каждой вершины любое совершенное паросочетаппе содержит в точности одно ребро, ип- 358 цидентное этой вершине, то множество оптимальных решений не изменится, если веса всех ребер, ипцидентпых какой-либо вершине, увеличить (уменьшить) на одно и то же число.

2. Если веса всех ребер графа неотрицательны и вес некоторого совершенного паросочетапия равен пулю, то оно является оптимальным решением. Пусть, как обычно, и~(х, у) — вес ребра ху. Будем считать, что ю(х, у)~0 для каждого ребра хушВС. Из первого свойства следует, что случай, когда имеются ребра отрицательного веса, сводится к нашему. Кроме того, это свойство позволяет, затратив 0(п») операций, переити к взвешенному графу, у которого каждой вершине инцндентно ребро нулевого веса и веса всех ребер пеотрицательны. Для этого достаточно изменить матрицу весов графа С следующим образом: сначала вычесть из всех элементов каждой строки минимальный элемент атой строки, а затем то же самое проделать со столбцами. Будем считать, что эта операция уя«е проделана и граф С обладает требуемыми свойствами.

Пусть А<=Х, В~ У и а — некоторое число. Будем говорить, что и »рафу С применяется операция (А, В, и), если сначала из веса каждого ребра, ипцндеятного вершине из множества А, вычитается с», а затем к весу кая«доге ребра, инцидентного вершине из В, прибавляется а. Согласно свойству 1 получившийся в результате взвешенный граф имеет то»ке множество оптимальных решений, что и граф С.

Кроме того, ребра вида аЬ, где а ш А, Ь ш В, в преобразованном графе будут иметь то же веса, что и в исходном. Пусть Т=(Х, У, С) — дзудольный граф и М вЂ” паросочетапне в этом графе. Будем, как и ранее, обозначать через Т = Т(Т, М) ориентированный двудольный граф, получеппый из графа Т путем ориентаций «от У к Х» всех ребер паросочетапия М и «от Х к У» остальных ребер этого графа. Будем считать, что граф С задан матрпцей весов. Алгоритм л»д построения совершенного паросочетания минимального веса в двудольном взвешенном графе. 1. Построить граф Т =(Х, У, С), сГ= (ху: ю(х, у)= О).

2. Найти в графе Т максимальное паросочетапие ЛХ. Пусть Хн н Ун — множества вершин, не насыщенных паросочетапнем М н входящих, соответственно, в доли Хи У. 359 3. Если Хм = Ув = Ы, то конец (ЛХ вЂ” оптимальное решение задачи]. Иначе построить граф Т=Т(Т, зд), 4. Применить к графу 7' 1н пса в ширпзу (алгоритм .Фд) из множества Хи.

Если найден (х, у)-путь Р, хдн <н Хя, у ~ Уя, то аерейтн к п. 5. Иначе перейти к п. 7. 5. Преобразовать граф Т, зацепив в нем каждую дугу пути Р па обратную. Пусть Хя = (ал х ~и Х, г( (х)= = О), Ум = (йч рдн У, И+(р)= О) (путем изменения йХ вдоль увеличивающей цепи найдено новое паросочетание в графе Т =(Х, У, П), Хв<=Х, У„~ У вЂ” подмножества вершин графа Т, пе насыщенных новым паросочетапием]. 6. Если Х.

= У = Ы, то конец (множество всех таких ребер хр, что х ш Х, у я У и (у, х) — дуга графа Т, составляет совершенное паросочетание минимального веса в исходном графе 6]. Иначе перейти к п. 4. 7. Пусть Х' ~= Х и У' ~ У вЂ” подмножества вершин графа Т, получивших пометки в результате поиска в ширину (в п. 4). Среди ребер графа С, имеющих вид ху, х я Х', уев У вЂ” Г, найти ребро минимального веса. Пусть сд — вес этого ребра. 8.

Модифицировать веса дуг графа 6, применив к нему операцию (Х', У', а). 9. Модифицировать граф Т, добавив к нему все такие дуги (х, у), что х ~иХ, у ш У вЂ” У', и(х, у)= О, и удалив все такие дуги (х, у), что х~нХ вЂ” Х, у~в Г. Перейти к п. 4. Займемся теперь обоснованием алгоритма Фд.

Корректность пп. 1 — 3 не вызывает сомнений. Легко видеть такдке, что каждый из этих пунктов можно выполнить за время 0(пд). Остальные пункты алгоритма рассмотрим более подробно. Каждое выполнение п. 5 увеличивает па единицу число вершин р ш У, для которых о+(у) = 1. Следовательно, этот пункт выполняется не более п раз. Наша ближайшая цель — показать, что после выполнения пп. 4, 6 — 9 не более чем и раз подряд обязательно произойдет переход к п.

5, т. е. очередное выполнение п. 4 закончится отысканием пути Р. Рассмотрим подробнее пп. 7 — 9. После окончания п. 4 и перехода к п. 7 кансдая дуга графа Т ипцидентна по крайней мере одной вершине множества (Х вЂ” Х')0 Г. Это сразу следует из утверждения 77.4. Таким образом, каждое ребро нулевого 360 веса в графе С ияцидептио одной из вершки этого миожества. С другой стороны, поскольку Х~~И, Ум««И, то Х «ь Х, У чь У. Поэтому из правила выбора величины а з п. 7 следует, что с«) О.

После модификации графа С в п. 8 веса всех его ребер останутся веотрицательвыми (это следует пз правила выбора и). В результате последующей модификации графа Т (и. 9) ого дуги во-прежнему будут соответствовать ребрам пулевого веса в графе 6, причем дуги вида (у, х), х ж Х, у ж У, будут соответствовать паросочетакию нулевого веса в графе 6. Модификация графа Т в п. 9 обладает двумя важиыми свойствамк. Во-первых, удаленные дуги этого графа направлены от непомеченных вершин доли Х.

Поэтому все зершииы, достижимые из Хв в «старом» графе Т, достижимы из этого миожества и в «иовом» графе Т. Во-вторых, добавлеипые дуги направлены от помеченных вершил доли Х к иепомечепиым вершинам доли У. Таким образом, примеяение поиска в ширину к модифицироваииому графу Т (п.

4) приведет к тому, что дополнительно будет помечена по крайней мере одна вершина доли У. Поскольку ) У) = п, то после выполиекия пп. 4, 7 — 9 ие более чем п раз подряд помеченной окажется иекоторая вершина множества Ув, т. е. будет найден путь Р. в затем последует выполнение п. 5. Как уже было показано, и. 5 (а значит, и п.

8) выполпяется пе более п раз. Поэтому каждый из пп. 4, 7 — 9 выполняется не более и' раз. Легко видеть, что трудоемкость каждого из пп. 1 — 9 ие превосходит 0(пг). Поэтому время работы алгоритма в целом оцеиивается сверху величиной 0(п«). Как отмечалось выше, после выполнения п. 8 веса всех ребер графа 6 остаются неотрицательными, и, следовательио, множество оптимальных решений пе меияется. Условие окончания Хи = Ув = ю означает, что в «последием» графе Т имеется п дуг, паправлеииых от Х; к У, которым соответствует совершенное паросочетаиие нулевого веса в «последнем» графе С.

Согласно свойству 2 оио является оптимальным решением исходной задачи. резюмируем все выше изложенное в виде теоремы. Т е о р е м а 77.5. Алгоритм А«строит совершенное паросочетание минимального веса в двудольном взвешенном графе С (Х, У, ЕС), !Х! = (У( =и, за время 0(и'). 3 а м е ч а н и е. Известен алгоритм, решающий эту задачу за время 0(и»). В алгоритме лб» оценка 0(п«) возникает, по существу, из-за того, что приходится 0(п') раз выполшггь операцию (Х', У', а), которая сама требует времени 0(и'). Снижение оценки до 0(п') достигается за счет того, что результат этой операции удается получить за время 0(п).

Недавно опубликован алгоритм, оценка трудоемкости которого во многих случаях предпочтительнее 0(п»). Эта г и' В и В 7 В В и ~ б г С, Ч« В В 7 б и т б В зз Рис. 77.3 оценка имеет внд 0(и»» 1ои(пТ) ), где Т вЂ” паиболыпий из весов ребер графа. .«Чтзь ««33) Пример. На рис. 77.3 представлена матрица весов И' = ~ И';,б двудольного графа 6 =(Х, У, ЕС), у которой И'е = ю(хв х,), х; ~н Х, у; ~ У. Там же изображен граф Т, построенный по максимальному паросочетанию М = =- (х»уь х~у») нулевого веса в графе О.

Соответствующие этому паросочетанию дуги графа Т обведены жирными лнпнямн, а элементы матрицы И' отмечены звездочками. Перед первым выполнением п. 4 имеем Хв = (х» х4~ х»)~ ум = (У»1 У«1 УБ). ПОиск В ширину из Хм дает Х' = (хь х», х«, х»), У' = (у1). Вершины множества Х' 0 У' будем отмечать значком «+».

Поскольку пути нз Хн в Ув пег, то переходим к пп. 7 — 9. Находим с« = = И'»» = 1 и выполняем операцию ((х», хз, х«, хз), (У1), 1) т. е. вычитаем 1 из всех элементов в строках 2, 3, 4, 5 и прибавляем это число ко всем элементам первого столбца. В результате к графу Т добавится дуга (хз, у»). Модифицированная матрица )т (т. е.