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

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

Названа в честь английского математика Филипа Холла (англ.), доказавшего ее в 1935 году.

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

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

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

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

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

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