Теорема о свадьбах

Теорема Холла (или теорема о свадьбах), названная в честь английского математика Филипа Холла (англ. Philip Hall), утверждает, что если в двудольном графе для любого $k$ любые $k$ элементов одной из долей связаны по крайней мере с $k$ элементами другой, то граф разбивается на пары.

Теорема обобщается на граф, имеющий произвольное (не обязательно конечное или счётное) множество долей.

Доказательство при помощи теоремы Форда-Фалкерсона

Пусть мощность первой доли — $n$. Сделаем из данного графа сеть. Для этого на каждом ребре введем пропускную способность по 1 в направлении от вершины первой доли к вершине второй. При этом создадим две дополнительные вершины — $s$ и $t$, от первой проведем все стрелки в вершины первой доли, а из каждой вершины второй проведем стрелки во вторую добавленную вершину. Заметим, что получившаяся сеть — целочисленная, то есть в ней существует максимальный целочисленный поток, и что если мы сможем доказать, что пропускная способность минимального разреза равна $n$, то по теореме Форда-Фалкерсона величина максимального потока равна пропускной способности минимального разреза, то есть тоже равна $n$. Очевидно, что если в бинарной транспортной сети величина максимального потока равна $n$, то существует $n$ непересекающихся по вершинам путей из истока в сток. Это следует из алгоритма для нахождения максимального целочисленного потока в целочисленном графе, а из каждого такого пути можно выбрать смежную пару вершин из разных долей исходного графа.

То, что мощность минимального разреза не превышает $n$, очевидно — достаточно рассмотреть разрез, в котором множество $S$ содержит одну вершину $s$.

Теперь рассмотрим произвольный разрез $(S,T)$. Пусть в $S$ попали ровно $m\leqslant n$ вершин из первой доли и $l$ из второй.

1. Пусть $l\geqslant m$. Тогда пропускная способность разреза складывается из $n-m$ рёбер, ведущих из $s$ в вершины первой доли, лежащие в $T$ и $l$ рёбер, ведущих из вершин второй доли, лежащих в $S$, в $t$. Суммируя, получаем: $n-m+l=n+(l-m)\geqslant n$.
2. Иначе, $l<m$. По условию теоремы, эти $m$ вершин связаны с $m$ вершинами второй доли, а так как $l<m$, то они связаны хотя бы с $m-l$ вершинами во второй доле, попавшими во множество $T$. Тогда пропускная способность разреза рассчитывается так же, как в предыдущем пункте, плюс $m-l$ рёбер из вершин первой доли, принадлежащих $S$ в вершины второй доли, принадлежащими $T$. Итого, $(n-m)+l+(m-l)=n$.

В обоих случаях величина максимального потока равна $n$, что и требовалось доказать.

Ссылки

• Формулировка и доказательство