Файл: Дискретная математика.pdf

Глава 3

ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ НА ГРАФАХ

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Двуд´ольный граф, или бигр´аф, — это математический термин тео-
рии графов. Обыкновенный граф L

=

(X,U) называется двудоль-

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

′

и X

′′

так,

чтобы никакие вершины из одного и того же подмножества не бы-
ли смежны, т. е.

X

= X

′

∪

X

′′

;

X

′

∩

X

′′

= ∅

и ∀x, y

∈ X

[ ̃

xy

∈ U

⇒ (x ∈ X

′

& y

∈ X

′′

) ∨ (x ∈ X

′′

& y

∈ X

′

)].

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Часто двудольный граф записывают в виде L

=

(X

′

, X

′′

, U

).

Матрица смежности двудольного графа полностью определяется своей прямо-

угольной подматрицей, строки которой отвечают вершинам множества X

′

, а столб-

цы — X

′′

.

Двудольный граф K

m

=

(X,Y,W), в котором ∣X∣ = ∣Y∣ = ∣W∣ и никакие два ребра

не смежны, называется паросочетанием. Отображение

∆, которое каждой вершине

множества X относит вершину множества Y , здесь является взаимно однозначным
соответствием между этими множествами.

Одной из важных в прикладном отношении задач теории графов является за-

дача нахождения наибольшего паросочетания, которая формулируется следующим

3.2 Венгерский алгоритм нахождения
максимального паросочетания в двудольном графе

47

образом: для данного графа L найти наибольшее натуральное число m

= π

(L), при

котором существует паросочетание K

m

, являющееся частью L.

Если L — двудольный граф, то под его паросочетанием понимается часть K

m

=

=

(Y

′

, Y

′′

, W

′

), удовлетворяющая условию: Y

′

⊆ X

′

& Y

′′

⊆ X

′′

и W

′

∣Y

′

∣ = ∣Y

′′

∣ = ∣W

′

∣,

и для любых w

j

, w

i

∈ W

′

справедливо: w

j

∩

w

i

= ∅.

Определить

π

(L) — это значит выяснить, какое наибольшее количество вершин

множества X

′

можно взаимно однозначно отобразить в X

′′

при помощи рёбер из W .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Теорема Кёнига—Орэ:

Все множество X

′

биграфа

(X

′

, X

′′

, U

) можно взаимно однозначно

отобразить в X

′′

при помощи рёбер U тогда и только тогда, когда

∀

A

⊆ X

′

(∣∆A∣ ⩾ ∣A∣).

Здесь

∆A — подмножество вершин множества X

′

, смежных с вер-

шинами из A.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Свойством, лежащим в основе определения двудольного графа,
может обладать любой, не только обыкновенный, граф. Именно,
граф L

(X,U;P) называется бихроматическим (или двудольным),

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

Из определения бихроматического графа следует, что все его вершины можно

раскрасить двумя цветами так, что смежные вершины будут покрашены в разные
цвета.

. . . . . . . . . . . . . . . . . . . . . . . . .

Выводы

. . . . . . . . . . . . . . . . . . . . . . . . .

Очевидно, что граф является бихроматическим тогда и только тогда, когда он

не содержит петель, а его скелет есть двудольный граф.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2 Венгерский алгоритм нахождения
максимального паросочетания в двудольном графе

Венгерский алгоритм (авторы — Эгервари 1931, Кун 1953) предназначен для

решения так называемых задач о назначении, которые в свою очередь в своем

48

Глава 3. Экстремальные задачи на графах

простейшем виде сводятся к нахождению наибольшего паросочетания у заданного
двудольного графа.

Рассмотрим венгерский алгоритм на следующем примере.

. . . . . . . . . . . . . . . . . . . . . .

Пример 3.1

. . . . . . . . . . . . . . . . . . . . .

Пусть имеется девять иностранных групп туристов Т

1

, . . ., Т

9

, причем гости

группы Т

1

говорят на языке А, гости Т

2

— на Б, Т

3

— на В, Т

4

— на А, Т

5

— на Б, Т

6

—

на Г, Т

7

— на E, Т

8

— на Г, Т

9

— на Д; в свою очередь бюро «Интурист» распола-

гает в данный момент десятью свободными переводчиками П

1

, . . ., П

10

, владею-

щими такими иностранными языками: П

1

— языком

(А,В); П

2

—

(А,Г); П

3

—

(А);

П

4

—

(Б,В,Е); П

5

—

(А,В); П

6

—

(А); П

7

—

(Г,Д); П

8

—

(Б,Д); П

9

—

(Б,Г,Е); П

10

—

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

Построим двудольный граф L

=

(X

1

, X

2

, U

) (рис. 3.1), в котором вершинам

множества X

1

соответствуют переводчики П

1

, П

2

, . . ., П

10

, вершинам X

2

— группы

туристов Т

1

, Т

2

, . . ., Т

9

. Смежность вершины П

i

∈ X

1

с вершиной Т

i

∈ X

2

означает

владение i-го переводчика языком j-ой группы. Требуется найти в L паросочетание
с наибольшим количеством

π

(L) рёбер.

Рис. 3.1 – Двудольный граф L

=

(X

1

, X

2

, U

)

Теорема Кёнига—Орэ позволяет вычислить наибольшее значение

π

(L) паросо-

четания:

π

(L) = ∣X

1

∣ − max (∣A∣ − ∣∆A∣),

где

∆A — подмножество вершин множества X

2

, смежных с вершинами из A

⊆ X

1

.

Для решения данной задачи представим граф L (рис. 3.1) матрицей смежности

B

=

(b

i j

) (табл. 3.1).

Строки матрицы B соответствуют элементам множества X

1

(переводчики), столб-

цы — элементам множества X

2

(туристы).

Элементы b

i j

=

{0,1}; b

i j

= 1, если i-й переводчик может обслуживать j-ю груп-

пу туристов, b

i j

= 0, в противном случае.

3.2 Венгерский алгоритм нахождения
максимального паросочетания в двудольном графе

49

Таблица 3.1 – Матрица смежности графа L

B

Т

1

Т

2

Т

3

Т

4

Т

5

Т

6

Т

7

Т

8

Т

9

П

1

1

1

1

П

2

1

1

1

1

П

3

1

1

П

4

1

1

1

1

П

5

1

1

1

П

6

1

1

П

7

1

1

1

П

8

1

1

1

П

9

1

1

1

1

1

П

10

1

1

1

Алгоритм решения состоит в следующем. Пусть некоторое паросочетание K

=

=

(Y

1

, Y

2

, V

) уже построено (в начальный момент это пустое паросочетание, V = ∅).

Ребра графа L, принадлежащие V , назовем «сильными», а ребра из U

/V — «слабы-

ми». Вершину, инцидентную сильному ребру, будем называть насыщенной, а вер-
шину, не инцидентную сильному ребру, — ненасыщенной.

Под «чередующейся цепью» будем понимать простую цепь, в которой слабые

рёбра строго чередуются с сильными; такую цепь назовем тонкой. Примем, что её
длина отрицательна, если начальная и конечная вершины — обе ненасыщенные.

Ясно, что при наличии у графа L с заданным паросочетанием K хотя бы одной

тонкой чередующейся цепи Q можно вместо K построить новое паросочетание K

′

,

содержащее на одно ребро больше. Для этого надо все слабые ребра цепи Q сде-
лать сильными, а сильные — слабыми, не трогая рёбер вне Q. Иначе говоря, надо
удалить из множества V все те рёбра, которые принадлежат цепи Q, и к остатку
добавить рёбра Q, принадлежащие U

/V. В свою очередь, если у графа L с паросо-

четанием K

′

опять есть тонкая чередующаяся цепь, то аналогично предыдущему

можно получить паросочетание K

′′

, имеющее уже на два ребра больше исходного.

Оказывается, что если на каком-то этапе тонких чередующихся цепей боль-

ше нет, то полученное паросочетание K

*

— наибольшее, т. е. содержит ровно

π

(L)

ребер.

Процедура поиска тонкой чередующейся цепи в графе с заданным паросо-

четанием состоит в следующем: выбираем в X

1

любую ненасыщенную вершину

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

1

, которая не инцидентна ни одному еще не пройденному слабому ребру, воз-

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

2

и мы получим искомую цепь (она состоит из рёбер,

отмеченных ровно одним штрихом), либо этот процесс приведёт нас в исходную
вершину и тогда надо начать аналогичный поиск с другой ненасыщенной вершины
множества X

1

.

В нашем конкретном примере всё решение выглядит следующим образом.

1. Задаём произвольно паросочетание K

=

{(П

3

Т

1

), (П

2

Т

4

)}.

50

Глава 3. Экстремальные задачи на графах

2. Фиксируем насыщенные вершины — П

3

, П

2

и Т

1

, Т

4

.

3. Строим тонкую чередующуюся цепь Q: П

1

−

Т

1

−

П

3

−

Т

4

−

П

2

−

Т

8

, которая

начинается и заканчивается в ненасыщенных вершинах П

1

и Т

8

и содержит

сильные рёбра

(П

3

−

Т

1

) и (П

2

−

Т

4

).

4. Переименуем рёбра построенной тонкой цепи: теперь рёбра

(П

3

−

Т

1

)

и

(П

2

−

Т

4

) — слабые, а рёбра (П

1

−

Т

1

),(П

3

−

Т

4

),(П

2

−

Т

8

) соответственно

стали сильными, вершины П

1

, Т

8

— насыщенные. Новое паросочетание K

′

содержит уже три ребра.

5. Находим в графе новые ненасыщенные вершины Т

3

и П

7

, которые смежны

насыщенным концевым вершинам построенной тонкой цепи

П

1

−

Т

1

−

П

3

−

Т

4

−

П

2

−

Т

8

.

6. Строим новую тонкую чередующуюся цепь Q: Т

3

−

П

1

−

Т

1

−

П

3

−

Т

4

−

П

2

−

Т

8

−

П

7

, которая содержит сильные рёбра

(П

1

−

Т

1

),(П

3

−

Т

4

),(П

2

−

Т

8

).

7. Переименуем рёбра построенной тонкой чередующейся цепи: теперь рёбра

(П

1

−

Т

1

),(П

3

−

Т

4

),(П

2

−

Т

8

) — слабые, а рёбра (Т

3

−

П

1

),(Т

1

−

П

3

),(Т

4

−

П

2

),(Т

8

−

П

7

) — сильные. Новое паросочетание K

′′

содержит уже четыре

ребра.

8. Присоединим к построенной тонкой чередующейся цепи Т

3

−

П

1

−

Т

1

−

П

3

−

Т

4

−

П

2

−

Т

8

−

П

7

ещё два ребра:

(Т

3

−

П

4

) и (П

7

−

Т

6

) и над новой чередующей-

ся цепью Q

= П

4

−

Т

3

−

П

1

−

Т

1

−

П

3

−

Т

4

−

П

2

−

Т

8

−

П

7

−

Т

6

выполним

преобразование, аналогичное тому, которое описано в п.п. 4–7, увеличив
таким образом паросочетание K

′′

ещё на одно ребро. Новое паросочетание

K

ν

включает сильные рёбра —

(П

4

, Т

3

),(П

1

, Т

1

),(П

3

, Т

4

),(П

2

, Т

8

),(П

7

, Т

6

).

Увеличить длину построенной цепи Q, проходящей через вершины П

4

, Т

3

, П

1

, Т

1

,

П

3

, Т

4

, П

2

, Т

8

, П

7

, Т

6

, нельзя, так как среди ненасыщенных вершин из множества

X

/V, принадлежащих разным подмножествам (X

1

, X

2

), нет инцидентных концевым

вершинам цепи Q.

Увеличить построенное паросочетание K

ν

можно добавлением к нему цепей

длины, равной 1, т. е. рёбер

(П

8

, Т

9

) и (П

9

, Т

5

) или (П

9

, Т

7

) и (П

8

, Т

9

). Тогда коли-

чество рёбер

π

(L) паросочетания K

ν

станет равно 7.

Q

= П

4

, Т

3

, П

1

, Т

1

, П

3

, Т

4

, П

2

, Т

8

, П

7

, Т

6

, П

9

, Т

5

, П

8

, Т

2

(табл. 3.2).

В таблице 3.2 показана матрица смежности B графа L, где знаком «+» помечены

насыщенные вершины графа и элементы b

i j

, соответствующие сильному ребру, т. е.

ребру паросочетания K

ν

, значком «*» помечены концевые вершины чередующейся

цепи Q, знаком «−» помечены элементы b

i j

, соответствующие слабому ребру, т. е.

ребру, которое не входит в паросочетания K

ν

.

Из матрицы видно, что увеличить построенное паросочетание нельзя, так как

оставшиеся ненасыщенные вершины инцидентны разным рёбрам.

Однако согласно теореме Кёнига—Холла для данного графа

π

(L) = 8. Дей-

ствительно, если мы в построенной тонкой чередующейся цепи Q ребро

(П

4

, Т

3

)

заменим ребром

(П

5

, Т

3

), то сможем построить другую чередующуюся цепь Q, ко-

торая проходит через вершины П

5

, Т

3

, П

1

, Т

1

, П

6

, Т

4

, П

2

, Т

6

, П

7

, Т

8

, П

9

, Т

5

(табл. 3.3,

рис. 3.2).