コンテンツにスキップ

タット行列

出典: フリー百科事典『ウィキペディア(Wikipedia)』

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

頂点の集合をとすると、タット行列は成分

を持つn × n行列Aである。上式においてxij不定元である。この歪対称行列行列式は多項式である(xiji < 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日閲覧。.