タット行列

グラフ理論において、グラフG = (V, E) のタット行列（タットぎょうれつ、英: Tutte matrix）Aは、完全マッチング、すなわち、それぞれの頂点と厳密に一度接続する辺の集合の存在を決定するために使われる行列である。

頂点の集合を V = { 1 , 2 , … , n } {\displaystyle V=\{1,2,\dots ,n\}} とすると、タット行列は成分

A i j = { x i j if ( i , j ) ∈ E  and  i < j − x j i if ( i , j ) ∈ E  and  i > j 0 otherwise {\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}}}

を持つn × n行列Aである。上式においてxijは不定元である。この歪対称行列の行列式は多項式である（xij、i < jにおいて）: これは行列Aのパフィアンの二乗と一致し、完全マッチングが存在する時かつその時に限り（多項式として）非ゼロである（この多項式はGのタット多項式（英語版）ではない）。

タット行列はW・T・タット（英語版）に因んで命名され、釣り合い型2部グラフについてのエドモンズ行列（英語版）の一般化である。

参考文献

  • 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”. J. London Math. Soc. 22 (2): 107–111. doi:10.1112/jlms/s1-22.2.107. http://jlms.oxfordjournals.org/cgi/reprint/s1-22/2/107.pdf 2008年6月15日閲覧。. 
  • 表示
  • 編集