WikiSort.ru - Не сортированное

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

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

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

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

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

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

• Из теоремы о свадьбах немедленно следует, что любой регулярный граф степени ${\displaystyle r\geq 1}$ допускает совершенное паросочетание.
• Теорема обобщается на двудольные графы с бесконечным множеством вершин, при условии, что все вершины имеют конечную степень.
  • Пример бесконечного двудольного графа, для которого теорема не верна — прямой цилиндрический стакан, который строится следующим образом: первая доля множества вершин — точки верхней окружности стакана и центр нижнего основания; вторая доля — точки окружности нижнего основания; рёбра графа — все радиусы нижнего основания и вертикальные отрезки боковой поверхности.
• Теорема Тата о паросочетаниях — обобщение теоремы о свадьбах на случай произвольных конечных, но необязательно двудольных, графов.
• Теорема Кёнига — близкое утверждение, связывающее нахождение наибольшего паросочетания и наименьшего вершинного покрытия в конечных графах.

Ссылки

• Н. Костюкова, Курс "Графы и их применение", Лекция 15: Паросочетания и свадьбы: "Теорема Холла о свадьбах" // Интуит.ру, 25.07.2006
• А. Ю. Эвнин. Вокруг теоремы Холла (рус.) // Матем. обр.. — 2005. — Т. 3(34). — С. 2—23.
• Hall, Philip (1935), "On Representatives of Subsets", J. London Math. Soc. Т. 10 (1): 26–30, DOI 10.1112/jlms/s1-10.37.26 

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.