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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

Пусть мощность первой доли — 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 , что и требовалось доказать.

Ссылки[править | править исходный текст]