Теорема Стокса
- 1 year ago
- 0
- 0
Теорема Татта о паросочетаниях — теоретико-графовое утверждение, дающее необходимое и достаточное условие на существование совершенного паросочетания в графе ; обобщает теорему о свадьбах для двудольных графов и является частным случаем формулы Татта — Бержа .
Утверждение теоремы: граф имеет совершенное паросочетание тогда и только тогда, когда для каждого подмножества вершин подграф , , имеет не более связных компонент с нечётным числом вершин .
Установлена Уильямом Таттом .