ピーターセングラフ
ウィキペディアから
Remove ads
ピーターセングラフ（英: Petersen graph）またはペテルセングラフとは、10個の頂点と15個の辺からなる無向グラフである。グラフ理論の様々な問題の例、あるいは反例としてよく使われる。1898年、ジュリウス・ピーターセンが3色辺彩色できない最小のブリッジのない3-正則グラフとして考案した[1]。そのため、ピーターセングラフと呼ばれているが、実際には1886年に既に考案されていた[2]。
ピーターセングラフは の線グラフの補グラフである。また、 のクネーザーグラフでもある。すなわち、5元の集合の2元部分集合それぞれについて頂点を割り当て、互いに素な部分集合に対応する頂点同士を辺で結ぶと、ピーターセングラフになる。
幾何学的には、半十二面体の頂点と辺をグラフで表したものと言える。すなわち、正十二面体の反対側の点、線、面を同じと識別したものである。
ピーターセングラフは平面グラフではない。一般に非平面グラフなら、マイナーとして の完全グラフか の完全2部グラフがあるが、ピーターセングラフでは両方同時にマイナーとして持つ。 マイナーは、完全マッチングの辺を縮約することで形成され、一番上の図で言えば、短い辺を縮約すればよい。 マイナーは、1つの頂点を削除し（例えば、3回対称の図の中央の頂点）、削除した頂点と隣接していた頂点に付随する辺を縮約することで形成される。
最も典型的なピーターセングラフの描き方は、正五角形の中に五芒星形を描く描き方だが、これでは5箇所で辺が交差する。しかし、もっと交差を少なくする描き方もある。右には交差が2つしかない図も示している。これが最小なので、ピーターセングラフの交叉数は2である。トーラス上では全く交差させずにピーターセングラフを描ける。つまり、向きのある種数が1である。
ピーターセングラフは（交差はあるが）平面上で全ての辺が同じ長さとなるよう描ける。すなわち、単位距離グラフである。
ピーターセングラフを交差なしに埋め込める最も単純な向き付け不能曲面は、射影平面である。これはピーターセングラフを半十二面体で構築する際に得られる埋め込みである。射影平面埋め込みは、通常のピーターセングラフの中心にクロスキャップを置き、五芒星の辺をクロスキャップに沿わせることでも得られる。この場合、6個の五角形の面が現れる。以上からピーターセングラフは向きのない種数も1である。
Remove ads
ピーターセングラフは強正則グラフである。また、辺推移的かつ頂点推移的という意味で対称グラフでもある。また、14ある3-正則の距離正則グラフの一つである[3]。
ピーターセングラフの自己同型群は対称群 である。ピーターセングラフ上の の振る舞いは、クネーザーグラフとしてのそれに従う。隣接する頂点を区別しないピーターセングラフの全ての準同型は自己同型である。図に示しているように、ピーターセングラフは5回対称としても3対称としても描けるが、対称群全体を表すような図を平面に描くことはできない。
ピーターセングラフは高い対称性があるがケイリーグラフではない。ケイリーグラフでない連結頂点推移グラフとしては最小である。
Remove ads
ピーターセングラフにはハミルトン路はあるがハミルトン閉路はない。ハミルトン閉路がなく、ブリッジ（それを削除するとグラフが2つの連結グラフに分かれてしまうという辺）のない3-正則グラフとしては最小である。 また、頂点を1つ削除するとハミルトングラフになるので、準ハミルトングラフであり、準ハミルトングラフとしても最小である。
ピーターセングラフは、5種類しか知られていないハミルトン閉路を持たない連結頂点推移グラフである。その5種類以外にそのようなグラフは存在しないという予想がなされている。2-連結で r-正則のグラフで、最大 3r + 1 の頂点を持つグラフは、ハミルトングラフかピーターセングラフのどちらかである[4]。
ピーターセングラフの彩色数は 3 であり、隣接する頂点が同じ色にならないようにグラフ彩色したとき、最低でも3色を必要とする。
ピーターセングラフの彩色指数は 4 である。すなわち、辺彩色では4色が最小の色数である。この証明には4つのケースを具体的に示して、3色では彩色できないことを示す。彩色指数が 4 のブリッジのない連結3-正則グラフであることから、ピーターセングラフはスナークであり、スナークとしては最小である。また、1946年までピーターセングラフ以外のスナークは知られていなかった。W. T. Tutte のスナーク予想（全てのスナークはマイナーとしてピーターセングラフを持つ）は、2001年に Robertson, Sanders, Seymour, Thomas が証明し、スナーク定理となった[5]。
- 3-連結でブリッジを持たない。
- 独立数は 4 で、3-部グラフである。
- 3-正則グラフであり、支配集合問題は 3 で、完全マッチングがある。
- 半径 2 で直径 2 である。直径 2 の3-正則グラフとしては最大である。
- グラフのスペクトルは −2, −2, −2, −2, 1, 1, 1, 1, 1, 3 である。
- 内周5 の 3-正則グラフとしては最小である。唯一の -ケージであり、10個しか頂点がないことから、唯一の -ムーアグラフである。
- 全域木は2000あり、10頂点の3-正則グラフの中で最大である[6][7]。
- 1-因子分解可能ではない（1-因子分解不可能である）。（＝完全マッチングのパターン3種のみで構成できない。）
Remove ads
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
Remove ads