Изменения

Пусть дан неориентированный двудольный граф <tex>G(V, E)</tex> и требуется найти [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] в нём. Обозначим доли исходного графа как <tex>L</tex> и <tex>R</tex>. Построим граф <tex>G'(V', E')</tex> следующим образом:

<tex>V' = V \cup \{s, t\}</tex> (т.е. добавим две новые вершины новый исток <tex>s</tex> и сток <tex>t</tex>);

<tex>E' = \{(s,u): u \in L\} \cup \{(u, v): u \in L, v \in R\} \cup \{(v, t): v \in R\} </tex> (проведем ребра из <tex>s</tex> в каждую вершину <tex>L</tex>, и из каждой вершины <tex>R</tex> в <tex>t</tex>, и ориентируем все ребра графа <tex>G'</tex> так, чтобы они шли от <tex>u \in L\</tex> к <tex>v \in R\</tex>).

# Будем искать Ищем в графе <tex>G'</tex> путь из <tex>s</tex> в <tex>t</tex> поиском в глубину. # Если путь найден, инвертируем все рёбра на пути(ребро <tex>(u, v)</tex> становится ребром <tex>(v, u)</tex>). После этого перезаписываем текущее паросочетание так, чтобы в него входили ребра этого пути, ведущие из <tex>R</tex> в <tex>L</tex>.

==Корректность алгоритма== # Путь из <tex>s</tex> в <tex>t</tex> является дополняющей цепью для исходного графа <tex>G</tex>. # Инвертация ребер не меняет пути, следовательно, он остается дополняющей цепью.# В любой момент времени текущим паросочетанием будет найденном пути вершины не повторяются (это свойство поиска в глубину), тогда множество рёберребер, направленных ведущих только из <tex>R</tex> в <tex>L</tex> является паросочетанием.# Путь не был найден. Это значит, что не существует дополняющей цепи для графа <tex>G'</tex>. Тогда по [[Теорема о максимальном паросочетании и дополняющих цепях|теореме]] текущее паросочетание является максимальным. ==Оценка производительности== Поиск в глубину запускается от вершины <tex>s</tex> не более чем <tex>L</tex> раз, т.к. из <tex>s</tex> ведет ровно <tex>L</tex> ребер, и при каждом запуске одно из них инвертируется. Сам поиск работает за <tex>O(E)</tex>, каждая инвертация и перезапись паросочетания так же занимает <tex>O(E)</tex> времени. Тогда все время алгоритма ограничено <tex>O(VE)</tex>.