ピーターセンの定理のソースを表示

[[File:Petersen-graph-factors.svg|thumb|300px|[[ピーターセングラフ]]での完全マッチング（赤色の辺集合）。ピーターセングラフは橋のない立方体グラフであり、ピーターセンの定理の仮定を満たす。]]
[[File:Sylvester counter.svg|thumb|220px|完全マッチングを持たない（橋が存在する）立方体グラフの例。「橋なし」の条件がピーターセンの定理から落とせないことを示す。]]
[[数学]]における'''ピーターセンの定理'''（ピーターセンのていり、{{Lang-en-short|Petersen's theorem}}）は[[グラフ理論]]の最初期の結果の一つで、名称は[[数学者]][[ジュリウス・ピーターセン]]に由来し、以下を主張する。

:'''定理：''' {{仮リンク|橋 (グラフ理論)|en|bridge (graph theory)|label=橋}}のない[[立方体グラフ]]は、必ず[[マッチング (グラフ理論)|完全マッチング]]を持つ<ref name="p1891">{{harvtxt|Petersen|1891}}.</ref>。

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

== 証明 ==
{{math|''G'' {{=}} (''V'', ''E'')}} を任意の橋のない立方体グラフとする。任意の頂点部分集合 {{math|''U'' &sube; ''V''}} に対し、{{math|''V''&nbsp;&minus;&nbsp;''U''}} が[[誘導部分グラフ|誘導する部分グラフ]]の奇数個の頂点を持つ連結成分の個数 {{math|''o''(''V''&nbsp;&minus;&nbsp;''U'')}} が {{math|{{!}}''U''{{!}}}} 以下であることを示せば、[[タットの定理]]から {{math|''G''}} が完全マッチングを持つことがわかる。

そこでそのような連結成分を一つ任意にとって {{math|''G<sub>i</sub>''}} とする。{{math|''G<sub>i</sub>''}} の頂点集合を {{math|''V<sub>i</sub>''}} 、両端が {{math|''G<sub>i</sub>''}} に属すような {{math|''G''}} の辺の総数を {{math|''M<sub>i</sub>''}} 、端点の一方が {{math|''V<sub>i</sub>''}} に属し、もう一方が {{math|''U''}} に属すような {{math|''G''}} の辺の総数を {{math|''m<sub>i</sub>''}} とする。{{math|''V<sub>i</sub>''}} 全体にわたる頂点の[[次数 (グラフ理論)|次数]]の和を2通りに数え上げることで、次の等式が得られる。 

:<math>\sum\nolimits_{v\in V_i} \deg_G(v) = 3 |V_i| = 2 M_i + m_i </math>

中辺は奇数で {{math|2 ''M<sub>i</sub>''}} は偶数なので {{math|''m<sub>i</sub>''}} は奇数でなければならず、さらに {{math|''G''}} は橋を持たないので {{math|''m<sub>i</sub>''&nbsp;≥&nbsp;3}} である。

端点の一方が {{math|''V''&nbsp;&minus;&nbsp;''U''}} に属し、もう一方が {{math|''U''}} に属すような {{math|''G''}} の辺の総数を {{math|''m''}} とする。{{math|''V''&nbsp;&minus;&nbsp;''U''}} の奇頂点連結成分1つにつき、この条件を満たす辺は3個以上あり、かつ異なる連結成分間での重複はない。よって {{math|''m''&nbsp;≥&nbsp;3 ''o''(''V''&nbsp;&minus;&nbsp;''U'')}} 。一方で {{math|''G''}} の全ての頂点の次数は3だから {{math|''m''&nbsp;≤&nbsp;3<nowiki>|</nowiki>''U''<nowiki>|</nowiki>}}。これらをあわせて

:<math>|U|\geq\frac{1}{3}m\geq o(V-U)</math>

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

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

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

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

== 拡張 ==
=== 完全マッチングの数===
[[ラースロー・ロヴァース]]と{{仮リンク|マイケル・D・プラマー|en|Michael D. Plummer}}は、橋のない立方体グラフの完全マッチングの数は、頂点数 {{math|''n''}} の指数関数的に増大すると予想した<ref>{{harvtxt|Lovász|Plummer|1986}}.</ref>。この予想はまず[[2部グラフ]]の場合に証明され({{harvtxt|Voorhoeve|1979}})、次いで平面グラフの場合に証明された({{harvtxt|Chudnovsky|Seymour|2012}}、受付は2009年)。一般の橋のない立方体グラフの場合、少なくとも <math>2^{n/3656}</math> の完全マッチングが存在することが示されている({{harvtxt|Esperet|Kardoš|King|Králʼ|2011}}、受付は2010年)。

===より高い次数の場合===
''d'' 次の正則グラフ ''G'' の[[k-辺連結グラフ|辺連結度]]が ''d''&nbsp;&minus;&nbsp;1 以上で、かつ ''G'' の頂点数が偶数であれば、完全マッチングが存在する。このときさらに、''G'' の任意の辺に対しそれを含むような完全マッチングが存在することが言える<ref>{{harvtxt|Naddef|Pulleyblank|1981}}, Theorem&nbsp;4, p.&nbsp;285.</ref>（なお次数 ''d'' が奇数のときは{{仮リンク|握手補題|en|handshaking lemma}} （handshaking lemma）より頂点数は必ず偶数になるから、これを仮定する必要はなくなる）。

== 脚注 ==
{{reflist|colwidth=30em}}

==参考文献==
{{refbegin|colwidth=30em}}
*{{citation
 | last1 = Biedl | first1 = Therese C. | author1-link = Therese Biedl
 | last2 = Bose | first2 = Prosenjit | author2-link = Jit Bose
 | last3 = Demaine | first3 = Erik D. | author3-link = Erik Demaine
 | last4 = Lubiw | first4 = Anna | author4-link = Anna Lubiw
 | doi = 10.1006/jagm.2000.1132
 | issue = 1
 | journal = Journal of Algorithms
 | mr = 1810434
 | pages = 110–134
 | title = Efficient algorithms for Petersen's matching theorem
 | volume = 38
 | year = 2001}}
*{{citation
 | last1 = Bouchet | first1 = André
 | last2 = Fouquet | first2 = Jean-Luc
 | editor1-last = C. Berge | editor1-first = P. Camion, D. Bresson
 | editor2-last = Sterboul | editor2-first = F.
 | contribution = Trois types de décompositions d'un graphe en chaînes
 | doi = 10.1016/S0304-0208(08)73380-2
 | language = French
 | mr = 0841287
 | pages = 131–141
 | publisher = North-Holland
 | series = North-Holland Mathematics Studies
 | title = Combinatorial Mathematics: Proceedings of the International Colloquium on Graph Theory and Combinatorics (Marseille-Luminy, 1981)
 | volume = 75
 | year = 1983}}
*{{citation
 | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
 | last2 = Seymour | first2 = Paul
 | authorlink2= Paul Seymour (mathematician)
 | doi = 10.1007/s00493-012-2660-9
 | issue = 4
 | journal = [[Combinatorica]]
 | mr = 2965284
 | pages = 403–424
 | title = Perfect matchings in planar cubic graphs
 | volume = 32
 | year = 2012}}
*{{citation
 | last1 = Diks | first1 = Krzysztof
 | last2 = Stanczyk | first2 = Piotr
 | editor1-last = van Leeuwen | editor1-first = Jan | editor1-link = Jan van Leeuwen
 | editor2-last = Muscholl | editor2-first = Anca
 | editor3-last = Peleg | editor3-first = David | editor3-link = David Peleg (computer scientist)
 | editor4-last = Pokorný | editor4-first = Jaroslav
 | editor5-last = Rumpe | editor5-first = Bernhard | editor5-link = Bernhard Rumpe
 | contribution = Perfect matching for biconnected cubic graphs in {{math|O(''n'' log<sup>2</sup> ''n'')}} time
 | doi = 10.1007/978-3-642-11266-9_27
 | pages = 321–333
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = 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
 | volume = 5901
 | year = 2010}}
*{{citation
 | last1 = Esperet | first1 = Louis
 | last2 = Kardoš | first2 = František
 | last3 = King | first3 = Andrew D.
 | last4 = Králʼ | first4 = Daniel | author4-link = Daniel Kráľ
 | last5 = Norine | first5 = Serguei
 | doi = 10.1016/j.aim.2011.03.015
 | issue = 4
 | journal = [[Advances in Mathematics]]
 | mr = 2799808
 | pages = 1646–1664
 | title = Exponentially many perfect matchings in cubic graphs
 | volume = 227
 | year = 2011}}
*{{citation
| doi = 10.2307/1967699
| volume = 27
| issue = 4
| pages = 491–493
| authorlink = Orrin Frink
| last = Frink
| first = Orrin
| title = A proof of Petersen’s theorem
| journal = [[Annals of Mathematics]]
| series = Second Series
| year = 1926
}}
*{{citation
 | last1 = Häggkvist | first1 = Roland
 | last2 = Johansson | first2 = Robert
 | doi = 10.1016/j.disc.2003.11.017
 | issue = 1–3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 2061501
 | pages = 263–266
 | title = A note on edge-decompositions of planar graphs
 | volume = 283
 | year = 2004}}
*{{Citation
| last = König
| first = Dénes
|authorlink=Dénes Kőnig
| title = Theorie der endlichen und unendlichen Graphen;  kombinatorische Topologie der Streckenkomplexe.
| year = 1936
}}
*{{citation
  | last1 = Lovász | first1 = László
  | authorlink1 = László Lovász
  | first2 = M. D. | last2 = Plummer
  | mr = 0859549
  | series = Annals of Discrete Mathematics
  | title = Matching Theory
  | publisher = North-Holland
  | volume = 29
  | year = 1986
  | isbn = 0-444-87916-1
}}
*{{citation
 | last1 = Meenakshisundaram | first1 = Gopi
 | last2 = Eppstein | first2 = David | author2-link = David Eppstein
 | arxiv = cs.CG/0405036
 | contribution = Single-strip triangulation of manifolds with arbitrary topology
 | pages = 371–379
 | series = Computer Graphics Forum
 | title = Proc. 25th Conf. Eur. Assoc. for Computer Graphics (Eurographics '04)
 | doi = 10.1111/j.1467-8659.2004.00768.x
 | volume = 23
 | year = 2004}}
*{{citation
 | last1 = Naddef | first1 = D.
 | last2 = Pulleyblank | first2 = W. R. | author2-link = William R. Pulleyblank
 | doi = 10.1016/0012-365X(81)90006-6
 | issue = 3
 | journal =[[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 613406
 | pages = 283–291
 | title = Matchings in regular graphs
 | volume = 34
 | year = 1981}}.
*{{Citation
| volume = 15
| pages = 193–220
| last = Petersen
| first = Julius 
| authorlink = Julius Petersen
| title = Die Theorie der regulären graphs
| journal = [[Acta Mathematica]]
| year = 1891
| doi = 10.1007/BF02392606
}}
*{{citation|first=Mikkel|last=Thorup|authorlink=Mikkel Thorup|year=2000|pages=343–350|doi=10.1145/335305.335345|contribution=Near-optimal {{Sic|hide=y|fully|-}}dynamic graph connectivity|title=[[Symposium on Theory of Computing|Proc. 32nd ACM Symposium on Theory of Computing]]|isbn=1-58113-184-4|mr=2114549}}
*{{citation
 | authorlink = Marc Voorhoeve
 | last = Voorhoeve | first = Marc
 | doi = 10.1016/1385-7258(79)90012-X
 | issue = 1
 | journal =  [[Indagationes Mathematicae]]
 | mr = 0528221
 | pages = 83–86
 | title = A lower bound for the permanents of certain (0,1)-matrices
 | volume = 82
 | year = 1979}}
{{refend}}

{{Combin-stub}}
{{DEFAULTSORT:ひいたあせんのていり}}
[[Category:グラフ理論]]
[[Category:数学に関する記事]]