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

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

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

Доказана в 1935 году Филиппом Холлом. Доказательство следует немедленно из венгерского алгоритма для поиска максимального паросочетания в графе; также утверждение легко выводится из теоремы Форда — Фалкерсона о разрезаниях транспортных сетей.

Вариации и обобщения[править | править код]

Из теоремы о свадьбах немедленно следует, что любой регулярный граф степени допускает совершенное паросочетание.

Теорема обобщается на двудольные графы с бесконечным множеством вершин, при условии, что все вершины имеют конечную степень. Пример бесконечного двудольного графа, для которого теорема не верна — прямой цилиндрический стакан, который строится следующим образом: первая доля множества вершин — точки верхней окружности стакана и центр нижнего основания; вторая доля — точки окружности нижнего основания; рёбра графа — все радиусы нижнего основания и вертикальные отрезки боковой поверхности.

Обобщение теоремы о свадьбах на случай произвольных конечных, но необязательно двудольных, графов — теорема Татта о паросочетаниях.

Теорема Кёнига — близкое утверждение, связывающее нахождение наибольшего паросочетания и наименьшего вершинного покрытия в конечных графах.

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