Меню Главная Случайная статья Настройки Теорема о свадьбах Материал из https://ru.wikipedia.org Теорема о свадьбах (также теорема о мальчиках и девочках, теорема Холла) — утверждение о том, что в двудольном графе для любого натурального ${\displaystyle k}$ любые ${\displaystyle k}$ вершин одной из долей, где ${\displaystyle k}$ не превышает числа вершин доли, связаны по крайней мере с ${\displaystyle k}$ различными вершинами другой доли тогда и только тогда, когда граф разбивается на пары по первой доле. Доказана в 1935 году Филиппом Холлом.[1] Содержание 1 О доказательствах 2 Вариации и обобщения 3 Примечания 4 Ссылки О доказательствах Одно из доказательств следует немедленно из венгерского алгоритма для поиска максимального паросочетания в графе. Также теорема является следствием из теоремы Форда — Фалкерсона о разрезаниях транспортных сетей. Для случая регулярных графов степени ${\displaystyle 2^{n}}$ теорема легко выводится из существования эйлерова цикла в каждой связной компоненте графа; на этой идее можно построить доказательство для всех регулярных графов.[2] Вариации и обобщения Из теоремы о свадьбах немедленно следует, что любой регулярный двудольный граф степени ${\displaystyle r\geqslant 1}$ допускает совершенное паросочетание. Теорема обобщается на двудольные графы с бесконечным множеством вершин, при условии, что все вершины имеют конечную степень. Пример бесконечного двудольного графа, для которого теорема не верна — прямой цилиндрический стакан, который строится следующим образом: первая доля множества вершин — точки верхней окружности стакана и центр нижнего основания; вторая доля — точки окружности нижнего основания; рёбра графа — все радиусы нижнего основания и вертикальные отрезки боковой поверхности. теорема Татта о паросочетаниях — обобщение теоремы о свадьбах на случай произвольных конечных, но необязательно двудольных, графов. Теорема Кёнига — близкое утверждение, связывающее нахождение наибольшего паросочетания и наименьшего вершинного покрытия в конечных графах. Примечания Hall, Philip (1935), On Representatives of Subsets, J. London Math. Soc., 10 (1): 26–30, doi:10.1112/jlms/s1-10.37.26 G. Kalai. The seventeen camels riddle, and Noga Alon’s camel proof and algorithms (англ.). — 2017. Архивировано 28 августа 2020 года. Ссылки Н. Костюкова, Курс «Графы и их применение», Лекция 15: Паросочетания и свадьбы: «Теорема Холла о свадьбах» // Интуит.ру, 25.07.2006 А. Ю. Эвнин. Вокруг теоремы Холла (рус.) // Математическое образование. — 2005. — Т. 3(34). — С. 2—23.