タット行列

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

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

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

タット行列はに因んで命名され、釣り合い型2部グラフについてのの一般化である。

参考文献



Category:行列
Category:グラフ理論
Category:代数的グラフ理論
Category:人名を冠した数式
Category:数学に関する記事