Алгоритм Куна для поиска максимального паросочетания

Теорема:

Если из вершины [math]x[/math] не существует дополняющей цепи относительно паросочетания [math]M[/math], то если паросочетание [math]M'[/math] получается из [math]M[/math] изменением вдоль дополняющей цепи, то из [math]x[/math] не существует дополняющей цепи в [math]M'[/math].

Доказательство:

[math]\triangleright[/math]

Доказательство от противного! Рассмотрим изменения, которые мы внесли в [math]M[/math] вдоль дополняющей цепи, чтобы получить паросочетание [math]M'[/math]. В этой цепи все промежуточные вершины были насыщенными, а концы свободные. После изменения вдоль этой цепи все вершины, лежащие на этой цепи станут насыщенными. Допустим, что из [math]x[/math] появилась дополняющая цепь относительно [math]M'[/math]. Тогда появившаяся дополняющая цепь должна проходить хотя бы через одну из концевых вершин в той дополняющей цепи, относительно которой вносили изменения, поскольку иначе такая же дополняющая цепь была и в паросочетании [math]M[/math]. Однако поскольку в паросочетании [math]M[/math] концевые вершины цепи, вдоль которой вносили изменения, не насыщены, то из вершины [math]x[/math] в паросочетании [math]M[/math] есть все равно есть дополняющая цепь. Надо рассмотреть часть дополняющей цепи в [math]M'[/math], ограниченную концом текущей дополняющей цепи и концом той дополняющей цепи, вдоль которой вносили изменения, такую что вершина [math]x[/math] будет промежуточной. Легко заметить, что в такой цепи все промежуточные вершины насыщенные, а концы свободны, поэтому она является дополняющей. Значит, мы пришли к противоречию, поскольку в паросочетании [math]M[/math] нет дополняющих цепей из вершины [math]x[/math].

[math]\triangleleft[/math]

Алгоритм

Пусть дан двудольный граф [math]G(V, E)[/math] и требуется найти максимальное паросочетание в нём. Обозначим доли исходного графа как [math]L[/math] и [math]R[/math].
1) Просматриваем вершины [math]s[/math] из доли [math]L[/math].

2) Будем искать дополняющую цепь из [math]s[/math](например, поиском в глубину).

3) Если цепь найдена, инвертируем все ребра на этой цепи.

В любой момент времени текущим паросочетанием будет множество ребер, направленных из [math]R[/math] в [math]L[/math]. Корректность работы алгоритма следует из теоремы Бержа и доказанной выше теоремы.

Псевдокод

 bool  dfs(x):
   vis[x] = true
   for [math]xy \in E[/math]:
       k = py[y]
       if (k == -1) or ((not vis[k]) and (dfs(k))):
           py[y] = x
           return true
   return false
 Kuhn():
   py[] = -1
   for [math]s \in L[/math]:
       vis[] = false
       dfs(s)

Время работы

Итак, алгоритм Куна можно представить как серию из |[math]L[/math]| запусков обхода в глубину на всём графе. Следовательно, всего этот алгоритм исполняется за время [math]O(V E)[/math], что в худшем случае есть [math]O(V^3)[/math].

Источники

Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — СПб.: Издательство "Лань", 2010. — 291 стр.