Максимальное паросочетание в двудольном графе.

Паросочетанием называется множество ребер (дуг), не имеющих общих вершин. Паросочетание с наибольшим числом ребер называется максимальным паросочетанием.

Вершина называется насыщенной в паросочетании М, если она является концевой для некоторого ребра, входящего в М. Полным паросочетанием

X с Y в двудольном графе G = (X U Y,E) называется такое паросочетание,

что все вершины из X являются насыщенными. Если | X| = | Y|, то полное паросочетание называется совершенным.

Пусть S – произволное подмножество X, а ГS - подмножество вершин

Y, смежных с вершинами S.

Полное паросочетание X с Y в двудольном графе G = (X U Y,E) существует

тогда и только тогда, когда | S| £ |ГS| для любого S Ì X ( теорема Холла).

Дефицитом двудольного графа G называется величина

 

σ (G) = max {| S| - |ГS| }

S Ì X

 

Поскольку не исключается случай S = 0, то σ (G) ≥ 0.

Основной результат, касающийся паросочетаний в двудольных графах,

Заключается в том, что в максимальное число ребер в паросочетании

равно | X| - σ (G) (теорема Кенига –Оре) [5].

Заметим, что полное паросочетание X с Y существует тогда и только тогда,

когда дефицит двудольного графа равен нулю.

В качестве примера рассмотрим двудольные графы, представленные на

рис. 14 и 15.

Не трудно проверить, что дефицит графа на рис. 14 равен 1, так как существует единственная положительная разность

 

|{ x₁, x_2, x₃ }| - | Г { x₁, x_2, x₃ }| = |{ x₁, x_2, x₃ }| - |{ y₁, y₂ }| = 1

 

Граф, представленный на рис. 15, отличается от графа на рис. 14

наличием pебра (x₃, y₄). Дефицит графа на рис. 15 равен 0. Следовательно, существует полное паросочетание X с Y, например,

M = {(x₁, y₁), (x₂, y₂), (x₃, y₄), (x₄, y₃)}.

 

X Y X Y

○ y₁ ○ y₁

x₁ ○ x₁ ○

○ y₂ ○ y₂

x₂ ○ x₂ ○

○ y₃ ○ y₃

x₃ ○ x₃ ○

○ y₄ ○ y₄

x₄ ○ x₄ ○

○ y₅ ○ y₅

 

 

Рис. 14 Рис. 15

 

 

Приведем формулировку теоремы Холла в терминах теории

трансверсалей.

Пусть P -непустое множество, а S = { S_1, S_2,…, S_k} – семейство

Непустых подмножеств множества P, причем допускается, что S_i = S_J

при i≠j. Системой различных представителей или трансверсалью семейства

S называется множество k различных элементов множества P, по одному

из каждого S_i.

Например, если P= {1,2,3,4,5,6}, S₁= {1,3,4}, S₂= {1,3,4}, S₃= {1,2,5}, S₄= {3,6},

то T = {1,3,2,6} множества S_1, S_2, S_3,S₄.

С другой стороны, если S₅= {3,6}, S₆= {4}, то для семейства S_1, S_2, S_3,S_4,S_5,S₆

трансверсаль не существует.

Задача нахождения трансверсали может быть сведена к задаче построения полного паросочетания в двудольном графе G = (X U Y,E), построенном следующим образом.

Поставим во взаимно однозначное соответствие элементы множества вершин двудольного графа X элементам семейства S (x_i ↔ S_i), а элементам множества Y – элементы множества P (p_i ↔ y_i). Ребро (x_i , y_j) Î E тогда и только тогда, когда p_i Î S_i.

Нетрудно заметить, что необходимые и достаточные условия существования трансверсали эквивалентны условиям существования полного паросочетания X с Y. Таким образом, для существования трансверсали семейства подмножеств

S множества P необходимо и достаточно чтобы объединение произвольных k

подмножеств из S содержало не менее k элементов из P.

Пример 6. Построим двудольные графы для двух рассмотренных ранее случаев. На рис.16 приведен граф, когда P= {1,2,3,4,5,6}, S ={S_1, S_2, S_3,S₄ }, а на

рис.17 – для случая, когда S ={S_1, S_2, S_3,S_4,S_5,S₆}

 

○ y₁ (p₁) x₁ ○ ○ y₁

(S₁) x₁ ○

○ y₂ (p₂) x₂ ○ ○ y₂

(S₂) x₂ ○

○ y₃ (p₃) x₃ ○ ○ y₃

(S₃) x₃ ○

○ y₄ (p₄) x₄ ○ ○ y₄

(S₄) x₄ ○

○ y₅ (p₅) x ₅ ○ ○ y₅

 

○ y₆ (p₆) x ₆ ○ ○ y₆

 

Рис. 16 Рис. 17

 

В первом случае выполняется условие теоремы Холла, а во втором –

условие нарушается: |{ x₁, x₂, x₄, x₅, x₆ }| > |{ y₁, y₃, y₄, y₆ }|, а также объединение пяти подмножеств S_1, S_2, S_4, S_5, S₆ содержит только четыре

элемента p₁, p₃, p₄, p₆. Следовательно, трансверсаль существует только в первом случае.

Рассмотрим алгоритм нахождения максимального паросочетания в двудольном графе G = (X U Y,E) [6]. Построим транспортную сеть, в

качестве вершин которой возьмем элементы множеств X и Y, добавив к ним

исток s и сток t. Соединим s с каждой вершиной x_j ÎX дугой (s, x_j) с пропускной способностью, равной 1, а каждую вершину y_j ÎY с t дугой (y_j,t) с пропускной способностью, также равной 1, а каждую вершину x_j ÎX с y_j ÎY

дугой (x_j,y_j), если y_j Î Гx_j, с пропускной способностью, равной ∞. На рис.19

изображена транспортная сеть, соответствующая двудольному графу на рис.18.

Нетрудно заметить, что число ребер в максимальном паросочетании равно величине максимального потока в построенной таким образом транспортной сети. Используя алгоритм Эдмондса-Карпа, можно найти максимальное паросочетание за о(m²n) шагов, где m - число дуг, n - число вершин в построенной транспортной сети. Однако особый вид этой сети позволяет построить более эффективный алгоритм, который рассматривается ниже и носит название алгоритма Хопкрофта-Карпа.

 

x₁ ∞ y₁

x₁ ○ ○ y₁ ○ ○ 1

1 x₂ ∞∞ y₂

x₂ ○ ○ y₂ 1 ○ ○ 1

1 x₃ ∞ y₃ 1

x₃ ○ ○ y₃ ○ ○ ○ ○

1 x₄ ∞ y₄ 1

x₄ ○ ○ y₄ ○ ○

1 x₅ ∞ y₅ 1

x ₅ ○ ○ y₅ ○ ○

 

 

Рис. 18 Рис. 19

Пусть M – паросочетание в графе G = (X U Y,E). Добавляющим путем P по отношению к M называется такой путь между ненасыщенными вершинами

x_j ÎX и y_j ÎY, ребра которого поочередно входят в E \ M и M. Если найдется добавляющий путь P, томожно построить паросочетание M’ = (M\P) U (P\M),

которое имеет на одно ребро больше, чем паросочетание M. Выбрав ненасыщенную вершину в X, можно строить дерево с чередующимися ребрами

до тех пор, пока не найдется P -добавляющий путь. Если не удается построить

дерево с корневой вершиной u, один из путей в котором является P – добавляющим, то это соответствует нарушению условия теоремы Холла.

Пример 7. Пусть необходимо построить совершенное паросочетание в графе

на рис.20. Начальное паросочетание M = {(x₂ , y₁), (x₃ , y₂)}

 

 

x₁ ○ ○ y₁ x₁

○

x₂ ○ ○ y₂ y₁ y₂

○ ○

x₃ ○ ○ y₃ ÎM

x₂ ○ ○ x₃

x₄ ○ ○ y₄

y₃ ○

x ₅ ○ ○ y₅

 

 

Рис.20 Рис.21

 

x₁ ○ ○ y₁ ○ x₄

x₂ ○ ○ y₂ ○ y₃

x₃ ○ ○ y₃ ○ x₂

y₁ y₂

x₄ ○ ○ y₄ ○ ○

x ₅ ○ ○ y₅ x₁ ○ ○ x₃

 

 

Рис.22 Рис.23

 

Выбираем вершину x₁, которая в паросочетании M ненасыщена, и пытаемся построить P – добавляющий путь с начальной вершиной x₁ . На рис.21 ребра начального паросочетания M изображены непрерывными линиями. Построение дерева с чередующимися ребрами заканчивается при построении

P – добавляющуго пути { x₁, y₁, x₂, y₃ }. Новое паросочетание M’ = {(x₁ , y₁),

(x₂ , y₃), (x₃ , y₂)} на рис.22 содержит на одно ребро больше, чем паросочетание M.

Теперь выбираем вершину x₄ и строим дерево с чередующимися ребрами до тех пор, пока это возможно. Построение дерева заканчивается на этапе, изображенном на рис.23. При этом не удается построить P – добавляющий путь. Вершины { x₁, x₂, x₃, x₄ } и { y₁, y₂, y₃ }, включенные в дерево, образуют подмножества S и ГS, на которых нарушается условие теоремы Холла. Таким образом, граф на рис.20 не имеет совершенного паросочетания.

Доказано [7], что число фаз алгоритма Хопкрофта-Карпа не превышает 2√ s +1,

где s – наибольшая мощность паросочетания в графе. Под фазой алгоритма понимается построение добавляющего пути P и увеличение паросочетания

M’ = (M\P) U (P\M).

Оценим сложность алгоритма Хопкрофта-Карпа. Каждая фаза алгоритма имеет сложность о(n²), которая определяется мощностью входных данных. Умножая на число фаз, окончательно получим вычислительную сложность алгоритма - о(n^5/2), где n - число вершин двудольного графа.

Рассмотрим один из вариантов задачи о назначении. Пусть имеется n рабочих { x₁, x₂, ..., x_n } и n видов работ { y₁, y₂, ...,y_n }, причем каждый рабочий может выполнять любой вид работы. Каждому назначению сопоставим число, которое оценивает эффективность работы рабочего x_i при выполнении задания y_j. Требуется назначить рабочих на различные работы по одному таким образом, чтобы максимизировать общую эффективность.

Построим двудольный граф G = (X U Y,E), в котором X - множество вершин, представляющих рабочих, Y - множество вершин, представляющих работы, причем для всех x_i и y_j существует ребро (x_i, y_j). Припишем каждому ребру (x_i, y_j) вес w_i,j = w (x_i, y_j), который показывает эффективность выполнения работы y_j рабочим x_i. Тогда задача об оптимальном значении соответствует

задаче определения в таком взвешенном графе совершенного паросочентания с максимальным весом. Такое паросочетание называется оптимальным. Рассмотрим алгоритм сложности о(n⁴), предложенный Каном и Мункресом [2] для решения задачи об оптимальном назначении.

Допустимой вершинной разметкой называется функция f, определенная на множестве X U Y и удовлетворяющая условию f (x)+ f (y) ≥ w (x, y). Нетрудно

заметить, что допустимая вершинная разметка всегда существует, независимо

от веса ребер. Для этого достаточно положить

 

f (x) = max { w (x, y) }, x ÎX

y ÎY

 

f (y) = 0, y ÎY

Обозначим через E_f подмножество ребер графа, для которых выполняется условие f (x)+ f (y) = w (x, y). Обозначим через G_f подграф, включающий те и только те ребра, которые принадлежат E_f.

Работа алгоритма начинается с произвольной допустимой вершинной разметки f. Затем строится подграф равенств G_f и находится максимальное паросочетание M в G_f. Если подграф G_f имеет совершенное паросочетание, то оно и является оптимальным. Если G_f не имеет совершенного паросочетания, то строится новая допустимая вершинная разметка и новый подграф равенств, в котором строится максимальное паросочетание. Для построения максимального паросочетания используется ранее рассмотренный алгоритм. В этом алгоритме, если совершенного паросочетания построить не удается, то имеем дерево с чередующимися ребрами, в котором не существует добавляющего пути и для некоторого S Ì X выполняется неравенство | S| >|ГS|. Новая допустима вершинная разметка вычисляется следующим образом:

f (z) - d_f , z ÎS

f’ (z) = f (z) + d_f , z ÎГS

f (z) в остальных случаях,

где d_f = min{f (x)+ f (y) - w (x, y)}

x ÎS

y ÎГS

 

Пример 8. Построить оптимальное паросочетание для двудольного графа, заданного матрицей весов:

 

5 4 4 3

W = 4 3 3 2

3 2 2 1

2 1 1 1