タットの定理

ウィキペディア

タットの定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/01/20 05:13 UTC 版)

中央の頂点を除くと、頂点数がいずれも5の3個の連結成分が生じる。よってタットの定理より、このグラフは完全マッチングを持たない。

数学の分科、グラフ理論におけるタットの定理（タットのていり、英: Tutte theorem）とは、完全マッチングを持つグラフの特徴付けを与える定理である。名称はウィリアム・トーマス・タットにちなむ。この定理はホールの定理を2部グラフから任意のグラフへと一般化したものであり、またタット-ベルジュの公式の特殊な場合である。

定理

グラフ G = (V, E) が完全マッチングを持つのは、頂点集合 V の任意の部分集合 U に対し、V − U から誘導される部分グラフの、奇数個の頂点を持つ連結成分の個数が高々 |U| 個であるとき、かつそのときに限る。

証明

条件を以下のように書く。

$(*)\qquad \forall U\subseteq V,\quad o(G-U)\leq |U|$

元のグラフ G = (V, E) の辺であるものを実線で示す。b と y は同一の頂点かもしれない。

• そうでない場合は、実はあり得ない。そのことを背理法で示す。

G − S のある連結成分 K が完全グラフではないとする。このとき xy ∉ E となる2頂点 x, y ∈ K が選べる。x, a, b ∈ K を、K 内で x, y を結ぶ最短経路の最初の3頂点だとする。すると xa, ab ∈ E かつ xb ∉ E である。a ∉ S だから、ac ∉ Eであるような頂点 c が存在する。G の辺極大性より G + xb の完全マッチング M₁ 、 G + ac の完全マッチング M₂ がとれる。G 自身は完全マッチングを持たないと仮定しているのだから、xb ∈ M₁ かつ ac ∈ M₂ である。

P を、頂点 c から始まり、まず M₁ に属す辺、次は M₂ に属す辺、と交互にたどっていく G の極大経路（この条件を守りながらではそれよりも延ばすことができない経路）とする。この経路の終端の状況について考察する。

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

v を経路 P の最後の頂点とする。もし経路 P の最後の辺が M₁ に属しているとすると、v は a でなくてはいけない。なぜなら、さもなければ M₂ から辺を選んで経路を延長できるからである（それにより x または b に達するかもしれない）。この場合、C : = P + ac と定義する。

もし経路 P の最後の辺が M₂ に属しているとすると、この辺は ca と隣接していないから、v ∈ {x, b}  でなければならない。この場合、 C : = P + va + ac と定義する。

このとき C は G + ac の偶数長の閉路で、M₂ の元が1本おきに現れる辺集合となっている。よって M : = M₂ Δ C （Δ は対称差）と定義したものは G の完全マッチングになる。これは G は完全マッチングを持たないとしていた仮定に反する。

関連項目

• ホールの定理
• ピーターセンの定理

参考文献

• Bondy, J. A.; Murty, U. S. R. (1976). Graph theory with applications. New York: American Elsevier Pub. Co.. ISBN 0-444-19451-7. 
• Lovász, László; Plummer, M. D. (1986). Matching theory. Amsterdam: North-Holland. ISBN 0-444-87916-1.