Матрица Эдмондса

В теории графов , то матрица Эдмондс сбалансированного двудольный граф с множествами вершин и определяется ${\ displaystyle A}$ ${\ Displaystyle G (U, V, E)}$ ${\ Displaystyle U = \ {u_ {1}, u_ {2}, \ dots, u_ {n} \}}$ ${\ displaystyle V = \ {v_ {1}, v_ {2}, \ dots, v_ {n} \}}$

{\ displaystyle A_ {ij} = \ left \ {{\ begin {array} {ll} x_ {ij} & (u_ {i}, v_ {j}) \ in E \\ 0 & (u_ {i}, v_ {j}) \ notin E \ end {array}} \ right.}

где х _IJ является неизвестными . Одно из применений матрицы Эдмондса двудольного графа состоит в том, что граф допускает полное соответствие тогда и только тогда, когда многочлен det ( A _ij ) от x _ij не равен тождественно нулю. Кроме того, количество совершенных паросочетаний равно количеству одночленов в многочлене det ( A ), а также перманенту числа . Кроме того, ранг из равен максимальному соответствия размеру . ${\ displaystyle A}$ ${\ displaystyle A}$ ${\ displaystyle G}$

Матрица Эдмондса названа в честь Джека Эдмондса . Матрица Tutte является обобщением , не двудольных графов.

Ссылки [ править ]

Р. Мотвани, П. Рагхаван (1995). Рандомизированные алгоритмы . Издательство Кембриджского университета. п. 167. ISBN. 9780521474658.
Аллен Б. Такер (2004). Справочник по информатике . CRC Press. п. 12.19. ISBN 1-58488-360-X.

Эта статья о комбинаторике незавершена . Вы можете помочь Википедии, расширив ее .