Изменения
Нет описания правки
Предположим, что существует паросочетание большей мощности. Однако тогда и соответствующий ему ненулевой (по теореме о матрице Татта) минор большего размера, чем <tex>A_M</tex>, что невозможно в силу выбора <tex>A_M</tex> максимальным.
}}
==См. также==
* [[Теорема Татта о существовании полного паросочетания]]
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
* [[Декомпозиция Эдмондса-Галлаи]]
==Источники информации==
*[https://en.wikipedia.org/wiki/Tutte_matrix Wikipedia {{---}} Tutte matrix]
*[https://en.wikipedia.org/wiki/Edmonds_matrix Wikipedia {{---}} Edmonds matrix]
*[http://e-maxx.ru/algo/tutte_matrix E-maxx {{---}} MAXimal::algo::Матрица Татта]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]
