105
правок
Изменения
Нет описания правки
===Максимальное паросочетание===
{{Определение|definition=
Максимальным [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|паросочетанием ]] <tex>MM</tex> <tex>(maximum</tex> <tex>matching)</tex> в [[Основные_определения_теории_графов|графе ]] <tex>G</tex> называется паросочетание максимальной мощности.
}}
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия.
|proof=
Пусть в <tex>G</tex> построено максимальное паросочетание. Ориентируем ребра паросочетания, чтобы они шли из правой доли в левую, ребра не из паросочетания – так, чтобы они шли из левой доли в правую. Запустим [[Обход_в_глубину,_цвета_вершин|обход в глубину ]] из всех не насыщенных паросочетанием вершин левой доли. Разобьем вершины каждой доли графа на два множества: те, которые были посещены в процессе обхода, и те, которые не были посещены в процессе обхода.
Тогда <tex>L = L^+ \cup L^-</tex>, <tex>R = R^+ \cup R^-</tex>, где <tex>L, R</tex> – правая и левая доли соответственно, <tex>L^+, R^+</tex> – вершины правой и левой доли, посещенные обходом, <tex>L^-, R^-</tex> – не посещенные обходом вершины.
Тогда в <tex>G</tex> могут быть следующие ребра:
