에드몬드 매트릭스

In graph theory, the Edmonds matrix ${\displaystyle A}$ of a balanced bipartite graph ${\displaystyle G(U,V,E)}$ with sets of vertices ${\displaystyle U=\{u_{1},u_{2},\dots ,u_{n}\}}$ and ${\displaystyle V=\{v_{1},v_{2},\dots ,v_$${n}\}$은(는) 다음에 의해 정의됨

${\displaystyle A_{ij}=\왼쪽\{\\begin{array}{ll}x_{ij}&(u_{i},v_{j})\in E\nd{array}\right.}$

x가_ij 불연속인 곳. 초당적 그래프의 Edmonds 행렬의 한 가지 적용은 x의_ij 다항식 멈춤(A_ij)이 동일한 0이 아닌 경우에만 그래프가 완벽한 일치를 인정하는 것이다. 더욱이, 완벽한 일치의 수는 다항식 det(A)의 단항수 수와 같으며, $또한{\displaystyle }$ A$${\$displaystyle A$}의 영구수와 같다$.$ 또한 $A{\displaystyle }$ ${\displaystyle A}$의 순위는 $G{\displaystyle }$ ${\displaystyle G}$의 최대 일치 크기와 같다$$$.$

에드몬드 매트릭스는 잭 에드몬드의 이름을 따서 명명되었다. 투테 행렬은 비-비-비-비-비-비-비-바타이트 그래프에 대한 일반화다.

참조

• R. Motwani, P. Raghavan (1995). Randomized Algorithms. Cambridge University Press. p. 167. ISBN 9780521474658.
• Allen B. Tucker (2004). Computer Science Handbook. CRC Press. p. 12.19. ISBN 1-58488-360-X.

이 콤비네이터 관련 기사는 단조롭다. 위키피디아를 확장하여 도울 수 있다.

• v
• t