ピーターセンの定理

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

定理： 橋（英語版）のない立方体グラフは、必ず完全マッチングを持つ^[1]。

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

証明[編集]

$G = (V, E)$ を任意の橋のない立方体グラフとする。任意の頂点部分集合 $U \subseteq V$ に対し、 $V - U$ が誘導する部分グラフの奇数個の頂点を持つ連結成分の個数 $o (V - U)$ が $| U |$ 以下であることを示せば、タットの定理から $G$ が完全マッチングを持つことがわかる。

そこでそのような連結成分を一つ任意にとって $G i$ とする。 $G i$ の頂点集合を $V i$ 、両端が $G i$ に属すような $G$ の辺の総数を $M i$ 、端点の一方が $V i$ に属し、もう一方が $U$ に属すような $G$ の辺の総数を $m i$ とする。 $V i$ 全体にわたる頂点の次数の和を2通りに数え上げることで、次の等式が得られる。

\sum \nolimits _{v\in V_{i}}\deg _{G}(v)=3|V_{i}|=2M_{i}+m_{i}

中辺は奇数で $2 M i$ は偶数なので $m i$ は奇数でなければならず、さらに $G$ は橋を持たないので $m i \geq 3$ である。

端点の一方が $V - U$ に属し、もう一方が $U$ に属すような $G$ の辺の総数を $m$ とする。 $V - U$ の奇頂点連結成分1つにつき、この条件を満たす辺は3個以上あり、かつ異なる連結成分間での重複はない。よって $m \geq 3 o (V - U)$ 。一方で $G$ の全ての頂点の次数は3だから $m \leq 3| U |$ 。これらをあわせて

|U|\geq {\frac {1}{3}}m\geq o(V-U)

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

歴史[編集]

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

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

応用[編集]

橋のない立方体グラフと、その完全マッチングを一つとる。マッチングに属さない辺集合は "2-factor" （元のグラフと頂点全体が一致するような 2-正則グラフ）を成す。この各連結成分（閉路）に向き付け（英語版）をすると、マッチングの各辺は長さ3の道に延長できる（例えば、各辺の端点に順方向の辺を加えればよい）。よって、任意の橋のない立方体グラフはどの2つも辺を共有しない長さ3の道の集合に分解できる^[2]。
ピーターセンの定理を使うと、任意の極大平面グラフ（どの2頂点を追加的に接続しても平面性が失われるような単純平面グラフ）が、どの2つも辺を共有しない長さ3の道の集合に分解できることも証明できる。

この場合は双対グラフが橋のない立方体グラフになり、ピーターセンの定理より完全マッチングがとれる。マッチングに属さない辺の閉路集合の向き付けを上手く行って、最初の例と同様にマッチングの各辺の両端に向きのついた辺を継いで長さ3の道を作ると、元のグラフでこの道に対応するのが隣接する三角形の5本の辺 "〼" を "Z" 型に通る長さ3の道（中間の辺が三角形の共有辺）になる^[3]。

ピーターセンの定理を三角メッシュ（triangle mesh）の双対グラフに適用し、マッチングに属さない隣接三角形をつないでいくと、三角メッシュをトライアングルストリップ（triangle strip）の輪の集合に分解できる。元の三角メッシュにさらにいくらかの変形（頂点と辺の追加）を施すことで、1本のトライアングルストリップにすることができる。これは双対グラフがハミルトングラフになるように三角メッシュを変形する手法を与える^[4]。

拡張[編集]

完全マッチングの数[編集]

ラースロー・ロヴァースとマイケル・D・プラマー（英語版）は、橋のない立方体グラフの完全マッチングの数は、頂点数 $n$ の指数関数的に増大すると予想した^[5]。この予想はまず2部グラフの場合に証明され(Voorhoeve (1979))、次いで平面グラフの場合に証明された(Chudnovsky & Seymour (2012)、受付は2009年)。一般の橋のない立方体グラフの場合、少なくとも $2^{n/3656}$ の完全マッチングが存在することが示されている(Esperet et al. (2011)、受付は2010年)。

より高い次数の場合[編集]

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

脚注[編集]

^ ^a ^b Petersen (1891).
^ 例えば Bouchet & Fouquet (1983) を参照。
^ Häggkvist & Johansson (2004).
^ Meenakshisundaram & Eppstein (2004).
^ Lovász & Plummer (1986).
^ Naddef & Pulleyblank (1981), Theorem 4, p. 285.

参考文献[編集]

Biedl, Therese C.; Bose, Prosenjit; Demaine, Erik D.; Lubiw, Anna (2001), “Efficient algorithms for Petersen's matching theorem”, Journal of Algorithms 38 (1): 110–134, doi:10.1006/jagm.2000.1132, MR 1810434
Bouchet, André; Fouquet, Jean-Luc (1983), “Trois types de décompositions d'un graphe en chaînes”, in C. Berge, P. Camion, D. Bresson; Sterboul, F. (French), Combinatorial Mathematics: Proceedings of the International Colloquium on Graph Theory and Combinatorics (Marseille-Luminy, 1981), North-Holland Mathematics Studies, 75, North-Holland, pp. 131–141, doi:10.1016/S0304-0208(08)73380-2, MR0841287
Chudnovsky, Maria; Seymour, Paul (2012), “Perfect matchings in planar cubic graphs”, Combinatorica 32 (4): 403–424, doi:10.1007/s00493-012-2660-9, MR2965284
Diks, Krzysztof; Stanczyk, Piotr (2010), “Perfect matching for biconnected cubic graphs in $O(n log 2 n)$ time”, in van Leeuwen, Jan; Muscholl, Anca; Peleg, David et al., SOFSEM 2010: 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 23–29, 2010, Proceedings, Lecture Notes in Computer Science, 5901, Springer, pp. 321–333, doi:10.1007/978-3-642-11266-9_27
Esperet, Louis; Kardoš, František; King, Andrew D.; Králʼ, Daniel; Norine, Serguei (2011), “Exponentially many perfect matchings in cubic graphs”, Advances in Mathematics 227 (4): 1646–1664, doi:10.1016/j.aim.2011.03.015, MR2799808
Frink, Orrin (1926), “A proof of Petersen’s theorem”, Annals of Mathematics, Second Series 27 (4): 491–493, doi:10.2307/1967699
Häggkvist, Roland; Johansson, Robert (2004), “A note on edge-decompositions of planar graphs”, Discrete Mathematics 283 (1–3): 263–266, doi:10.1016/j.disc.2003.11.017, MR2061501
König, Dénes (1936), Theorie der endlichen und unendlichen Graphen; kombinatorische Topologie der Streckenkomplexe.
Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, 29, North-Holland, ISBN 0-444-87916-1, MR0859549
Meenakshisundaram, Gopi; Eppstein, David (2004), “Single-strip triangulation of manifolds with arbitrary topology”, Proc. 25th Conf. Eur. Assoc. for Computer Graphics (Eurographics '04), Computer Graphics Forum, 23, pp. 371–379, arXiv:cs.CG/0405036, doi:10.1111/j.1467-8659.2004.00768.x
Naddef, D.; Pulleyblank, W. R. (1981), “Matchings in regular graphs”, Discrete Mathematics 34 (3): 283–291, doi:10.1016/0012-365X(81)90006-6, MR613406 .
Petersen, Julius (1891), “Die Theorie der regulären graphs”, Acta Mathematica 15: 193–220, doi:10.1007/BF02392606
Thorup, Mikkel (2000), “Near-optimal fully-dynamic graph connectivity”, Proc. 32nd ACM Symposium on Theory of Computing, pp. 343–350, doi:10.1145/335305.335345, ISBN 1-58113-184-4, MR2114549
Voorhoeve, Marc (1979), “A lower bound for the permanents of certain (0,1)-matrices”, Indagationes Mathematicae 82 (1): 83–86, doi:10.1016/1385-7258(79)90012-X, MR0528221

この項目は、組合せ数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。

[p1891-1] Petersen (1891).

[2] 例えば Bouchet & Fouquet (1983) を参照。

[3] Häggkvist & Johansson (2004).

[4] Meenakshisundaram & Eppstein (2004).

[5] Lovász & Plummer (1986).

[6] Naddef & Pulleyblank (1981), Theorem 4, p. 285.

[1]

[2]

[3]

[4]

[5]

[6]