Interested Article - Теорема Татта о паросочетаниях

Теорема Татта о паросочетаниях теоретико-графовое утверждение, дающее необходимое и достаточное условие на существование совершенного паросочетания в графе ; обобщает теорему о свадьбах для двудольных графов и является частным случаем формулы Татта — Бержа .

Утверждение теоремы: граф имеет совершенное паросочетание тогда и только тогда, когда для каждого подмножества вершин подграф , , имеет не более связных компонент с нечётным числом вершин .

Установлена Уильямом Таттом .

Литература

  • Bondy, J. A. (неопр.) . — 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 .
Источник —

Same as Теорема Татта о паросочетаниях