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

Рассмотрим мультиграф Л, получающийся из графа Р () Рг заменой каясдой дуги, входящей одновременно в Р' и Рг„двумя экземплярами этой дуги. Очевидно, что Л пе содержит отрицателыгых контуров. Поэтому, согласно утверждению 76.3, Х содержит такой (1, /)-путь Р, что ю(Ь)~ и~(Р) и, следовательно, (Р')= (Р:)+и(Р',) (Р')+ (Р.') = (Е)~.(Р) Это ~еравенство противоречит минимальности Рг. Таким образом, пути Рг и Рг являются кратчайшими среди, соответственно, (1, (г)- и ((г, 1)-путей, все внутренние вершины которых принадлежат множеству (1, 2, ..., й — 1).

Поэтому, воспользовавшись предположением индукции, получим И ~ч = И'~,, '+ И "„' = ю (Р~) + М) = «(Р'). а Теорема 76.5. Время работы алгоритма эвг пе превосходит 0((С~з). Если граф С не содержит отрицательных контуров, то Итц — вес кратчайшего (1, ])-пути в графе С для всех 1, 7 =1., и, и =!С!. Если же такие контуры в графе итлеются, то существуют такие числа и и 1, что Итй(0. > Справедливость первого утверждения теоремы очевидна, поскольку каждая из ке более чем !С~ итераций выполняется за время 0 ~ С ~ г. Второе утверждение теоремы непосредственно следует из утверждения 76.4.

Допустим теперь, что граф С содержит отрицательные контуры. Пусть т — такой наименьший индекс, что для некоторой вершины 1 в графе С имеется отрицательный контур о', содеря ащий только ( и некоторые верзпипы множества (1, 2, ..., гп). Ясно, что контур д включает вершину и. Тогда прн любых 1, 1 = 1, и число Иг~ н~ равно весу кратчайшего (1, 7)-пути, все внутренние вершины которого принадлежат множеству (1, 2, ..., т — 1). Доказательство этого факта дословно повторяет доказательство утверждения 76.4. Контуру В соответствуют ((, т)-путь Р, и (т, ()-путь Рг, такие, что Р~ 6 Рг = о'.

Поскольку внутренние вершины путей Р~ и Рг принад- 332 лежат множеству (1, 2, ..., лг — 1), то ю(Р,)>Ига 1 й(рв))И7 ~. Следовательно, ' И, '+ И'; 'е..ю(рг)+ +и(рв)=ю(Я), т. е. Игг1 ш1п(О,И7' '+ И",",,') с'.О. <1 Рис. 76.2 Пример 2. Ниже приведены резулт,таты гьвполлония пан<дай из четырех итераций алгоритма для графа, изображенного на рис.

76,2: Найдем, например, с помощью матрицы Ре кратчайпшй (2, 1)-путьорвг = 4, Ре, = 3, Ре„= 2 Слодоиатольпо, (2, 3, 4, 1) — кратчайший (2, 1)-путь. 23 В, ь. Биевичев и ав. зсз -.-(' ' ') '-(-' -' -'') .-('- -' -'') Ив 02 — 1 '-('-'-) 0111 ре 2022 4440,, О111 рг 20221 = ззоз~ 4140, "-('"':~ 0121 рз (2023 =('3303 е41 2 0 0121, ре (4023) !~ 1~ :4 1 2 О, 4 77. Наибольшие пароеочетапия и задача о назначениях Задача построения наибольших паросочетаний в графе широко распространеяа, и для ее решения имеются аффективные алгоритмы. Эти алгоритмы основаны па методе чередующихся цепей, восходящем к Дж.

Петерсену. Пусть М вЂ” паросочетанне в графе 6. Цепь графа 6, ребра которой поочередно входят и не входят в М, называется чередующейся относительно М. Цепь длины 1 1 е, я е, 5 Рвс. 77Л по определению также чередующаяся. Ребра цепи называются темными или светлыми, если они входят или, соответственно, не входят в М. Вершины графа 6, инцидентные ребрам из М, называются насыщенными, все другие вершины — ненасыщенными. Рассмотрим, например, граф на рис. 77.1, Множество ребер М= (еп еп е1о) является в С паросочетанием; Р=(7,8, 4, 1,2,5) (2) — чередующаяся относительно М цепь; е1 = (1, 2), ею= = (4, 8) — томные ребра Р; ел = (1, 4), ее=(2, 5), ем =- = (7, 8) — светлые ребра Р; (1, 2, 3, 4, б, 8) и (5, 7, 9, 10) — лшожества насыщенных и ненасыщенных вершин соответственно.

Очегидпо, что если в графе С существует чередующаяся относительно паросочетапия М цепь, соединяющая две несовпадающие ненасыщенные вершины, то можно построить в С паросочетанне с большим числом ребер, чем в М. В самом доле, в такой цепи число темных ребер на единицу меньше числа светлых. Удалив из М 354 все темные ребра и присоединив все светлые, получим новое паросочетание, в котором число ребер на единицу больше. По отой причине чередующуюся относительно паросочотання ЛХ цепь, соединяющую две различные ненасыщеппыо вершины, будом называть увеличивающей относительно ЛХ цепью в графе С.

Итак, отсутствие увеличивающих относительно М цепей необходимо, если паросочетание М наибольшее. Это условие оказывается и достаточным. Именно, верна Теорема 77.1. Наросочетание М в графе является наибольшим тогда и только тогда, когда в етом графе нет увеличивающих относительно М з)елей. > Необходимость условия теоремы, как выше отмечалось, очевидна. Достаточность докажем от противного. Пусть ЛХ1 также является паросочетанием в 6 и ~ЛХз) ) ) ~ЛХ~. Рассмотрим граф Н, образованный ребрами, входящими в сумму ЛХ и ЛХз по модулю 2, т. е.

в (М0 М~)~ ~(ЛХ 0 М1). Так как произвольная вершина о этого графа ннцпдентпа пе более чем одному ребру каждого из паросочетапяй М и Мь то ее степень не болыпе чем 2. Если йод о = 2, то одно из инцидентных вершине о ребер входит в ЛХ, другое — в ЛХь Поэтому любая связная компонента графа Н является либо циклом, содержащим одно и то же число ребер из М н из Мн либо чередующейся относительно ЛХ цепью. Но ~М1~ ) ~ЛХ~, следовательно, среди этих компонент обязательно есть чередузощаяся относительно М цепь, нрайние ребра которой (порзое и последнее) входят в ЛХо Тогда крайние вершины этой цепи не насыщены паросочетанием ЛХ, что противоречит условию теоремы. 3 Для иллюстрации снова обратимся к графу С на рис.

77.1. Чередующаяся относительно паросочетания (1) цепь (2) соединяет ненасыщенные вершины 5 и 7. Следовательно, можно построить паросочетание М' с большим числом ребер: ЛХ' =(М~(еь е1ь)) 0 (ез, ез, е1з) = (ез, ез, ен езз) Паросочетание ЛХ' также не является наибольшим: (9, 10) — увеличивающая относительно ЛХ' цепь. Паросочетание М = М 0 (е!з) = (ез, ез, ез е!3 е~з) — папболыпее, сз1(С) = 5.

Таким образом, теорема 77.1 подсказывает следующую стратегию поиска наиболыпсго паросочетания: на- 23» 355 чзв с произвольного паросочетания М, строить последовательность М = М, Мх М», ..., в которой паросочетанпе М„+, получается из М, с помощью только что рассмотренного изменения вдоль некоторой увеличивающей цепи. Поскольку )М„+1! = !М,! + 1, то для получения напболшчего наросочетапия потребуется не более ~6~!2 итераций (т.

е. переходов от М, к М„+1). В качестве М можно взять, например, произвольное ребро графа или, что лучше, некоторое максимальное паросочетание, так что исходное паросочетание всегда имеется в нашем распоряжении. Поэтому разработка аффективного алгоритма, основанного на указанной стратегии, сводится к построению процедуры, которая быстро находит увеличивающую цепь в графе, либо выявляет ее отсутствие. Ограничимся случаем двуРис. 77.2 дольного графа, хотя такая процедура (а значит, и эффективный алгоритм отыскания наибольшего паросочетаппя) известна и в случае произвольного графа.

Итак, пусть 6=(Х, У, Е) — двудольный граф и М вЂ” паросочетапве в этом графе. Поставим в соответствие графу 6 и паросочетапию М вспомогательный ориентированный двудольпып граф 6=(Х, У, А), полагая Л =Л10Л«, где Л~ -— -((у, х): х ш Х, уж У, ху = М), Аз= ((х, у): х«н е Х, у е У, хр я ЕРМ). Иными словами, чтобы получить граФ 6, достаточно придать ориентацию «от У к Х» всем ребрам графа 6, входящим в паросочетание М, и «от Х к У» всем остальным ребрам этого графа. На рис. 77.2 изображены граф 6 с паросочетанием М (выделено жирными линияни) и граф 6. Обозначим через Хи н У„множества ненасыщенных вершин, входящих, соответственно, в Х и У.

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

Эта операция вместе с поиском пути Р составляет итерацию приводимого алгоритма. Предполагается, что граф 6 задан списками смежности. Алгоритм .Ф, построении наибольшего паросочетания в двудольном графе. 1. Построить какое-либо максимальное паросочетание М в графе 6. 2. По графу 6 и паросочетапию М построить граф 6. 3. Пусть в графе С Х =(х: х~нХ, д (х)=0), У+= =(у: ун У, д~(у)= О) (в графе 6 Х-0 Ул — множество вершин, не насыщенных текущим паросочетанием]. Выполнить в графе 6 поиск в ширину (алгорнтм Фз) из множества Х .

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

2. Утверждение 77.3. Алгоритм Фз строит наибольшее наросочетание е деудольном графе 6=(Х, У, ЕС) за гремя 0(]Е6] ш(п (]Х!, ] У])). с' То, что алгоритм корректен и построенное им паросочетание является наибольшим, следует из теоремы 77А и утвернгдения 77.2. Очевидно также, что число итераций алгоритма (т. е. выполнений п. 2 — 5) не превосходит величины шш (]Х], ]У]), поскольку па каждой итерации, кроме последней, величины ]Х ] и ]У+] уменьшаютсн па единицу. Согласно утверждению 76.2 п. 3 выполняется за время 0(]ЕС]).

Легко покааать, что зта же оценка трудо- емкости справедлива и для остальных шагов алгоритма. Таким образом, время выполнения отдельной итерации составляет 0(~ЕС~), а алгоритма в целом— 0(~ЕС~ шш (~Х~, ~ У~)). з Вместо с наибольшим паросочетанием алгоритм .Фз фактически находит и наименьшео вершинное покрытие в графе С. В результате последнего выполнения п. 3 алгоритма будет установлено отсутствие пути из Х в У+ в графе С. Следовательно, только часть вершин этого графа будет иметь метки после окончания поиска в ширину пз Х . Обозначим через Х' и У', соответственно, множества непомеченных вершин доли Х и помеченных вершин доли У. Положим Я = Х 0 У . Будем считать, что в графе С пет изолированных воршин.