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

Теорема Тата о паросочетаниях даёт необходимое и достаточное условие на существование совершенного паросочетания в графе. Названа в честь Уильяма Томаса Тата.

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

Теорема Тата

Граф G = (V, E) имеет совершенное паросочетание тогда и только тогда, когда для каждого подмножества U в V подграф, индуцированный V − U, имеет не более |U| связных компонент с нечётным числом вершин.

См. также

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

Ссылки

• Bondy, J. A. Graph theory with applications. — New York : American Elsevier Pub. Co., 1976. — ISBN 0-444-19451-7.
• Lovász, László. Matching theory. — Amsterdam : North-Holland, 1986. — ISBN 0-444-87916-1.