タット行列

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

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

$A_{ij}=\{\begin{array}{c}{x}_{ij}\text{if}(i,j)\in E\text{ and }i<j\\ -x_{ji}\text{if}(i,j)\in E\text{ and }i>j\\ 0\text{otherwise}\end{array}$

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

タット行列はテンプレート:仮リンクに因んで命名され、釣り合い型2部グラフについてのテンプレート:仮リンクの一般化である。

参考文献

• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Cite journal