ピーターセングラフのソースを表示

{{Infobox graph
 | name = ピーターセングラフ
 | image = [[Image:Petersen graph blue.svg|200px]]
 | image_caption = 典型的なピーターセングラフ。五角形の中に[[五芒星]]形を描き、対応する各頂点を結ぶ。
 | namesake = [[ジュリウス・ピーターセン]]
 | vertices = 10
 | edges = 15
 | automorphisms = 120 (S<sub>5</sub>)
 | radius = 2
 | diameter = 2
 | girth = 5
 | chromatic_number = 3
 | chromatic_index = 4
 | fractional_chromatic_index = 3
 | properties = [[正則グラフ]]<br />[[:en:Strongly regular graph|強正則グラフ]]<br />[[:en:Snark (graph theory)|スナークグラフ]]
}}

[[画像:Petersen graph, two crossings.svg|class=skin-invert-image|thumb|right|辺の交差が2のピーターセングラフ]]
[[画像:Petersen graph, unit distance.svg|class=skin-invert-image|thumb|right|ピーターセングラフは[[単位距離グラフ]]である。平面に各辺の長さが単位距離のグラフとして描ける。]]
[[画像:Petersen graph 2.svg|class=skin-invert-image|thumb|right|ピーターセングラフは準ハミルトングラフである。頂点のどれか1つを削除すると、残ったグラフがハミルトングラフになる。また、この図のように描くと3回[[回転対称性|対称]]になるが、一番上の図などは5回対称である。]]
'''ピーターセングラフ'''（{{lang-en-short|Petersen graph}}）または'''ペテルセングラフ'''とは、10個の頂点と15個の辺からなる[[グラフ理論#無向グラフ|無向グラフ]]である。グラフ理論の様々な問題の例、あるいは反例としてよく使われる。1898年、[[ジュリウス・ピーターセン]]が3色辺彩色できない最小のブリッジのない3-正則グラフとして考案した<ref>{{citation|url= http://www.win.tue.nl/~aeb/drg/graphs/Petersen.html|title=The Petersen graph|first=Andries E.|last=Brouwer}}</ref>。そのため、ピーターセングラフと呼ばれているが、実際には1886年に既に考案されていた<ref>{{citation|first=A. B.|last=Kempe|title=A memoir on the theory of mathematical form|journal=Philosophical Transactions of the Royal Society of London|volume=177|pages=1&ndash;70|date=1886|doi=10.1098/rstl.1886.0002}}</ref>。

== 構成 ==
ピーターセングラフは <math>K_5</math> の{{仮リンク|線グラフ|en|Line graph}}の[[補グラフ]]である。また、<math>KG_{5,2}</math> の[[クネーザーグラフ]]でもある。すなわち、5元の集合の2元部分集合それぞれについて頂点を割り当て、[[素集合|互いに素]]な部分集合に対応する頂点同士を辺で結ぶと、ピーターセングラフになる。

幾何学的には、{{仮リンク|半十二面体|en|hemi-dodecahedron}}の頂点と辺をグラフで表したものと言える。すなわち、[[正十二面体]]の反対側の点、線、面を同じと識別したものである。

== 埋め込み ==
ピーターセングラフは[[平面グラフ]]ではない。一般に非平面グラフなら、[[マイナー (グラフ理論)|マイナー]]として <math>K_5</math> の[[完全グラフ]]か <math>K_{3,3}</math> の[[完全2部グラフ]]があるが、ピーターセングラフでは両方同時にマイナーとして持つ。<math>K_5</math> マイナーは、[[マッチング (グラフ理論)|完全マッチング]]の辺を縮約することで形成され、一番上の図で言えば、短い辺を縮約すればよい。<math>K_{3,3}</math> マイナーは、1つの頂点を削除し（例えば、3回対称の図の中央の頂点）、削除した頂点と隣接していた頂点に付随する辺を縮約することで形成される。

最も典型的なピーターセングラフの描き方は、正五角形の中に五芒星形を描く描き方だが、これでは5箇所で辺が交差する。しかし、もっと交差を少なくする描き方もある。右には交差が2つしかない図も示している。これが最小なので、ピーターセングラフの{{仮リンク|交差数 (グラフ理論)|label=交叉数|en|Crossing number (graph theory)}}は2である。[[トーラス]]上では全く交差させずにピーターセングラフを描ける。つまり、[[向き]]のある[[種数]]が1である。

ピーターセングラフは（交差はあるが）平面上で全ての辺が同じ長さとなるよう描ける。すなわち、[[単位距離グラフ]]である。

ピーターセングラフを交差なしに埋め込める最も単純な向き付け不能[[曲面]]は、[[射影平面]]である。これはピーターセングラフを半十二面体で構築する際に得られる埋め込みである。射影平面埋め込みは、通常のピーターセングラフの中心に[[クロスキャップ]]を置き、五芒星の辺をクロスキャップに沿わせることでも得られる。この場合、6個の五角形の面が現れる。以上からピーターセングラフは向きのない種数も1である。

== 対称性 ==
ピーターセングラフは[[強正則グラフ]]である。また、[[辺推移グラフ|辺推移的]]かつ[[頂点推移グラフ|頂点推移的]]という意味で[[対称グラフ]]でもある。また、14ある3-正則の{{仮リンク|距離正則グラフ|en|Distance-regular graph}}の一つである<ref>[http://www.csse.uwa.edu.au/~gordon/remote/foster/#drgs Cubic symmetric graphs (The Foster Census)]</ref>。

ピーターセングラフの{{仮リンク|グラフ自己同型|label=自己同型群|en|Graph automorphism}}は[[対称群]] <math>S_5</math> である。ピーターセングラフ上の <math>S_5</math> の振る舞いは、クネーザーグラフとしてのそれに従う。隣接する頂点を区別しないピーターセングラフの全ての{{仮リンク|グラフ準同型|label=準同型|en|Graph homomorphism}}は自己同型である。図に示しているように、ピーターセングラフは5回対称としても3対称としても描けるが、対称群全体を表すような図を平面に描くことはできない。

ピーターセングラフは高い対称性があるが[[ケイリーグラフ]]ではない。ケイリーグラフでない連結頂点推移グラフとしては最小である。

== ハミルトン路とハミルトニアン閉路 ==
ピーターセングラフには[[ハミルトン路]]はあるがハミルトン閉路はない。ハミルトン閉路がなく、ブリッジ（それを削除するとグラフが2つの連結グラフに分かれてしまうという辺）のない3-正則グラフとしては最小である。 また、頂点を1つ削除するとハミルトングラフになるので、準ハミルトングラフであり、準ハミルトングラフとしても最小である。

ピーターセングラフは、5種類しか知られていないハミルトン閉路を持たない連結頂点推移グラフである。その5種類以外にそのようなグラフは存在しないという予想がなされている。2-[[連結グラフ|連結]]で ''r''-正則のグラフで、最大 3''r''&nbsp;+&nbsp;1 の頂点を持つグラフは、ハミルトングラフかピーターセングラフのどちらかである<ref>{{citation |first1=D. A. |last1=Holton |first2=J. |last2=Sheehan |url= http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521435943 |title=The Petersen Graph |publisher=Cambridge University Press |date=1993年 |isbn=0-521-43594-3}}, page 32.</ref>。

== 彩色 ==
[[画像:Petersen graph 3-coloring.svg|class=skin-invert-image|thumb|right|ピーターセングラフの頂点を3色に彩色した様子]]

ピーターセングラフの[[グラフ彩色|彩色数]]は 3 であり、隣接する頂点が同じ色にならないように[[グラフ彩色]]したとき、最低でも3色を必要とする。

ピーターセングラフの{{仮リンク|彩色指数|en|Edge coloring}}は 4 である。すなわち、辺彩色では4色が最小の色数である。この証明には4つのケースを具体的に示して、3色では彩色できないことを示す。彩色指数が 4 のブリッジのない連結3-正則グラフであることから、ピーターセングラフは{{仮リンク|スナーク (グラフ理論)|en|Snark (graph theory)|label=スナーク}}であり、スナークとしては最小である。また、1946年までピーターセングラフ以外のスナークは知られていなかった。W. T. Tutte のスナーク予想（全てのスナークはマイナーとしてピーターセングラフを持つ）は、2001年に Robertson, Sanders, Seymour, Thomas が証明し、スナーク定理となった<ref>{{citation |last=Pegg |first=Ed, Jr. |authorlink= |title=Book Review: The Colossal Book of Mathematics |journal=Notices of the American Mathematical Society |volume=49 |issue=9 |date=2002年 |pages=1084-1086 |url= http://www.ams.org/notices/200209/rev-pegg.pdf}}.</ref>。

== その他の性質 ==
* 3-連結でブリッジを持たない。
* 独立数は 4 で、3-部グラフである。
* 3-正則グラフであり、[[支配集合問題]]は 3 で、完全マッチングがある。
* [[半径 (グラフ理論)|半径]] 2 で直径 2 である。直径 2 の3-正則グラフとしては最大である。
* グラフのスペクトルは &minus;2, &minus;2, &minus;2, &minus;2, 1, 1, 1, 1, 1, 3 である。
* [[内周 (グラフ理論)|内周]]5 の 3-正則グラフとしては最小である。唯一の <math>(3,5)</math>-[[ケージ (グラフ理論)|ケージ]]であり、10個しか頂点がないことから、唯一の <math>(3,5)</math>-[[ムーアグラフ]]である。
* [[全域木]]は2000あり、10頂点の3-正則グラフの中で最大である<ref>{{citation | last1 = Jakobson | first1= Dmitry | last2= Rivin | first2= Igor | title = On some extremal problems in graph theory | date = 1999年 | id = {{arxiv|archive = math.CO|id = 9907050}}}}</ref><ref>{{citation | last = Valdes|first= L. | title = Extremal properties of spanning trees in cubic graphs | journal = Congressus Numerantium | date = 1991年 | volume = 85  | pages = 143-160}}</ref>。
* 1-因子分解可能ではない（1-因子分解不可能である）。（＝完全マッチングのパターン3種のみで構成できない。）

== 注釈・出典 ==
{{Reflist}}

== 参考文献 ==
{{Commonscat|Petersen graph}}
* {{citation|first1=Geoffrey|last1=Exoo|first2=Frank|last2=Harary|authorlink2= |first3=Jerald|last3=Kabell|title=The crossing numbers of some generalized Petersen graphs|journal=Mathematica Scandinavica|volume=48|date=1981年|pages=184&ndash;188}}
* {{citation | authorlink = | first = H. S. M. | last = Coxeter | title = Self-dual configurations and regular graphs | journal = Bulletin of the American Mathematical Society | volume = 56 | date = 1950年 | pages = 413-455 | doi = 10.1090/S0002-9904-1950-09407-5}}
* Keller, Mitch. [http://planetmath.org/?op=getobj&from=objects&id=5732 Kneser graphs] on [[PlanetMath]]
* {{citation|first=László|last=Lovász|authorlink= |title=Combinatorial Problems and Exercises|edition=2nd|publisher=North-Holland|date=1993年|isbn= 0-444-81504-X}}
* {{citation|first=Julius|last=Petersen|title=Sur le théorème de Tait|journal=L'Intermédiaire des Mathématiciens|volume=5|date=1898年|pages=225&ndash;227}}
* {{citation | first=Mark E.|last=Watkins | title=A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs | journal=Journal of Combinatorial Theory | date=1969年 | volume=6 | pages=152&ndash;164}}
* {{MathWorld|urlname=PetersenGraph|title=Petersen Graph}}

{{DEFAULTSORT:ひいたあせんくらふ}}

[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]