Алгоритм Гопкрофта-Карпа: различия между версиями

[непроверенная версия]

Версия 00:09, 25 июня 2015

Содержание

1 Свойства и структура алгоритмов
2 Программная реализация алгоритмов
3 Литература

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм Гопкрофта-Карпа^[1] предназначен для решения задачи о назначениях в случае единичных цен. По заданному двудольному графу алгоритм находит максимальное паросочетание за время [math]O(m \sqrt{n})[/math].

1.2 Математическое описание

Граф [math]G = (V, E)[/math] называется двудольным, если его вершины можно разделить на две части [math]V = X \sqcup Y[/math], так что каждое ребро [math]e \in E[/math] соединяет вершины из [math]X[/math] и [math]Y[/math]. Набор рёбер [math]M \subseteq E[/math] называется паросочетанием, если каждая вершина [math]v \in V[/math] принадлежит не более чем одному ребру из [math]M[/math]. Требуется найти максимальное паросочетание – паросочетание с максимально возможным числом рёбер.

Вершина [math]v \in V[/math] называется свободной, если она не принадлежит ни одному ребру из [math]M[/math]. Простой путь

[math] P: e_1 = (v_1, v_2), e_2 = (v_2, v_3), \ldots, e_{2k-1} = (v_{2k-1}, v_{2k}) [/math]

называется увеличивающей цепью, если его концы [math]v_1[/math] и [math]v_{2k}[/math] – свободные вершины, а каждое второе ребро принадлежит текущему паросочетанию:

[math] e_2, e_4, \ldots, e_{2k-2} \in M. [/math]

Паросочетание [math]M[/math] является максимальным, если для него не существует увеличивающей цепи.

Множество [math]M'[/math], полученное заменой в [math]M[/math] рёбер [math]e_2, e_4, \ldots, e_{2k-2}[/math] на рёбра [math]e_1, e_3, \ldots, e_{2k-1}[/math], является паросочетанием и содержит на одно ребро больше, чем [math]M[/math]. Множество [math]M' = M \mathop{\Delta} P[/math], где [math]\mathop{\Delta}[/math] обозначает операцию симметрической разности множеств.

На каждом шаге алгоритма Гопкрофта-Карпа строится максимальное по включению множество кратчайших увеличивающих цепей [math]\{ P_1, \ldots, P_q \}[/math], не пересекающихся по вершинам, и текущее паросочетание [math]M[/math] заменяется на [math]M = M \mathop{\Delta} P_1 \mathop{\Delta} P_2 \mathop{\Delta} \dots \mathop{\Delta} P_q[/math]. Гарантируется, что число шагов не превышает [math]2 (\sqrt{\mu} + 1) = O(\sqrt{n})[/math], где [math]\mu[/math] – число рёбер максимального паросочетания.

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

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Описание схемы реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Описание ресурса параллелизма алгоритма

1.9 Описание входных и выходных данных

1.10 Свойства алгоритма

2 Программная реализация алгоритмов

2.1 Особенности реализации последовательного алгоритма

2.2 Описание локальности данных и вычислений

2.3 Возможные способы и особенности реализации параллельного алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

Java: JGraphT (класс HopcroftKarpBipartiteMatching).

3 Литература

↑ Hopcroft, John E, and Richard M Karp. “An $N^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing 2, no. 4 (1973): 225–31. doi:10.1137/0202019.

[1] Hopcroft, John E, and Richard M Karp. “An $N^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing 2, no. 4 (1973): 225–31. doi:10.1137/0202019.

[1]

@@ Строка 5: / Строка 5: @@
 === Математическое описание ===
+Граф <math>G = (V, E)</math> называется ''двудольным'', если его вершины можно разделить на две части <math>V = X \sqcup Y</math>, так что каждое ребро <math>e \in E</math> соединяет вершины из <math>X</math> и <math>Y</math>. Набор рёбер <math>M \subseteq E</math> называется ''паросочетанием'', если каждая вершина <math>v \in V</math> принадлежит не более чем одному ребру из <math>M</math>. Требуется найти '''максимальное паросочетание''' – паросочетание с максимально возможным числом рёбер.
+Вершина <math>v \in V</math> называется свободной, если она не принадлежит ни одному ребру из <math>M</math>. Простой путь
+:<math>
+        P: e_1 = (v_1, v_2), e_2 = (v_2, v_3), \ldots, e_{2k-1} = (v_{2k-1}, v_{2k})
+</math>
+называется ''увеличивающей цепью'', если его концы <math>v_1</math> и <math>v_{2k}</math> – свободные вершины, а каждое второе ребро принадлежит текущему паросочетанию:
+:<math>
+        e_2, e_4, \ldots, e_{2k-2} \in M.
+</math>
+Паросочетание <math>M</math> является максимальным, если для него не существует увеличивающей цепи.
+Множество <math>M'</math>, полученное заменой в <math>M</math> рёбер <math>e_2, e_4, \ldots, e_{2k-2}</math> на рёбра <math>e_1, e_3, \ldots, e_{2k-1}</math>, является паросочетанием и содержит на одно ребро больше, чем <math>M</math>. Множество <math>M' = M \mathop{\Delta} P</math>, где <math>\mathop{\Delta}</math> обозначает операцию симметрической разности множеств.
+На каждом шаге алгоритма Гопкрофта-Карпа строится максимальное по включению множество кратчайших увеличивающих цепей <math>\{ P_1, \ldots, P_q \}</math>, не пересекающихся по вершинам, и текущее паросочетание <math>M</math> заменяется на <math>M = M \mathop{\Delta} P_1 \mathop{\Delta} P_2 \mathop{\Delta} \dots \mathop{\Delta} P_q</math>. Гарантируется, что число шагов не превышает <math>2 (\sqrt{\mu} + 1) = O(\sqrt{n})</math>, где <math>\mu</math> – число рёбер максимального паросочетания.
+Для поиска максимального множества кратчайших увеличивающих цепей применяется [[Поиск в ширину (BFS)|поиск в ширину]] с последующим [[Поиск в глубину (DFS)|поиском в глубину]].
 === Вычислительное ядро алгоритма ===
 === Макроструктура алгоритма ===