Изменения

Перейти к: навигация, поиск
Нет описания правки
==Матрица Татта==
{{Определение
|definition = Матрицей Татта (W.D.Tutte) для орграфа <tex>G</tex> с <tex>n</tex> вершинами называется матрица размера <tex>n \times n</tex>
}}
Заметим, что для неориентированного графа <tex>G</tex> матрицей Татта называется матрица орграфа <tex>G'</tex>, полученного из <tex>G</tex> произвольной ориентацией рёбер.
 
{{Определение
|definition = Совершенным паросочетанием в графе <tex>G</tex> называется паросочетание, покрывающее все вершины <tex>G</tex>
}}
==Матрица Эдмондса==Для случая, когда <tex>G</tex> - двудольный, существует более простая форма записи матрицы матрица, аналогичная матрице Татта.
{{Определение
|definition = Матрицей Эдмондса для двудольного графа <tex>G</tex> с размерами долей <tex>n</tex>,<tex>m</tex> называется матрица размера <tex>n \times m</tex>
108
правок

Навигация