투테 행렬

그래프 이론에서, 그래프 G = (V, E)의 Tutte 행렬 A는 완벽한 일치의 존재를 결정하는 데 사용되는 행렬이다. 즉, 각 정점과 정확히 한 번 충돌하는 가장자리 집합이다.

정점 집합이 $V{\displaystyle }$=${\displaystyle }${ ${\displaystyle 1}$,${\displaystyle }$2,${\displaystyle }$…${\displaystyle }$, ${\displaystyle n}$ ${\displaystyle \}}$ ${\displaystyle V=\{1,2,\dots,n\}$인 경우 Tutte 행렬은 항목이 포함된 n × n 행렬 A이다.

${\displaystyle A_{ij}={\begin{cases}x_{ij}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i<j\\-x_{ji}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i>j\\0\;\;\;\;{\mbox{otherwise}}\end{cases}}}$

x가_ij 불연속인 곳. 이 스큐 대칭 행렬의 결정요인은 다항식(x_ij, i < j )이다. 이는 행렬 A의 파피안의 제곱과 일치하며, 완벽한 일치가 존재하는 경우에만 0이 아니다(다항식으로서). (이 다항식은 G의 Tutte 다항식이 아니다.

투테 매트릭스는 W. T. 투테의 이름을 따서 명명되었으며, 균형 잡힌 초당적 그래프를 위해 에드몬드 매트릭스를 일반화한 것이다.

참조

• R. Motwani, P. Raghavan (1995). Randomized Algorithms. Cambridge University Press. p. 167.
• Allen B. Tucker (2004). Computer Science Handbook. CRC Press. p. 12.19. ISBN 1-58488-360-X.
• W.T. Tutte (April 1947). "The factorization of linear graphs" (PDF). J. London Math. Soc. 22 (2): 107–111. doi:10.1112/jlms/s1-22.2.107. Retrieved 2008-06-15.

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

• v
• t