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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Теорема Холла»)
Перейти к: навигация, поиск

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

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

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

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

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

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

Теперь рассмотрим произвольный разрез . Пусть в попали ровно вершин из первой доли и из второй.

  1. Пусть . Тогда пропускная способность разреза складывается из рёбер, ведущих из в вершины первой доли, лежащие в и рёбер, ведущих из вершин второй доли, лежащих в , в . Суммируя, получаем: .
  2. Иначе, . По условию теоремы, эти вершин связаны с вершинами второй доли, а так как , то они связаны хотя бы с вершинами во второй доле, попавшими во множество . Тогда пропускная способность разреза рассчитывается так же, как в предыдущем пункте, плюс рёбер из вершин первой доли, принадлежащих в вершины второй доли, принадлежащими . Итого, .

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

Ссылки[править | править вики-текст]