- Теорема Холла
-
Теорема Холла (или теорема о свадьбах), утверждает, что если в двудольном графе для любого
любые
элементов одной из долей связаны по крайней мере с
элементами другой, то граф разбивается на пары.
Названна в честь английского математика Филипа Холла (англ.).
Теорема обобщается на граф, имеющий произвольное (не обязательно конечное или счётное) множество долей.
Доказательство при помощи теоремы Форда — Фалкерсона
Пусть мощность первой доли —
. Сделаем из данного графа сеть. Для этого на каждом ребре введем пропускную способность по 1 в направлении от вершины первой доли к вершине второй. При этом создадим две дополнительные вершины —
и
, от первой проведем все стрелки в вершины первой доли, а из каждой вершины второй проведем стрелки во вторую добавленную вершину. Заметим, что получившаяся сеть — целочисленная, то есть в ней существует максимальный целочисленный поток, и что если мы сможем доказать, что пропускная способность минимального разреза равна
, то по теореме Форда-Фалкерсона величина максимального потока равна пропускной способности минимального разреза, то есть тоже равна
. Очевидно, что если в бинарной транспортной сети величина максимального потока равна
, то существует
непересекающихся по вершинам путей из истока в сток. Это следует из алгоритма для нахождения максимального целочисленного потока в целочисленном графе, а из каждого такого пути можно выбрать смежную пару вершин из разных долей исходного графа.
То, что мощность минимального разреза не превышает
, очевидно — достаточно рассмотреть разрез, в котором множество
содержит одну вершину
.
Теперь рассмотрим произвольный разрез
. Пусть в
попали ровно
вершин из первой доли и
из второй.
- Пусть
. Тогда пропускная способность разреза складывается из
рёбер, ведущих из
в вершины первой доли, лежащие в
и
рёбер, ведущих из вершин второй доли, лежащих в
, в
. Суммируя, получаем:
.
- Иначе,
. По условию теоремы, эти
вершин связаны с
вершинами второй доли, а так как
, то они связаны хотя бы с
вершинами во второй доле, попавшими во множество
. Тогда пропускная способность разреза рассчитывается так же, как в предыдущем пункте, плюс
рёбер из вершин первой доли, принадлежащих
в вершины второй доли, принадлежащими
. Итого,
.
В обоих случаях величина максимального потока равна
, что и требовалось доказать.
Ссылки
Категория:- Теория графов
- Пусть
Wikimedia Foundation. 2010.