Изменения
Нет описания правки
==Матрица Татта==
{{Определение
|definition = '''Матрицей Татта''' (англ. '''Tutte matrix''') для орграфа <tex>G</tex> с <tex>n</tex> вершинами называется матрица размера <tex>n \times n</tex>.
<tex>A_{ij} =
\begin{cases}
Заметим, что для неориентированного графа <tex>G</tex> матрицей Татта называется матрица орграфа <tex>G'</tex>, полученного из <tex>G</tex> произвольной ориентацией рёбер.
{{Определение
|definition = '''Совершенным паросочетанием''' в графе <tex>G</tex> называется паросочетание, покрывающее все вершины <tex>G</tex>.
}}
{{Теорема
|statement = В графе <tex>G</tex> существует совершенное паросочетание тогда и только тогда, когда определитель матрицы Татта для <tex>G</tex> не равен нулютождественно.
|proof =
<tex>det(A_{ij}) = \sum\limits_\phi sign(\phi)E_{1\phi(1)}E_{2\phi(2)}...E_{n\phi(n)}</tex>
