ピーターセンの定理

提供: testwiki
ナビゲーションに移動 検索に移動
ピーターセングラフでの完全マッチング（赤色の辺集合）。ピーターセングラフは橋のない立方体グラフであり、ピーターセンの定理の仮定を満たす。
完全マッチングを持たない（橋が存在する）立方体グラフの例。「橋なし」の条件がピーターセンの定理から落とせないことを示す。

数学におけるピーターセンの定理（ピーターセンのていり、テンプレート:Lang-en-short）はグラフ理論の最初期の結果の一つで、名称は数学者ジュリウス・ピーターセンに由来し、以下を主張する。

定理： テンプレート:仮リンクのない立方体グラフは、必ず完全マッチングを持つ[1]。

言い換えると、もしグラフの全ての頂点がちょうど3本の辺で接続されていて、全ての辺がいずれかの閉路の一部であるならば、どの2つも隣接しないようなグラフの辺集合を上手く選んで、それらの端点を集めたものがグラフの頂点全体と一致するようにできる。

証明

テンプレート:Math を任意の橋のない立方体グラフとする。任意の頂点部分集合 テンプレート:Math に対し、テンプレート:Math が誘導する部分グラフの奇数個の頂点を持つ連結成分の個数 テンプレート:Math が テンプレート:Math 以下であることを示せば、タットの定理から テンプレート:Math が完全マッチングを持つことがわかる。

そこでそのような連結成分を一つ任意にとって テンプレート:Math とする。テンプレート:Math の頂点集合を テンプレート:Math 、両端が テンプレート:Math に属すような テンプレート:Math の辺の総数を テンプレート:Math 、端点の一方が テンプレート:Math に属し、もう一方が テンプレート:Math に属すような テンプレート:Math の辺の総数を テンプレート:Math とする。テンプレート:Math 全体にわたる頂点の次数の和を2通りに数え上げることで、次の等式が得られる。

∑v∈VidegG(v)=3|Vi|=2Mi+mi

中辺は奇数で テンプレート:Math は偶数なので テンプレート:Math は奇数でなければならず、さらに テンプレート:Math は橋を持たないので テンプレート:Math である。

端点の一方が テンプレート:Math に属し、もう一方が テンプレート:Math に属すような テンプレート:Math の辺の総数を テンプレート:Math とする。テンプレート:Math の奇頂点連結成分1つにつき、この条件を満たす辺は3個以上あり、かつ異なる連結成分間での重複はない。よって テンプレート:Math 。一方で テンプレート:Math の全ての頂点の次数は3だから テンプレート:Math。これらをあわせて

|U|≥13m≥o(V−U)

ゆえにタットの定理の前提条件が満たされ、ピーターセンの定理は証明された。

歴史

この定理はデンマークの数学者ジュリウス・ピーターセンに負う。グラフ理論における最初期の結果の一つと考えられる。定理が初めて世に出たのは1891年の論文 "Die Theorie der regulären graphs" においてであった[1]。今日的な基準からすると、ピーターセンの証明は非常に入り組んだものだった。テンプレート:Harvtxt、次いでテンプレート:Harvtxtは、ピーターセンの定理の証明を劇的に簡潔化した。

現代の教科書ではピーターセンの定理はタットの定理の一応用例とされる。

応用

  • 橋のない立方体グラフと、その完全マッチングを一つとる。マッチングに属さない辺集合は "2-factor" （元のグラフと頂点全体が一致するような 2-正則グラフ）を成す。この各連結成分（閉路）にテンプレート:仮リンクをすると、マッチングの各辺は長さ3の道に延長できる（例えば、各辺の端点に順方向の辺を加えればよい）。よって、任意の橋のない立方体グラフはどの2つも辺を共有しない長さ3の道の集合に分解できる[2]。
  • ピーターセンの定理を使うと、任意の極大平面グラフ（どの2頂点を追加的に接続しても平面性が失われるような単純平面グラフ）が、どの2つも辺を共有しない長さ3の道の集合に分解できることも証明できる。
この場合は双対グラフが橋のない立方体グラフになり、ピーターセンの定理より完全マッチングがとれる。マッチングに属さない辺の閉路集合の向き付けを上手く行って、最初の例と同様にマッチングの各辺の両端に向きのついた辺を継いで長さ3の道を作ると、元のグラフでこの道に対応するのが隣接する三角形の5本の辺 "テンプレート:JIS2004フォント" を "Z" 型に通る長さ3の道（中間の辺が三角形の共有辺）になる[3]。
  • ピーターセンの定理を三角メッシュ（triangle mesh）の双対グラフに適用し、マッチングに属さない隣接三角形をつないでいくと、三角メッシュをトライアングルストリップ（triangle strip）の輪の集合に分解できる。元の三角メッシュにさらにいくらかの変形（頂点と辺の追加）を施すことで、1本のトライアングルストリップにすることができる。これは双対グラフがハミルトングラフになるように三角メッシュを変形する手法を与える[4]。

拡張

完全マッチングの数

ラースロー・ロヴァースとテンプレート:仮リンクは、橋のない立方体グラフの完全マッチングの数は、頂点数 テンプレート:Math の指数関数的に増大すると予想した[5]。この予想はまず2部グラフの場合に証明され(テンプレート:Harvtxt)、次いで平面グラフの場合に証明された(テンプレート:Harvtxt、受付は2009年)。一般の橋のない立方体グラフの場合、少なくとも 2n/3656 の完全マッチングが存在することが示されている(テンプレート:Harvtxt、受付は2010年)。

より高い次数の場合

d 次の正則グラフ G の辺連結度が d − 1 以上で、かつ G の頂点数が偶数であれば、完全マッチングが存在する。このときさらに、G の任意の辺に対しそれを含むような完全マッチングが存在することが言える[6]（なお次数 d が奇数のときはテンプレート:仮リンク （handshaking lemma）より頂点数は必ず偶数になるから、これを仮定する必要はなくなる）。

脚注

テンプレート:Reflist

参考文献

テンプレート:Refbegin

テンプレート:Refend

テンプレート:Combin-stub

  1. ↑ 1.0 1.1 テンプレート:Harvtxt.
  2. ↑ 例えば テンプレート:Harvtxt を参照。
  3. ↑ テンプレート:Harvtxt.
  4. ↑ テンプレート:Harvtxt.
  5. ↑ テンプレート:Harvtxt.
  6. ↑ テンプレート:Harvtxt, Theorem 4, p. 285.
「https://ja.wiki.beta.math.wmflabs.org/w/index.php?title=ピーターセンの定理&oldid=11836」から取得