|
|
Пишет ringill (![[info]](http://lj.rossia.org/img/userinfo.gif){kind=small} ringill)@ 2005-08-23 23:36:00 |
 |
|
 |
|
|
|
|
|
|
 |
|
 |
Наибольшее паросочетание в двудольном графе
[тут ничего нового]
Паросочетание (matching) -- произвольное подмножество попарно несмежных ребер графа.
Максимальное паросочетание (maximal matching) -- паросочетание, которое не содержится в паросочетании с большим числом ребер
Наибольшее паросочетание (maximum matching) -- паросочетание, в котором число рёбер наибольшее среди всех паросочетаний графа.
Двудольный (bipartite) граф -- такой граф, вершины которого (V) можно разделить на два множества (V+ и V-), так чтобы вершины каждого из множеств были попарно несмежны.
Наибольшее паросочетание в любом графе можно найти за полиномиальное время (так написано в известной книге Гэри и Джонсона в комментарии к задаче ТГ 10).
Ниже -- алгоритм нахождения наибольшего паросочетания в связном двудольном графе за O(mn), где |V|=n и |E|=m.
Взято из статьи "Matching Algorithms for Bipartite Graphs" (ссылка).
Определение
Пусть есть паросочетание в графе (V, E), обозначим его M (множество рёбер). M-чередующийся путь -- это путь в графе, содержащий поочерёдно рёбра из M и из (E\M).
Теорема
Паросочетание M является наибольшим тогда и только тогда, когда нет невырожденного M-чередующегося пути, начинающегося и заканчивающегося в вершинах, не инцидентных ни одному ребру из М.
Лемма
Если такой путь есть (обозначим его рёбра как P), то можно получить разбиение большее, чем M, следующим образом: M' = M ^ P (симметрическая разность, или XOR).
Алгоритм прост -- начать с пустого паросочетания M={} и постепенно увеличивать его, находя M-чередующийся путь из теоремы и выполняя операции, указанные в лемме. Когда путь найти будет нельзя, это будет означать, что M -- наибольшее паросочетание.
Каждый шаг увеличивает M как минимум на одно ребро. Это значит, что всего шагов будет не больше чем n/2.
Нахождение M-чередующегося пути осуществляется поиском в ширину (BFS). В качестве начальной вершины для поиска выбирается, например, свободная (не инцидентная ни одному ребру из M) вершина из V+. Если итерации BFS нумеровать с единицы, то на нечётных итерациях будем рассматривать только рёбра из (E\M), а на чётных -- только из M. Таким образом, если во фронте BFS окажется свободная вершина из V-, то получившийся путь к ней будет M-чередующимся путём со свободными началом и концом.
Если BFS не обнаружит свободной вершины в V-, значит M-чередующегося пути нет, и текущее разбиение является наибольшим.
При условии связности графа BFS займёт O(m) времени. А общее время работы = O(m*n).
В статье приводится также модификация этого алгоритма, позволяющая снизить сложность до O(m * sqrt(n)). Суть модификации в том, чтобы при BFS не останавливаться на первой попавшейся свободной вершине из V-, а найти все и выбрать самую "далёкую", т.е. которая даст самый длинный путь.
[тут ничего нового]
Паросочетание (matching) -- произвольное подмножество попарно несмежных ребер графа.
Максимальное паросочетание (maximal matching) -- паросочетание, которое не содержится в паросочетании с большим числом ребер
Наибольшее паросочетание (maximum matching) -- паросочетание, в котором число рёбер наибольшее среди всех паросочетаний графа.
Двудольный (bipartite) граф -- такой граф, вершины которого (V) можно разделить на два множества (V+ и V-), так чтобы вершины каждого из множеств были попарно несмежны.
Наибольшее паросочетание в любом графе можно найти за полиномиальное время (так написано в известной книге Гэри и Джонсона в комментарии к задаче ТГ 10).
Ниже -- алгоритм нахождения наибольшего паросочетания в связном двудольном графе за O(mn), где |V|=n и |E|=m.
Взято из статьи "Matching Algorithms for Bipartite Graphs" (ссылка).
Определение
Пусть есть паросочетание в графе (V, E), обозначим его M (множество рёбер). M-чередующийся путь -- это путь в графе, содержащий поочерёдно рёбра из M и из (E\M).
Теорема
Паросочетание M является наибольшим тогда и только тогда, когда нет невырожденного M-чередующегося пути, начинающегося и заканчивающегося в вершинах, не инцидентных ни одному ребру из М.
Лемма
Если такой путь есть (обозначим его рёбра как P), то можно получить разбиение большее, чем M, следующим образом: M' = M ^ P (симметрическая разность, или XOR).
Алгоритм прост -- начать с пустого паросочетания M={} и постепенно увеличивать его, находя M-чередующийся путь из теоремы и выполняя операции, указанные в лемме. Когда путь найти будет нельзя, это будет означать, что M -- наибольшее паросочетание.
Каждый шаг увеличивает M как минимум на одно ребро. Это значит, что всего шагов будет не больше чем n/2.
Нахождение M-чередующегося пути осуществляется поиском в ширину (BFS). В качестве начальной вершины для поиска выбирается, например, свободная (не инцидентная ни одному ребру из M) вершина из V+. Если итерации BFS нумеровать с единицы, то на нечётных итерациях будем рассматривать только рёбра из (E\M), а на чётных -- только из M. Таким образом, если во фронте BFS окажется свободная вершина из V-, то получившийся путь к ней будет M-чередующимся путём со свободными началом и концом.
Если BFS не обнаружит свободной вершины в V-, значит M-чередующегося пути нет, и текущее разбиение является наибольшим.
При условии связности графа BFS займёт O(m) времени. А общее время работы = O(m*n).
В статье приводится также модификация этого алгоритма, позволяющая снизить сложность до O(m * sqrt(n)). Суть модификации в том, чтобы при BFS не останавливаться на первой попавшейся свободной вершине из V-, а найти все и выбрать самую "далёкую", т.е. которая даст самый длинный путь.
