ピーターセングラフ

ウィキペディア

ピーターセングラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/06 05:36 UTC 版)

ピーターセングラフ
典型的なピーターセングラフ。五角形の中に五芒星形を描き、対応する各頂点を結ぶ。
命名者	ジュリウス・ピーターセン
頂点	10
辺	15
半径	2
直径	2
内周	5
自己同型	120 (S5)
彩色数	3
彩色指数	4
分数彩色指数	3
特性	正則グラフ 強正則グラフ スナークグラフ
テンプレートを表示

辺の交差が2のピーターセングラフ

ピーターセングラフは単位距離グラフである。平面に各辺の長さが単位距離のグラフとして描ける。

ピーターセングラフは準ハミルトングラフである。頂点のどれか1つを削除すると、残ったグラフがハミルトングラフになる。また、この図のように描くと3回対称になるが、一番上の図などは5回対称である。

ピーターセングラフ（英: Petersen graph）またはペテルセングラフとは、10個の頂点と15個の辺からなる無向グラフである。グラフ理論の様々な問題の例、あるいは反例としてよく使われる。1898年、ジュリウス・ピーターセンが3色辺彩色できない最小のブリッジのない3-正則グラフとして考案した^[1]。そのため、ピーターセングラフと呼ばれているが、実際には1886年に既に考案されていた^[2]。

構成

ピーターセングラフは ${\displaystyle K_{5}}$

ピーターセングラフの頂点を3色に彩色した様子

ピーターセングラフの彩色数は 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-正則グラフとしては最小である。唯一の ${\displaystyle (3,5)}$

ウィキメディア・コモンズには、ピーターセングラフに関連するカテゴリがあります。