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

Теорема

Теорема:

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

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

[math]\triangleright[/math]

Пунктиром обозначен путь между двумя вершинами. Ребро красного цвета лежит в паросочетании, а черного - нет. Доказательство от противного. Допустим в паросочетание внесли изменения вдоль дополняющей цепи [math](y \rightsquigarrow z)[/math] и из вершины [math]x[/math] появилась дополняющая цепь. Заметим, что эта дополняющая цепь должна вершинно пересекаться с той цепью, вдоль которой вносились изменения, иначе такая же дополняющая цепь из [math]x[/math] существовала и в исходном паросочетании. Пусть [math]p[/math] - ближайшая к [math]x[/math] вершина, которая принадлежит и новой дополняющей цепи и цепи [math](y \rightsquigarrow z)[/math]. Тогда [math]MP[/math] - последнее ребро на отрезке [math](y \rightsquigarrow p)[/math] цепи [math](y \rightsquigarrow z)[/math], [math]NP[/math] - последнее ребро на отрезке [math](z \rightsquigarrow p)[/math] цепи [math](y \rightsquigarrow z)[/math], [math]QP[/math] - последнее ребро лежащее на отрезке [math](x \rightsquigarrow p)[/math] новой дополняющей цепи.(см. рисунок). Допустим [math]MP[/math] принадлежит паросочетанию [math]M'[/math], тогда [math]NP[/math] ему не принадлежит. Поскольку паросочетание [math]M'[/math] получается из [math]M[/math] изменением вдоль дополняющей цепи [math](y \rightsquigarrow z)[/math], в паросочетание [math]M[/math] входило ребро [math]NP[/math], а ребро [math]MP[/math] нет. Кроме того, ребро [math]QP[/math] не лежит ни в исходном паросочетании [math]M[/math], ни в паросочетании [math]M'[/math], в противном случае оказалось бы, что вершина [math]p[/math] инцидентна нескольким ребрам из паросочетания, что противоречит определению паросочетания. Тогда заметим, что цепь [math](x \rightsquigarrow z)[/math], полученная объединением цепей [math](x \rightsquigarrow p)[/math] и [math](p \rightsquigarrow z)[/math], по определению будет дополняющей в паросочетании [math]M[/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 стр.