タットの定理のソースを表示

[[File:Sylvester counter.svg|thumb|200px|中央の頂点を除くと、頂点数がいずれも5の3個の連結成分が生じる。よってタットの定理より、このグラフは完全マッチングを持たない。]]
[[数学]]の分科、[[グラフ理論]]における'''タットの定理'''（タットのていり、{{Lang-en-short|Tutte theorem}}）とは、[[マッチング (グラフ理論)|完全マッチング]]を持つグラフの特徴付けを与える定理である。名称は{{仮リンク|ウィリアム・トーマス・タット|en|William Thomas Tutte}}にちなむ。この定理は[[ホールの定理]]を[[2部グラフ]]から任意のグラフへと一般化したものであり、また{{仮リンク|タット-ベルジュの公式|en|Tutte–Berge formula}}の特殊な場合である。

== 定理 ==
グラフ {{math|''G''&nbsp;{{=}}&nbsp;(''V'',&nbsp;''E'')}} が完全マッチングを持つのは、[[頂点 (グラフ理論)|頂点]]集合 {{math|''V''}} の任意の[[部分集合]] {{math|''U''}} に対し、{{math|''V''&nbsp;&minus;&nbsp;''U''}} から[[誘導部分グラフ|誘導される部分グラフ]]の、[[奇数]]個の頂点を持つ[[連結成分]]の個数が高々 {{math|<nowiki>|</nowiki>''U''<nowiki>|</nowiki>}} 個であるとき、かつそのときに限る<ref>{{harvtxt |Lovász|Plummer|1986}}, p.&nbsp; 84; {{harvtxt|Bondy|Murty|1976}}, Theorem&nbsp;5.4, p.&nbsp;76.</ref>。

==証明==
条件を以下のように書く。
:<math>(*) \qquad \forall U \subseteq V, \quad o(V-U)\le|U|</math>
ここで <math>o(X)</math> は <math>X</math> から誘導される部分グラフの、奇数個の頂点を持つ連結成分の個数を表す。

'''(∗)の必要性：''' グラフ {{math|''G''}} に完全マッチングがあるとする。{{math|''U''}} を {{math|''V''}} の任意の部分集合として、グラフから {{math|''U''}} を除く。{{math|''C''}} を 誘導部分グラフ {{math|''G''&nbsp;&minus;&nbsp;''U''}} の任意の奇頂点連結成分とする。{{math|''G''}} は完全マッチングを持つから、{{math|''C''}} にはそのマッチングにおいて {{math|''U''}} の要素と接続されていた頂点が少なくとも1つは存在する。

この対応付けによって {{math|''G''&nbsp;&minus;&nbsp;''U''}} の奇頂点連結成分全体から {{math|''U''}} への[[写像]]が定まるが、これはマッチングの完全性より[[単射]]である。よって {{math|''o''(''G''&nbsp;&minus;&nbsp;''U'')&nbsp;≤&nbsp;{{!}}''U''{{!}}}}<ref name="bm-proof">{{harvtxt|Bondy|Murty|1976}}, pp.&nbsp;76–78.</ref>。

'''(∗)の十分性：''' 完全マッチングを持たないグラフ {{math|''G''}} を任意にとる。このとき {{math|{{!}}''S''{{!}}&nbsp;<&nbsp;''o''(''G''&nbsp;&minus;&nbsp;''S'')}} を満たす {{math|''V''}} の部分集合 {{math|''S''}} （以下これを「悪い」頂点部分集合と呼ぶ）が必ず存在する。ここで、

* もし {{math|''G''}} の頂点数 {{math|{{!}}''V''{{!}}}} が奇数であるとすれば、{{math|''G''}} には少なくとも1個以上の奇頂点連結成分が存在するから、[[空集合]] {{math|&#8709;}} が悪い頂点部分集合になる。よって以下、頂点は偶数個であると仮定してよい。このとき  {{math|''o''(''G''&nbsp;&minus;&nbsp;''U'')}} と {{math|{{!}}''U''{{!}}}} の[[偶奇性]]は常に一致する。
* さらに、{{math|''G''}} は辺極大（edge-maximal）である、つまり {{math|''G''}} に存在しないような任意の2頂点間の接続 {{math|''e''}} について、{{math|''G''&nbsp;+&nbsp;''e''}} が完全マッチングを持つようになると仮定してよい。
:なぜなら、グラフ {{math|''G''}} の悪い頂点部分集合 {{math|''S''}} は、{{math|''G''}} の任意の[[グラフ理論|全域部分グラフ]]（spanning subgraph, 部分グラフであって元のグラフと頂点集合が一致するもの）の悪い頂点部分集合でもあるからである（奇頂点連結成分から辺を取り去ることでいくつかの連結成分に分裂したとすると、そのうち少なくとも1つの連結成分は頂点が奇数個でなければならない）。

{{math|''S''}} を、[[次数 (グラフ理論)|次数]]が {{math|{{!}}''V''{{!}}&nbsp;&minus;&nbsp;1}} である頂点の集合（自分自身以外の全ての頂点と接続されているような頂点全体）と定義する。これが悪い頂点部分集合になることを以下場合分けして証明する。

* {{math|''G''&nbsp;&minus;&nbsp;''S''}} の全ての連結成分が[[完全グラフ]]になる場合、{{math|''S''}} は悪い頂点部分集合である。なぜならもし {{math|''o''(''G''&nbsp;&minus;&nbsp;''S'')&nbsp;≤&nbsp;{{!}}''S''{{!}}}} だとすると、各奇頂点連結成分と {{math|''S''}} の頂点とを結ぶ辺の集合と、それ以外の全ての頂点を余さず二人一組にするような辺集合の[[和集合]]が完全マッチングになるからである。

[[File:TuttThmPrfFig_1.png|thumb|right|200px|元のグラフ {{math|''G''&nbsp;{{=}}&nbsp;(''V'',&nbsp;''E'')}} の辺であるものを実線で示す。{{math|''b''}} と {{math|''y''}} は同一の頂点かもしれない。]]
* そうでない場合は、実はあり得ない。そのことを[[背理法]]で示す。

:{{math|''G''&nbsp;&minus;&nbsp;''S''}} のある連結成分 {{math|''K''}} が完全グラフではないとする。このとき {{math|''xy''&nbsp;&notin;&nbsp;''E''}} となる2頂点 {{math|''x'',&nbsp;''y''&nbsp;&isin;&nbsp;''K''}} が選べる。{{math|''x'',&nbsp;''a'',&nbsp;''b''&nbsp;&isin;&nbsp;''K''}} を、{{math|''K''}} 内で {{math|''x'',&nbsp;''y''}} を結ぶ最短経路の最初の3頂点だとする。すると {{math|''xa'',&nbsp;''ab''&nbsp;&isin;&nbsp;''E''}} かつ {{math|''xb''&nbsp;&notin;&nbsp;''E''}} である。{{math|''a''&nbsp;&notin;&nbsp;''S''}} だから、{{math|''ac''&nbsp;&notin;&nbsp;''E''}}であるような頂点 {{math|''c''}} が存在する。{{math|''G''}} の辺極大性より {{math|''G''&nbsp;+&nbsp;''xb''}} の完全マッチング {{math|''M''<sub>1</sub>}} 、 {{math|''G''&nbsp;+&nbsp;''ac''}} の完全マッチング {{math|''M''<sub>2</sub>}} がとれる。{{math|''G''}} 自身は完全マッチングを持たないと仮定しているのだから、{{math|''xb''&nbsp;&isin;&nbsp;''M''<sub>1</sub>}} かつ {{math|''ac''&nbsp;&isin;&nbsp;''M''<sub>2</sub>}} である。

: {{math|''P''}} を、頂点 {{math|''c''}} から始まり、まず {{math|''M''<sub>1</sub>}} に属す辺、次は {{math|''M''<sub>2</sub>}} に属す辺、と交互にたどっていく {{math|''G''}} の極大[[道 (グラフ理論)|経路]]（この条件を守りながらではそれよりも延ばすことができない経路）とする。この経路の終端の状況について考察する。

:経路 {{math|''P''}} は、「特別」な頂点である {{math|''x'',&nbsp;''a'',&nbsp;''b''}} のいずれかに到達しない限り、必ずそれより長く延ばすことができる。なぜなら、頂点 {{math|''c''}} がマッチング {{math|''M''<sub>2</sub>}} では辺 {{math|''ca''}} により接続されていることから、 {{math|''P''}} の最初の辺は {{math|''M''<sub>2</sub>}} に属さない。よって {{math|''c''}} の次の頂点はマッチング {{math|''M''<sub>2</sub>}} では {{math|''c''}} とは異なる頂点と接続されている。この辺はマッチング {{math|''M''<sub>1</sub>}} には属さないから、第3の頂点は {{math|''c''}} とも第2の頂点とも異なる。以下、特別な頂点に到達しない限り全く同様の延長を繰り返すことができる。

:{{math|''v''}} を経路 {{math|''P''}} の最後の頂点とする。もし経路 {{math|''P''}} の最後の辺が {{math|''M''<sub>1</sub>}} に属しているとすると、{{math|''v''}} は {{math|''a''}} でなくてはいけない。なぜなら、さもなければ {{math|''M''<sub>2</sub>}} から辺を選んで経路を延長できるからである（それにより {{math|''x''}} または {{math|''b''}} に達するかもしれない）。この場合、{{math|''C''&nbsp;:&nbsp;{{=}}&nbsp;''P''&nbsp;+&nbsp;''ac''}} と定義する。

:もし経路 {{math|''P''}} の最後の辺が {{math|''M''<sub>2</sub>}} に属しているとすると、この辺は {{math|''ca''}} と隣接していないから、{{math|''v''&nbsp;&isin;&nbsp;{''x'',&nbsp;''b''}&nbsp;}} でなければならない。この場合、 {{math|''C''&nbsp;:&nbsp;{{=}}&nbsp;''P''&nbsp;+&nbsp;''va''&nbsp;+&nbsp;''ac''}} と定義する。

:このとき {{math|''C''}} は {{math|''G''&nbsp;+&nbsp;''ac''}} の偶数長の[[閉路]]で、{{math|''M''<sub>2</sub>}} の元が1本おきに現れる辺集合となっている。よって {{math|''M''&nbsp;:&nbsp;{{=}}&nbsp;''M''<sub>2</sub>&nbsp;&Delta;&nbsp;''C''}} （{{math|&Delta;}} は[[対称差]]）と定義したものは {{math|''G''}} の完全マッチングになる。これは {{math|''G''}} は完全マッチングを持たないとしていた仮定に反する。

== 関連項目 ==
* [[ホールの定理]]
* [[ピーターセンの定理]]

==脚注==
{{reflist}}

==参考文献==
* {{Cite book
 | last=Bondy  | first=J. A.
 | last2=Murty | first2=U. S. R.
 | title=Graph theory with applications | year=1976 | publisher=American Elsevier Pub. Co. | location=New York  | isbn=0-444-19451-7|ref=harv}}
* {{Cite book
 | last1=Lovász    | first1=László | author1-link=László Lovász
 | last2=Plummer | first2=M. D. | author2-link=Michael D. Plummer
 | title=Matching theory | year=1986 | publisher=North-Holland | location=Amsterdam | isbn=0-444-87916-1|ref=harv}}

{{DEFAULTSORT:たつとのていり}}
[[Category:グラフ理論]]
[[Category:数学に関する記事]]