Меню Главная Случайная статья Настройки Теорема Татта о паросочетаниях Материал из https://ru.wikipedia.org Теорема Татта о паросочетаниях — теоретико-графовое утверждение, дающее необходимое и достаточное условие на существование совершенного паросочетания в графе; обобщает теорему о свадьбах для двудольных графов и является частным случаем формулы Татта — Бержа. Утверждение теоремы: граф ${\displaystyle G=(V,E)}$ имеет совершенное паросочетание тогда и только тогда, когда для каждого подмножества вершин ${\displaystyle U\subseteq V}$ подграф, индуцированный ${\displaystyle V\setminus U}$, имеет не более ${\displaystyle |U|}$ связных компонент с нечётным числом вершин. Установлена Уильямом Таттом. Литература Bondy, J. A. Graph theory with applications (неопр.). — New York: American Elsevier Pub. Co., 1976. — ISBN 0-444-19451-7.