Теорема Татта о паросочетаниях
Перейти к навигации
Перейти к поиску
Теорема Татта о паросочетаниях — теоретико-графовое утверждение, дающее необходимое и достаточное условие на существование совершенного паросочетания в графе; обобщает теорему о свадьбах для двудольных графов и является частным случаем формулы Татта — Бержа.
Утверждение теоремы: граф имеет совершенное паросочетание тогда и только тогда, когда для каждого подмножества вершин подграф, индуцированный , имеет не более связных компонент с нечётным числом вершин.
Установлена Уильямом Таттом.
Литература
[править | править код]- 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.
В другом языковом разделе есть более полная статья Tutte theorem (англ.). |