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

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

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

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

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

Ссылки

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