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

Теорема:

Если из вершины х не существует дополняющей цепи относительно паросочетание М, то если паросочетание М' получается из М изменением вдоль дополняющей цепи, то из х не существует дополняющей цепи в М'.

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Алгоритм

Пусть дан двудольный граф [math]G(V, E)[/math] и требуется найти максимальное паросочетание в нём. Преобразуем его в граф [math]G'(V', E')[/math] следующим образом

[math]V' = V \cup \{s, t\}[/math]

Обазначим доли исходного графа как [math]L[/math] и [math]R[/math]. Тогда [math]E' = {(s,u): u \in L} \cup {(u, v): u \in L, v \in R} \cup {(v, t): v \in R} [/math]

1) Будем искать путь из [math]s[/math] в [math]t[/math] поиском в глубину.

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

3) Если путь не был найден, значит текущее паросочетание является максимальным и алгоритм завершает работу. Иначе переходим к пункту 1)

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