Наибольшие паросочетания и задача о назначениях

Задача построения наибольших паросочетаний в гра­фе широко распространена, и для ее решения имеются эффективные алгоритмы. Эти алгоритмы основаны на ме­тоде чередующихся цепей, восходящем к Дж. Петерсену.

поопределению также чередующаяся. Ребра цепи назы­ваются темными или светлыми, если они входят или, соответственно, не входят вМ. Вершины графа G, ин­цидентные ребрам изМ, называются насыщенными, все другие вершины — ненасыщенными.

Рассмотрим, например, граф на рис. 77.1. Множество
ребер

— чередующаяся относительно М цепь; e₁ = {1, 2}, e₁₀ = {4, 8} — темные ребра Р; e₃ ={1, 4}, e₅ = {2, 5}, e₁₃ ={7, 8} — светлые ребра Р; {1, 2, 3, 4, 6, 8} и {5, 7, 9, 10} — множества насыщенных и ненасыщенных вершин соответственно.

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

Итак, отсутствие увеличивающих относительно М це­пей необходимо, если паросочетание М наибольшее. Это условие оказывается и достаточным. Именно, верна

Теорема 77.1. Паросочетание М в графе является наибольшим тогда и только тогда, когда в этом графе нет увеличивающих относительно М цепей.

Необходимость условия теоремы, как выше отмеча­лось, очевидна. Достаточность докажем от противного. Пусть М₁ также является паросочетанием в G и| М₁| > |М|. Рассмотрим граф Н, образованный ребрами, вхо­дящими в сумму М и М₁ по модулю 2, т. е. в (М UMi)\ \(М П Mi). Так как произвольная вершина v этого гра­фа инцидентна не более чем одному ребру каждого из паросочетаний М иMi, то ее степень не больше чем 2. Если deg v = 2, то одно из инцидентных вершине v ребер входит в М, другое — в М₁. Поэтому любая связная ком­понента графа Н является либо циклом, содержащим одно и то же число ребер из М и из М₁, либо чередую­щейся относительно М цепью. Но |М₁|>|М|, следова­тельно, среди этих компонент обязательно есть череду­ющаяся относительно М цепь, крайние ребра которой (первое и последнее) входят в М₁. Тогда крайние вер­шины этой цепи не насыщены паросочетанием М, что противоречит условию теоремы.

— наибольшее, α1 (G) — 5.

Таким образом, теорема 77.1 подсказывает следую­щую стратегию поиска наибольшего паросочетания: набрав с произвольного паросочетания М, строить последовательность М₁ = М, М₂, М₃, ...., в которой паросочетание M_k+1 получается из М_к с помощью только что расcмотренного изменения вдоль некоторой увеличивающей цепи. Поскольку |М_к+1| = |М_к| +1, то для получения наиболыпего паросочетания потребуется не более |G|/2 итераций (т. е. переходов от M_h к M_h+1). В качестве М можно взять, например, произвольное ребро графа или, что лучше, некоторое максимальное паросочетание, так что исходное паросочетание всегда имеется в нашем рас­поряжении. Поэтому разра­ботка эффективного алгорит­ма, основанного на указан­ной стратегии, сводится к построению процедуры, кото­рая быстро находит увели­чивающую цепь в графе, ли­бо выявляет ее отсутствие. Ограничимся случаем дву­дольного графа, хотя такая процедура (а значит, и эф-зективный алгоритм отыскания наибольшего паросочета-[ия) известна и в случае произвольного графа. Итак, Пусть G = (X, У, Е) — двудольный граф и М — паросочетание в этом графе. Поставим в соответствие графу G и паросочетанию М вспомогательный ориентированный двудольный граф G =(Х, У, А), полагая А=А1 U А2 где A1 = {{y, х): x € X, y € Y, xy € M), А₂={(х, у): х € = X, у € У, ху € EG\M}. Иными словами, чтобы получить граф G, достаточно придать ориентацию «от У к X» всем ребрам графа G, входящим в паросочетание М, и «от X к У» всем остальным ребрам этого графа. На рис. 77.2 изображены граф G с паросочетанием М (выделено жирными линиями) и граф G.

Обозначим через Х_M и У_м множества ненасыщенных вершин, входящих, соответственно, в X и У. Справедливость следующего утверждения очевидна.

Утверждение 77.2. В графе G увеличивающая относительно паросочетания М цепь существует тогда и толъко тогда, когда в графе G существует (s, t)-путь, у которого s € Х_м, t € У_м .

Пусть Р — (s, t)-путь в графе G, s € Х_м, t € У_м, P — соответствующая увеличивающая цепь в графе G и М₁ — паросочетание, полученное изменением М вдоль цепи Р. Тогда вспомогательный граф G₁ для графа G и паросо­четания М₁ можно получить из графа G заменой каждой дуги пути Р на обратную. Эта операция вместе с поиском пути Р составляет итерацию приводимого алгоритма. Предполагается, что граф G задан списками смежности.

Алгоритм A8_s построения наибольшего паросочетания в двудольном графе.

1. Построить какое-либо максимальное паросочетание М в графе G.

2. По графу G и паросочетанию М построить граф G.

3. Пусть в графе G Х- = {х: х € X, d-(x)=0}, Y⁺ = {у: y € Y, d⁺(y)=0} [в графе G X- U У⁺ — множе­ство вершин, не насыщенных текущим паросочетанием]. Выполнить в графе G поиск в ширину (алгоритм A6) из множества Х-.

4. Если в результате поиска в ширину ни одна из вершин множества У⁺ не получила метки, то перейти к п. 5. Иначе перейти к п. 6.

5. Пусть Т={(у₁ ,x₁), (у₂ ,x₂), ...,(у_k ,x_k)} — множество всех дуг, выходящих из множества У. Положить М* = { у₁x₁, у₂x₂, ..., y_kx_k} [M* — наибольшее паросоче­тание]. Конец.

6. Пусть P — (s, t)-путь в графе G такой, что s € X-", t € Y⁺. Изменить граф G, заменив в нем каждую дугу (а, b) пути Р на дугу ( b, а). Перейти к п. 2.

Утверждение 77.3. Алгоритм A8 строит наиболь­шее паросочетание в двудольном графе G = (X, У, EG) за время O(|EG| min{|X|, |У|}).

To, что алгоритм корректен и построенное им паро­сочетание является наибольшим, следует из теоремы 77.1 и утверждения 77.2. Очевидно также, что число итера­ций алгоритма (т. е. выполнений п. 2—5) не превосхо­дит величины min{|X|, |У|}, поскольку на каждой ите­рации, кроме последней, величины |Х-| и |У⁺| умень­шаются на единицу.

Согласно утверждению 76.2 п. 3 выполняется за вре­мя O(|EG|). Легко показать, что эта же оценка трудоемкости справедлива и для остальных шагов алгоритма. Таким образом, время выполнения отдельной итерации составляет O(|EG|), а алгоритма в целом — O(|EG| min{|X|, |У|}).

Вместе с наибольшим паросочетанием алгоритм A8 фактически находит и наименьшее вершинное покрытие в графе G. В результате последнего выполнения п. 3 ал­горитма будет установлено отсутствие пути из Х- в У⁺ в графе G. Следовательно, только часть вершин этого графа будет иметь метки после окончания поиска в ши­рину из Х-. Обозначим через X' и У’, соответственно, множества непомеченных вершин доли X и помеченных вершин доли У. Положим Z = X' U Y'. Будем считать, что в графе G нет изолированных вершин.

Утверждение 77.4. Множество Z является наи­меньшим вершинным покрытием графа G.

Утверждение достаточно доказать для связных гра­фов. Пусть (а, b)— произвольная дуга графа G. Если a € Y, b € X, то эти вершины либо обе помечены, либо нет. В обоих случаях дуга (а, b) инцидентна вершине множества Z. Пусть а € X, b € Y. Тогда, если вершина а не помечена, то a € Z. Если же а помечена, то и вер­шина b помечена и, следовательно, b € Z. Итак, всякая дуга графа G инцидентна некоторой вершине множества Z, т. е. Z — покрытие графа G. Кроме того, легко видеть,

что \Z\ = \Т\, где Т — множество всех дуг графа G, ве­дущих из множества Y. Множеству Т в графе G соот­ветствует наибольшее паросочетание. Поэтому из тео­ремы 32.2 следует, что вершинное покрытие Z является наименьшим.

Использованный здесь метод чередующихся цепей иг­рает важную роль и при решении более общих задач. Одну из них мы сейчас рассмотрим.

Пусть G — (X, Y, EG)—полный двудольный взвешен­ный граф, |X| = |Y|=n. Требуется найти в графе G совершенное паросочетание, вес которого минимален. Легко видеть, что это — упоминавшаяся ранее задача о назначениях (см. гл. IV, § 30).

Совершенное паросочетание минимального веса назо­вем для краткости оптимальным решением.

Задача о назначениях обладает двумя простыми свой­ствами:

1. Поскольку для каждой вершины любое совершен­ное паросочетание содержит в точности одно ребро, инцидентное этой вершине, то множество оптимальных ре­шений не изменится, если веса всех ребер, инцидентных какой-либо вершине, увеличить (уменьшить) на одно и то же число.

2. Если веса всех ребер графа неотрицательны и вес некоторого совершенного паросочетания равен нулю, то оно является оптимальным решением.

Пусть, как обычно, w(x, у)—вес ребра ху. Будем считать, что w(х, у) ≥ 0 для каждого ребра ху € EG. Из первого свойства следует, что случай, когда имеются ребра отрицательного веса, сводится к нашему. Кроме того, это свойство позволяет, затратив О (п²) операций, перейти к взвешенному графу, у которого каждой вер­шине инцидентно ребро нулевого веса и веса всех ребер неотрицательны. Для этого достаточно изменить матрицу весов графа G. следующим образом: сначала вычесть из всех элементов каждой строки минимальный элемент этой строки, а затем то же самое проделать со столбцами. Будем считать, что эта операция уже проделана и граф G обладает требуемыми свойствами.

Пусть A € X, В € Y и α — некоторое число. Будем говорить, что к графу G применяется операция (А, В, α), если сначала из веса каждого ребра, инцидентного вершине из множества А, вычитается α, а затем к весу каждого ребра, инцидентного вершине из В, прибавля­ется α. Согласно свойству 1 получившийся в результате взвешенный граф имеет то же множество оптимальных решений, что и граф G. Кроме того, ребра вида аb, где а € А, b € В, в преобразованном графе будут иметь те же веса, что и в исходном. Пусть Т = (X, У, U) — двудоль­ный граф M — паросочетание в этом графе. Будем, как и ранее, обозначать через Т = Т(Т, М) ориентированный двудольный граф, полученный из графа Т путем ориен­тации «от У к X» всех ребер паросочетания М и «от X к У» остальных ребер этого графа.

Будем считать, что граф G задан матрицей весов.

Алгоритм A9 построения совершенного паросочетания минимального веса в двудольном взвешенном графе.

1. Построить граф Т =(Х, У, U), U = {ху: w(x, y)=0).

2. Найти в графе Т максимальное паросочетание М.Пусть Х_M ж Y_M — множества вершин, не насыщенных паросочетанием М и входящих, соответственно, в доли Х и Y

3. 3. Если Х_м = Y_M = ¢ то конец [M — оптимальное решение задачи]. Иначе построить граф T = T(T, М).

4. Применить к графу Т поиск в ширину (алгоритм A6) из множества Хм. Если найден (х,y)-путь Р, х € Х_м, y € Y_M то перейти к п. 5. Иначе перейти к п. 7.

5. Преобразовать граф Т, заменив в нем каждую ду­гу пути Р на обратную. Пусть Х_м = (х: х € X, d-(x) = 0), Y_M =( y: y € Y, d⁺(y)=0) [путем изменения М вдоль увеличивающей цепи найдено новое паросочетание в графе Т — (Х, У, U), Хм € Х, Y_M € Y — подмножества вершин графа Т, не насыщенных новым паросочетанием].

6. Если Х_м = Y_M =¢, то конец [множество всех та­ких ребер ху, что х € X, у € Y и (у, x)—дуга графа T, составляет совершенное паросочетание минимального веса в исходном графе G]. Иначе перейти к п. 4.

7. Пусть X' € X и Y' € Y — подмножества вершин графа Т, получивших пометки в результате поиска в ширину (в п. 4). Среди ребер графа G, имеющих вид ху, х € Х’ , y € Y — Y’, найти ребро минимального веса. Пусть α — вес этого ребра.

8. Модифицировать веса дуг графа G, применив к нему операцию (Х’, Y', α).

9. Модифицировать граф Т, добавив к нему все такие дуги (х, у), что х € Х, у €Y- Y’, w(x, y)=0, и удалив все такие дуги (х, у), что x € Х-Х’, y € Y’. Перей­ти к п. 4.

Займемся теперь обоснованием алгоритма A9. Кор­ректность пп. 1—3 не вызывает сомнений. Легко видеть также, что каждый из этих пунктов можно выполнить за время О(п²). Остальные пункты алгоритма рассмот­рим более подробно.

Каждое выполнение п. 5 увеличивает на единицу число вершин y € Y, для которых d⁺(y)= 1. Следователь­но, этот пункт выполняется не более п раз. Наша бли­жайшая цель — показать, что после выполнения пп. 4, 6—9 не более чем п раз подряд обязательно произойдет переход к п. 5, т. е. очередное выполнение п. 4 закон­чится отысканием пути Р. Рассмотрим подробнее пп. 7—9. После окончания п. 4 и перехода к п. 7 каждая дуга графа Т инцидентна по крайней мере одной вершине множества (X — X') U Y. Это сразу следует из утверждения 77.4. Таким образом, каждое ребро нулевого веса в графе G инцидентно одной из вершин этого множе­ства. С другой стороны, поскольку Х_м ≠ ¢, Y_M ≠ ¢, то X' ≠ Х, Y' ≠ Y. Поэтому из правила выбора величины α в п. 7 следует, что α > 0. После модификации графа G в п. 8 веса всех его ребер останутся неотрицательными (это следует из правила выбора α). В результате последующей модификации графа Т (п. 9) его дуги по-прежнему будут соответствовать ребрам нулевого веса в графе G, причем дуги вида (у, х), х € X, у € Y, будут соответствовать паросочетанию нулевого веса в графе G. Модификация гра­фа Т в п. 9 обладает двумя важными свойствами. Во-пер­вых, удаленные дуги этого графа направлены от непомеченных вершин доли X. Поэтому все вершины, достижимые из Х_м в «старом» графе Т, достижимы из этого множества и в «новом» графе Т. Во-вторых, добав­ленные дуги направлены от помеченных вершин доли X кнепомеченным вершинам доли Y. Таким образом, при­менение поиска в ширину к модифицированному графу Т (п. 4) приведет к тому, что дополнительно будет по­мечена по крайней мере одна вершина доли Y. Посколь­ку |Y| = п, то после выполнения пп. 4, 7—9 не более чем п раз подряд помеченной окажется некоторая вер­шина множества Y_M, т. е. будет найден путь Р, и затем последует выполнение п. 5. Как уже было показано, п. 5 (а значит, и п. 6) выполняется не более п раз. Поэтому каждый из пп. 4, 7—9 выполняется не более п² раз.

Легко видеть, что трудоемкость каждого из пп. 1—9 не превосходит O(п²). Поэтому время работы алгоритма в целом оценивается сверху величиной О(п⁴).

Как отмечалось выше, после выполнения п. 8 веса всех ребер графа G остаются неотрицательными, и, сле­довательно, множество оптимальных решений не меня­ется. Условие окончания Х_м = Y_M = ¢ означает, что в «последнем» графе Т имеется п дуг, направленных от X к У, которым соответствует совершенное паросочетание нулевого веса в «последнем» графе G. Согласно свой­ству 2 оно является оптимальным решением исходной задачи.

Резюмируем все выше изложенное в виде теоремы.

Теорема 77.5. Алгоритм Ад строит совершенное паросочетание минимального веса в двудольном взве шенном графе G=*(X, Y, EG), |X| =|Y|=n, за вре­мя О(п⁴).

Замечание. Известен алгоритм, решающий эту задачу за время О(п³). В алгоритме A9 оценка О(п⁴) возникает, по существу, из-за того, что приходится О(п²) раз выполнять операцию (X', Y', α), которая сама требует времени О(п²). Снижение оценки до О(п³) дости­гается за счет того, что результат этой операции удается получить за время О(п).

Рис. 77.3

Оценка имеет вид О (п²-⁵ log (пТ)), где Т— наибольший из весов ребер графа.

Пример. На рис. 77.3 представлена матрица весов V=|| W_ij || двудольного графа G=(X, Y, EG), у которой V_ij = w (x_i, x_j), x_i € X, y_j € Y. Там же изображен граф G, построенный по максимальному паросочетанию М = (x₂y₁, x₁y₂) нулевого веса в графе G. Соответствующие этому паросочетанию дуги графа Т обведены жирными линиями, а элементы матрицы W отмечены звездочками. Перед первым выполнением п. 4 имеем Х_м = {х₃,, х₄ , х₅} , Y_M = {y₃,, y₄ ,y₅}. Поиск в ширину из Х_м дает X' = { х₂ , х₃,, х₄ , х₅}, Y' = {y₁}. Вершины множества X' U Y' будем отмечать значком «+». Поскольку пути из Xм в Y_M нет, то переходим к пп. 7—9. Находим α = W₃₂ = 1 и выполняем операцию ({ х₂ , х₃,, х₄ , х₅},{y₁}, 1), т. е. вычитаем 1 из всех элементов в строках 2, 3, 4, 5 и прибавляем это число ко всем элементам первого столбца. В результате к графу Т добавится дуга (х₃ , y₂). Модиицированная матрица W (т. е. граф G) и граф Т представлены на рис. 77.4.

Применение поиска в ширину к графу Т дает путь = (х₃ , y₂,, х₁ , y₅) из Х_м в Y_M. Заменим (выполнение 5) в графе Т дуги (х₃ , y₂,), (y₂ , x₁), (х₁ , y₅)соответственно на дуги (y₂ , x₃), (x₁ , y₂), (y₅ x₁). Новый граф Т также изображен на рис. 77.4. В нем Х_м = { х₄ , х₅}, Y_M ={y₃,, y₄ }.

Получим α= W₅₅ = 2. Результаты последующего приме­нения к графу G операции ({ х₂ , х₄ , х₅},{y₁}, 2) и моди­фицированный граф Т представлены на рис. 77.5. В этом графе имеется путь Р=(х₅, y₅ ,х₁, у₁) из Х_м в Y_M.

совершенного паросочетания минимального веса в исход­ном графе G. Вес этого паросочетания равен 0 + 0 + 1 + + 6 + 3 = 10.