タット行列

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

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

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である。上式においてx_ijは不定元である。この歪対称行列の行列式は多項式である（x_ij、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 2008年6月15日閲覧。.

この項目は、組合せ数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。