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

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

${displaystyle A_ {ij} = left {{egin {array} {ll} x_ {ij} & (u_ {i}, v_ {j}) в E 0 & (u_ {i}, v_ {j}) otin Eend {array}} ight.}$

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

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

Рекомендации

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

Этот комбинаторика-связанная статья является заглушка. Вы можете помочь Википедии расширяя это. v т е