Учебное пособие: Дискретная математика
Глава 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).