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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



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

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

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, так как существует единственная положительная разность

 

|{ x1, x2, x3 }| - | Г { x1, x2, x3 }| = |{ x1, x2, x3 }| - |{ y1, y2 }| = 1

 

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

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

M = {(x1, y1), (x2, y2), (x3, y4), (x4, y3)}.

 

X Y X Y

○ y1 ○ y1

x1 ○ x1

○ y2 ○ y2

x2 ○ x2

○ y3 ○ y3

x3 ○ x3

○ y4 ○ y4

x4 ○ x4

○ y5 ○ y5

 

 

Рис. 14 Рис. 15

 

 

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

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

Пусть P -непустое множество, а S = { S1, S2,…, Sk} – семейство

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

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

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

из каждого Si.

Например, если P= {1,2,3,4,5,6}, S1= {1,3,4}, S2= {1,3,4}, S3= {1,2,5}, S4= {3,6},

то T = {1,3,2,6} множества S1, S2, S3,S4.

С другой стороны, если S5= {3,6}, S6= {4}, то для семейства S1, S2, S3,S4,S5,S6

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

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

Поставим во взаимно однозначное соответствие элементы множества вершин двудольного графа X элементам семейства S (xi Si), а элементам множества Y – элементы множества P (pi yi). Ребро (xi , yj) Î E тогда и только тогда, когда pi Î Si.

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

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

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

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

рис.17 – для случая, когда S ={S1, S2, S3,S4,S5,S6}

 

○ y1 (p1) x1 ○ ○ y1

(S1) x1

○ y2 (p2) x2 ○ ○ y2

(S2) x2

○ y3 (p3) x3 ○ ○ y3

(S3) x3

○ y4 (p4) x4 ○ ○ y4

(S4) x4

○ y5 (p5) x 5 ○ ○ y5

 

○ y6 (p6) x 6 ○ ○ y6

 

Рис. 16 Рис. 17

 

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

условие нарушается: |{ x1, x2, x4, x5, x6 }| > |{ y1, y3, y4, y6 }|, а также объединение пяти подмножеств S1, S2, S4, S5, S6 содержит только четыре

элемента p1, p3, p4, p6. Следовательно, трансверсаль существует только в первом случае.

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

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

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

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

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

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

 

x1 y1

x1 ○ ○ y1 ○ ○ 1

1 x2 ∞∞ y2

x2 ○ ○ y2 1 ○ ○ 1

1 x3 y3 1

x3 ○ ○ y3 ○ ○ ○ ○

1 x4 y4 1

x4 ○ ○ y4 ○ ○

1 x5 y5 1

x 5 ○ ○ y5 ○ ○

 

 

Рис. 18 Рис. 19

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

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

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

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

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

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

на рис.20. Начальное паросочетание M = {(x2 , y1), (x3 , y2)}

 

 

x1 ○ ○ y1 x1

x2 ○ ○ y2 y1 y2

○ ○

x3 ○ ○ y3 ÎM

x2 ○ ○ x3

x4 ○ ○ y4

y3

x 5 ○ ○ y5

 

 

Рис.20 Рис.21

 

x1 ○ ○ y1 ○ x4

x2 ○ ○ y2 ○ y3

x3 ○ ○ y3 ○ x2

y1 y2

x4 ○ ○ y4 ○ ○

x 5 ○ ○ y5 x1 ○ ○ x3

 

 

Рис.22 Рис.23

 

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

P – добавляющуго пути { x1, y1, x2, y3 }. Новое паросочетание M’ = {(x1 , y1),

(x2 , y3), (x3 , y2)} на рис.22 содержит на одно ребро больше, чем паросочетание M.

Теперь выбираем вершину x4 и строим дерево с чередующимися ребрами до тех пор, пока это возможно. Построение дерева заканчивается на этапе, изображенном на рис.23. При этом не удается построить P – добавляющий путь. Вершины { x1, x2, x3, x4 } и { y1, y2, y3 }, включенные в дерево, образуют подмножества S и ГS, на которых нарушается условие теоремы Холла. Таким образом, граф на рис.20 не имеет совершенного паросочетания.

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

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

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

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

Рассмотрим один из вариантов задачи о назначении. Пусть имеется n рабочих { x1, x2, ..., xn } и n видов работ { y1, y2, ...,yn }, причем каждый рабочий может выполнять любой вид работы. Каждому назначению сопоставим число, которое оценивает эффективность работы рабочего xi при выполнении задания yj. Требуется назначить рабочих на различные работы по одному таким образом, чтобы максимизировать общую эффективность.

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

задаче определения в таком взвешенном графе совершенного паросочентания с максимальным весом. Такое паросочетание называется оптимальным. Рассмотрим алгоритм сложности о(n4), предложенный Каном и Мункресом [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

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

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

f (z) - df , z ÎS

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

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

где df = 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



Поделиться:


Последнее изменение этой страницы: 2016-06-28; просмотров: 655; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.211.35.130 (0.078 с.)