Теорема Холла

Теорема Холла (или теорема о свадьбах), утверждает, что если в двудольном графе для любого $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$, что и требовалось доказать.

Ссылки

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