Мирзаянов М.Р. Паросочетания и смежные задачи (графы)
Подождите немного. Документ загружается.
Мирзаянов М.Р. Паросочетания и смежные задачи
На рис. 6-7 ненасыщенными являются вершины 1 и 7. В графе
H
действительно
существует цепь из 1 в 7:
(1, 6)(6,2)(2, 7)P
. Следовательно, паросочетание
M
можно
увеличить
*
:M M P
, где
*
M
– увеличенное паросочетание.
Если теперь по графу
G
и паросочетанию
*
M
построить новый ориентированный граф
H
, то в этом графе уже не будет ориентированной цепи из ненасыщенной вершины доли
X
в ненасыщенную вершину доли
Y
. Следовательно, паросочетание
*
M
–
максимальное.
Эти рассуждения подсказывают метод нахождения
M
-удлиняющих цепей (или факта их
отсутствия). Заметим, что существование пути можно проверять за время
(| | | |)O V E
с
помощью поиска в ширину или в глубину.
Так как количество итерация цикла while алгоритма 1 не превосходит
| |
2
V
, то сложность
алгоритма 1 при использования вышеописанной методики составляет
2
(| | | || |)O V V E
.
Следующий алгоритм является своеобразной модификацией алгоритма 1.
Алгоритм 2 (алгоритм Куна)
Вход: неориентированный двудольный граф
( , , )G X Y E
Выход: максимальное паросочетание
Метод:
function MAX_MATCHING_KHUN(
G
)
01
:M
02 for
x X
do
03 Fill(used, FALSE)
04 TRY_KHUN(
x
)
05 return
M
end
11
Мирзаянов М.Р. Паросочетания и смежные задачи
Алгоритм 2 в строке 04 использует функцию TRY_KHUN(
x
).
Функция TRY_KHUN(
x
).
Вход: вершина
x
множества
X
Выход: TRUE или FALSE (найдена ли
M
-удлиняющая цепь из вершины
x
)
Глобальные переменные: двудольный граф
( , , )G X Y E
, паросочетание
M
, булевский
массив used, проиндексиванный элементами множества
X
Метод:
function TRY_KHUN(
x
)
01 if used[
x
] then
02 return FALSE
03 used[
x
] := TRUE
04 for
[ ]
G
y Adj x
do
05 if (
[ ] 0M y
) or (TRY_KHUN(
[ ]M y
)) then
06
[ ]:M y x
07 return TRUE
08 return FALSE
end
В описании функции TRY_KHUN(
x
) используется, что паросочетание
M
хранится в
виде массива, проиндексированного элементами множества
Y
.
0, ;
[ ]
, ( , ) .
если вершина y ненасыщена
M y
x если x y M
Присвоение в строке 06 обозначает, что ребро
( , )x y
добавляется в
M
(при этом из
M
при необходимости удаляется другое ребро инцидентное
y
). Символ
[ ]
G
Adj x
в строке 04
обозначает множество вершин смежных с вершиной
x
в графе
G
. В строке 05
предполагается, что TRY_KHUN(
[ ]M y
) не вызывается, если
[ ] 0M y
(что соответствует
стандартной оптимизации булевских выражений в современных языках
программирования).
Теорема 7. Алгоритм 2 – корректен.
Пусть вершины множества
X
перебираются в порядке
1 2 | |
, ,...,
X
x x x
в стоке 02 алгоритма
2. Ниже символом
*
k
G
будет обозначать граф
G
, из которого удалили вершины
1 2 | |
, ,...,
k k X
x x x
и инцидентные им ребра.
12
Мирзаянов М.Р. Паросочетания и смежные задачи
Покажем, что выполняется следующий инвариант: после
i
-го выполнения строки 04
алгоритма 2 в
M
содержится максимальное паросочетание для графа
*
i
G
. Докажем это
утверждение по индукции. В самом деле, после первой итерации цикла в паросочетании
M
будет содержаться ребро, если и только если вершина
1
x
не изолированная.
Заметим, что TRY_KHUN(
i
x
) фактически пытается найти с помощью поиска в глубину
M
-удлиняющую цепь из
i
x
и, в случае успеха, заменяет
M
на
M P
, где
P
–
найденная цепь, и возвращает TRUE.
Рассмотрим
i
-ую итерацию цикла 02-04. В вызове TRY_KHUN(
i
x
) все рекурсивные
вызовы TRY_KHUN будут только от вершин
j
x
, где
j i
. Максимальное паросочетание
для графа
*
i
G
может быть больше, чем для графа
*
1i
G
максимум на одно ребро. В этом
случае в
*
( )
i
MM G
обязательно найдется ребро инцидентное
i
x
, но так как эта вершина не
насыщена паросочетанием
*
1
( )
i
MM G
, то чтобы перейти от
*
1
( )
i
MM G
к
*
( )
i
MM G
достаточно найти удлиняющую цепочку из вершины
i
x
, что и делает TRY_KHUN(
i
x
).
Таким образом, в предположении, что инвариант верен на
1i
-ой итерации, удалось
доказать, что инвариант сохраняется и на
i
-ой итерации. Значит, инвариант выполняется
на любой итерации, то есть в конце алгоритма, так как
*
| |X
G G
,
M
суть максимальное
паросочетание.
Утверждение 2. Если в процессе алгоритма 2 вершина
v X Y
насытилась некоторым
промежуточным паросочетанием, то
v
останется насыщенной до конца выполнения
алгоритма 2.
Утверждение 3. Если на
i
-ой итерации цикла 02-04 алгоритма 2 вершина
i
x X
не
насытилась в ходе выполнения TRY_KHUN(
i
x
), то
i
x
останется ненасыщенной до
конца выполнения алгоритма 2.
Сложность алгоритма 2 составляет, очевидно, величину
2
(| | | || |)O V V E
. Можно
попытаться оценить его сложность точнее. Предположим
| | | |X Y
, тогда цикл 02-04
выполнится
| |X
раз. Оценим время работы каждого вызова TRY_KHUN(
x
) строки 04.
Каждый вызов TRY_KHUN(
x
) (в том числе и рекурсивные вызовы) на первый взгляд
работают за
(| [ ]|)
G
O Adj x
действий (разумеется, имеются в виду те вызовы, которые
проходят проверку в строке 01). На самом деле, каждая итерация цикла 04-07 либо
соответствует одному ребру из
M
, либо мгновенно успешно завершает вызов (если
13
Мирзаянов М.Р. Паросочетания и смежные задачи
[ ] 0M y
). Поэтому верно, что каждый вызов TRY_KHUN(
x
) работает за
(min(| [ ] |,| |))
G
O Adj x M
. Так как
| | | |M X
, то один вызов TRY_KHUN(
i
x
) (в него
включаются все необходимые рекурсивные вызовы) работает за
2
(min(| |,| | ))O E X
, а,
значит, весь алгоритм 2 выполняется за время
3
(min(| | ,| || |))O X X E
.
Заметим, что можно очень просто сильно ускорить алгоритм 2 (впрочем, как и алгоритм
1). Если в алгоритме 2 строки 01 и 04 немного изменить, то получим следующий
алгоритм.
Алгоритм 3 (модифицированный алгоритм Куна)
Вход: неориентированный двудольный граф
( , , )G X Y E
Выход: максимальное паросочетание
Метод:
function MAX_MATCHING_KHUN_MODIFIRED(
G
)
01(1)
M
:= MAX_MATCHING_HEURISTIC(
G
)
02 for
x X
do
03 Fill(used, FALSE)
04(1) if
[ ] 0M x
then
04(2) TRY_KHUN(
x
)
05 return
M
end
Здесь подразумевается, что MAX_MATCHING_HEURISTIC(
G
) возвращает некоторое
паросочетание (достаточно большое) найденное некоторым быстро работающим
эвристическим методом. Примером такой функции может служить следующая функция.
Алгоритм 4 (эвристический алгоритм нахождения максимального паросочетания)
Вход: неориентированный двудольный граф
( , , )G X Y E
Выход: некоторое паросочетание
Метод:
function MAX_MATCHING_HEURISTIC(
G
)
01
M
:=
02 while в графе
G
есть хотя бы одно ребро do
03 найти неизолированную вершину
v
наименьшей степени
04 найти любое ребро
( , )v v
в графе
G
05
M
:=
( , )M v v
14
Мирзаянов М.Р. Паросочетания и смежные задачи
06 удалить из
G
вершины
,v v
вместе с инцидентными ребрами
07 return
M
end
Этот эвристический метод при использовании приведенной матрицы смежности легко
реализовать за время
(| || |)O X Y
. На самом деле, его можно реализовать значительно
эффективнее. Заметим, что алгоритм 4 дает отличные результаты на случайных графах и
некоторых графах специального вида.
На этом мы заканчиваем изучение вопросов связанных с алгоритмами построения
максимального паросочетания, обойдя наиболее быстрый известный алгоритм
Хопкрофта-Карпа, асимптотическая временная сложность которого составляет
(| | | |)O E V
.
15
Мирзаянов М.Р. Паросочетания и смежные задачи
§6. Построение минимального вершинного покрытия в двудольном графе
В этом параграфе не только будет приведен метод построения
MVC
, но и, наконец,
доказана теорема 5.
Ориентацию ребер двудольного графа
( , , )G X Y E
относительно некоторого
паросочетания
M E
введенную в предыдущем параграфе (см. рис. 6-7) будем называть
естественной.
Сначала приведем алгоритм построения
MVC
, а затем докажем его корректность.
Алгоритм 5 (общий алгоритм нахождения минимального вершинного покрытия)
Вход: неориентированный двудольный граф
( , , )G X Y E
Выход: минимальное вершинное покрытие
U
Метод:
function MIN_VERTEX_COVERING(
G
)
01
M
:= MAX_MATCHING(
G
)
02 построить
( ,H X Y
M
E
) – естественную ориентацию
G
03 найти множество вершин
W
– достижимых
из ненасыщенных вершин
множества
X
в орграфе
H
04
U
:=
( \ ) ( )X W Y W
end
Заметим, что при реализации этого алгоритма граф
H
строить совсем не обязательно.
Например, можно использовать функцию DFS_MVC(
x
), имеющую минимальное
различие с функцией TRY_KHUN(
x
).
Алгоритм 6 (детальный алгоритм нахождения минимального
вершинного покрытия)
Вход: неориентированный двудольный граф
( , , )G X Y E
Выход: минимальное вершинное покрытие
U
Метод:
function MIN_VERTEX _COVERING(
G
)
01
M
:= MAX_MATCHING(
G
)
02 Fill(used_x, FALSE)
03 Fill(used_y, FALSE)
04 for
x X
do
16
Мирзаянов М.Р. Паросочетания и смежные задачи
05 if
x
не насыщенна
M
then
06 DFS_MVC(
x
)
07
U
:= (!used_x)
used_y
end
Функция DFS_MVC(
x
) выглядит следующим образом.
Функция DFS_MVC(
x
).
Вход: вершина
x
множества
X
Выход: пустой (результаты сохраняются в used_x, used_y)
Глобальные переменные: двудольный граф
( , , )G X Y E
, паросочетание
M
, булевские
массивы used_x, used_y проиндексиванные элементами множеств
X
,
Y
соответственно.
Метод:
function DFS_MVC(
x
)
01 if used_x[
x
] then
02 return
03 used_x[
x
] := TRUE
04 for
[ ]
G
y Adj x
do
05 used_y[
y
] := TRUE
06 if
[ ]M y
не равно
0
then
07 DFS_MVC(
[ ]M y
)
end
В строке 06 алгоритма 6 символом !used_x обозначается дополнение множества used_x до
X
. Так как алгоритм 6 является лишь детальным изложением алгоритма 5, то достаточно
доказать только корректность алгоритма 5.
Лемма 2. В произвольном графе
( , )G V E
верно неравенство:
| ( ) | | ( ) |MVC G MM G
.
Доказательство. В самом деле, каждое ребро максимального паросочетания инцидентно
хотя бы одной вершине вершинного покрытие, но все вершины инцидентные
паросочетанию – различны.
Теорема 8. Алгоритм 5 – корректен.
17
Мирзаянов М.Р. Паросочетания и смежные задачи
Доказательство. Докажем, что найденное множество
U
в самом деле образует вершинное
покрытие. Предположим существование такого ребра
( , )x y
, что вершина
x
W
, а
y W
.
Возможен один из двух случаев:
( , )x y
M
и
( , )x y
M
.
Пусть
( , )x y
M
. В этом случае вершина
x
насыщена паросочетанием и попасть в
W
она
может лишь в случае существования некоторой цепи
0 0
, ,...., ,
k k
x y y x
в графе
H
, где
0
x
–
ненасыщенная вершина, а
k
x
=
x
. Так как переходить из доли
Y
в
X
можно только по
ребрам из
M
, получаем, что
k
y y
, то есть вершина
y W
. Противоречие.
Предположим
( , )x y
M
. В этом случае из
x W
немедленно следует
y W
. Получаем
противоречие.
Итак, множество
U
в самом деле является вершинным покрытием.
Покажем его минимальность. В силу леммы 2 достаточно доказать, что
| | | |U M
.
Очевидно, каждое ребро из множества
M
инцидентно не более чем одной вершине из
множества
U
. Покажем, что все вершины из
U
инцидентны какому-то ребру из
паросочетания
M
. Предположим противное, то есть допустим, что в множестве
U
существует ненасыщенная вершина. Очевидно, что эту вершина не принадлежит доли
X
(так как все ненасыщенные вершины доли
X
достижимы из себя и, следовательно,
принадлежат
W
). Доли
Y
эта вершина принадлежать тоже не может, так как это
обозначало бы наличие в
H
M
-увеличивающей цепи, заканчивающейся в этой вершине.
Таким образом,
| | | |U M
. По лемме 2 получаем, что
| | | |U M
и
U
– минимальное
вершинное покрытие.
Заметим, что в ходе доказательства теоремы 8 доказана теорема 5.
18