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

В теория графов, то Матрица Эдмондса ${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{{egin{array}{ll}x_{ij}&(u_{i},v_{j})in E�&(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.