Паросочетание в графе - это множество его ребер, каждая пара которых не смежна.
Максимальное паросочетание содержит наибольшее число ребер.
Задача о свадьбах между знакомыми
Теорема. (Холл) Двудольный граф \(G\) с долями \(V_1, V_2\) имеет полное паросочетание из \(V_1\) в \(V_2\) тогда и только тогда \(|N(A)| \geq |A|\) для любого \(A \subseteq V_1\).
Необходимость очевидна. Достаточность методом индукции по \(|V_1|\). Если \(|V_1| = 1\), то по условию \(|N(V_1)| \geq 1\) и паросочетание существует. Предположим теорема верна для любых графов с \(|V_1| \leq k\). Рассмотрим граф \(G\) с \(|V_1| = k+1\).
Сначала допустим, что для некоторого \(A \subseteq V_1\), \(|A| = j \leq k\) в точности \(|N(A)| = j\). Тогда по индуктивному предположению существует полное паросочетание из \(A\) в \(N(A)\). Удалим вершины \(A, N(A)\). В полученом графе \(G'\) выполняется условие теоремы: \(|N(A)| \geq |A|\). В противном случае должны найтись \(t \leq k+1-j\) вершин с окружением меньше \(t\), которые вместе с удаленными \(A, N(A)\) дадут противоречие условию во всем графе \(G\). Поэтому в \(G'\) графе выполняется индуктивное предположение и существует полное паросочетание. Его можно дополнить до полного в графе \(G\) возвратом удаленных вершин.
Теперь предположим, что для всех \(A \subseteq V_1\), \(|A| = j \leq k\) будет \(|N(A)| \geq j+1\). Выберем \(v \in V_1\), \(w \in N(v)\) и удалим их. В полученном графе \(G'\) по индуктивному предположению есть полное паросочетание. Добавив к нему \((v,w)\) получим его в \(G\).
Пусть \(M\) - паросочетание в графе \(G\). Цепь называется чередующейся относительно \(M\), если ее ребра входят (темные) и не входят (светлые) \(M\) по очереди. Вершина называется насыщенной (сочетающейся), если она инцидентна ребру \(M\), и ненасыщенной (свободной) в противном случае.
Лемма. Если в графе \(G\) существует чередующаяся относительно паросочетания \(M\) цепь, соединяющая две ненасыщенные вершины (светлые ребра на концах), то паросочетание \(M\) не является максимальным.
Такая цепь называется увеличивающей относительно \(M\). Удалим из \(M\) все темные ребра этой цепи и присоединим все светлые ребра этой цепи (их на одно больше), остальные ребра в \(M\) не трогаем. Получившееся паросочетание \(M'\) содержит на одно ребро больше.
Теорема. Паросочетание \(M\) в графе является максимальным тогда и только тогда, когда в графе нет увеличивающих относительно \(M\) цепей.
Необходимость очевидна. Достаточность. Допустим \(M\) не максимальное и существует паросочетание \(M'\) с \(|M'|>|M|\). Рассмотрим граф \(H\) с ребрами \((M \cup M') \setminus (M \cap M')\). Любая \(v \in H\) может быть инцидентна только одному ребру из \(M\) и только одному из \(M'\), то есть \(\deg v \leq 2\). Поэтому любая компонента связности \(H\) может быть либо циклом с одинаковым числом ребер из \(M\) и \(M'\), либо чередующейся относительно \(M\) цепью. Но \(|M'| > |M|\). Поэтому все циклами быть не могут. Кроме того, должна найтись цепь, в которой будет больше ребер из \(M'\) (они будут на концах). Эта цепь увеличивающей относительно \(M\). Противоречие.
Алгоритм поиска максимального паросочетания в двудольном графе может состоять в поиске увеличивающей цепи.
Пусть \(G = V_1 \cup V_2\) - двудольный граф и \(M\) - паросочетание. Сопоставим \(G\) и \(M\) ориентированный граф \(G'\), в котором:
Очевидно,
Лемма. В графе \(G\) существует увеличивающая цепь для \(M\) тогда и только тогда, когда в орграфе \(G'\) существует путь из \(V_1\) в \(V_2\), соединяющий две ненасыщенные вершины.
Отметим, что если в \(G'\) взять такой \((u,v)\)-путь \(P'\), то соответствующая ему цепь \(P\) в \(G\) увеличивающая для \(M\). По этой цепи \(P\) описанной заменой светлых и темных ребер получим паросочетание \(M'\), \(|M'| > |M|\). Этому действию в \(G'\) соответствует смена направления всех его дуг, входящих в цепь \(P\).
Алгоритм: