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

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

Доказана в 1935 году Филиппом Холлом .

О доказательствах

Одно из доказательств следует немедленно из венгерского алгоритма для поиска максимального паросочетания в графе.

Также теорема является следствием из теоремы Форда — Фалкерсона о разрезаниях транспортных сетей .

Для случая регулярных графов степени $2^{n}$ теорема легко выводится из существования эйлерова цикла в каждой связной компоненте графа; на этой идее можно построить доказательство для всех регулярных графов.

Вариации и обобщения

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

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

Пример бесконечного двудольного графа в котором не выполняется теорема о свадьбах

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

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

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

Примечания

Hall, Philip (1935), "On Representatives of Subsets", J. London Math. Soc. , 10 (1): 26—30, doi :
G. Kalai. (англ.) . — 2017. 28 августа 2020 года.

Ссылки

Н. Костюкова, : «Теорема Холла о свадьбах» // Интуит.ру , 25.07.2006
А. Ю. Эвнин. (рус.) // Математическое образование . — 2005. — Т. 3(34) . — С. 2—23 .