タット行列のソースを表示

[[グラフ理論]]において、[[グラフ (離散数学)|グラフ]]''G''&nbsp;=&nbsp;(''V'',&nbsp;''E'') の'''タット行列'''（タットぎょうれつ、{{lang-en-short|Tutte matrix}}）''A''は、[[マッチング (グラフ理論)|完全マッチング]]、すなわち、それぞれの[[頂点 (グラフ理論)|頂点]]と厳密に一度接続する辺の集合の存在を決定するために使われる[[行列]]である。

頂点の集合を<math>V = \{1, 2, \dots , n\}</math>とすると、タット行列は成分
: <math>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}</math>
を持つ''n''&nbsp;×&nbsp;''n''行列''A''である。上式において''x''<sub>''ij''</sub>は[[不定元]]である。この[[交代行列|歪対称行列]]の[[行列式]]は多項式である（''x<sub>ij</sub>''、''i&nbsp;<&nbsp;j''において）: これは行列''A''の[[パフィアン]]の二乗と一致し、完全マッチングが存在する時かつその時に限り（多項式として）非ゼロである（この多項式は''G''の{{仮リンク|タット多項式|en|Tutte polynomial}}ではない）。

タット行列は{{仮リンク|W・T・タット|en|W. T. Tutte}}に因んで命名され、釣り合い型[[2部グラフ]]についての{{仮リンク|エドモンズ行列|en| Edmonds matrix}}の一般化である。

==参考文献==
*{{cite book|author=R. Motwani, P. Raghavan |title=Randomized Algorithms|publisher=Cambridge University Press|year=1995|page=167}}
*{{cite book|author=Allen B. Tucker|title=Computer Science Handbook|publisher=CRC Press|date=2004|isbn=1-58488-360-X|page=12.19}}
* {{cite journal|url= http://jlms.oxfordjournals.org/cgi/reprint/s1-22/2/107.pdf|title= The factorization of linear graphs
|accessdate= 2008-06-15|author= W.T. Tutte|date=April 1947|volume=22|journal=J. London Math. Soc.|pages=107–111|doi=10.1112/jlms/s1-22.2.107|issue= 2}}

{{DEFAULTSORT:たつときようれつ }}
[[Category:行列]]
[[Category:グラフ理論]]
[[Category:代数的グラフ理論]]
[[Category:人名を冠した数式]]
[[Category:数学に関する記事]]

{{Combin-stub}}