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

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

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

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