ピーターセングラフ
ピーターセングラフは、グラフ理論の分野で非常に重要な位置を占める、10個の点と15本の線で構成される無向グラフです。このグラフは、その独特な構造と多彩な性質から、数多くのグラフ理論的な問題において、具体的な例や、時には反例として頻繁に参照されます。
その名は、1898年にデンマークの数学者ジュリウス・ピーターセンが、辺を取り除いても連結性が失われない（ブリッジを持たない）3-正則グラフの中で、3色で辺を塗り分けられない最小の例として紹介したことに由来します。ただし、実際にはこれより前の1886年には既にその存在が確認されていました。
ピーターセングラフの構成方法にはいくつかのアプローチがあります。一つは、5つの頂点を持つ完全グラフ `K₅` の線グラフ（元の辺を頂点とし、元のグラフで共通の頂点を持つ辺同士を辺で結んだグラフ）の補集合として得られるというものです。また、より抽象的な定義としては、クネーザーグラフ `KG₅,₂` としても知られています。これは、5つの要素からなる集合から、2つの要素を選ぶ全ての組み合わせを頂点と見なし、選ばれた2つの組み合わせが互いに共通の要素を持たない場合にその頂点間に辺を結ぶ、という規則で定義されます。
幾何学的な視点からは、ピーターセングラフは半十二面体の骨組み、すなわち頂点と辺の関係を表していると解釈できます。これは、正十二面体において、ちょうど反対側に位置する点、線、面を同じものと見なした場合に得られる構造に対応します。
ピーターセングラフは、平面上に辺が交差することなく描くことができない「非平面グラフ」です。非平面グラフは通常、完全グラフ `K₅` または完全2部グラフ `K₃,₃` のいずれかをマイナー（辺の縮約などによって得られる部分構造）として含みますが、ピーターセングラフはこれら両方を同時にマイナーとして持ちます。
最も一般的なピーターセングラフの図示方法は、一つの正五角形の中に五芒星形を描くものですが、この描き方では辺が5箇所で交差してしまいます。辺の交差を最小限に抑える描き方も存在し、その最小値は2であることが知られています。このため、ピーターセングラフの交叉数は2です。しかし、平面以外の曲面、例えばトーラス上では、辺を一切交差させることなく描くことが可能です。これにより、向きのある種数は1となります。また、射影平面上でも交差なしに埋め込むことができ、これは半十二面体としての構築とも対応しています。射影平面への埋め込みは、グラフの中央にクロスキャップを配置し、五芒星の辺をそれに沿わせる方法でも実現でき、この際には6個の五角形の面が現れます。このことから、ピーターセングラフの向きのない種数も1となります。
ピーターセングラフは高度な対称性を持つグラフです。全ての頂点や辺が同じように扱われる（頂点推移的かつ辺推移的）という意味で対称グラフであり、さらに強正則グラフや距離正則グラフでもあります。グラフの構造を保つ変換である自己同型写像の全体がなす群は、5つの要素の置換全体からなる対称群 `S₅` と同型です。この対称性は、クネーザーグラフ `KG₅,₂` としての性質に由来します。これほど高い対称性を持つにもかかわらず、ピーターセングラフはケイリーグラフではありません。連結かつ頂点推移的でありながらケイリーグラフではないグラフの中で、ピーターセングラフは最も小さい例として知られています。
ピーターセングラフは、グラフ理論におけるハミルトン性の議論においても重要な存在です。このグラフには、全ての頂点を一度だけ通る「ハミルトン路」は存在しますが、始点と終点が同じである「ハミルトン閉路」は存在しません。ブリッジを持たない3-正則グラフの中でハミルトン閉路を持たない最小のグラフとして、ピーターセン自身が考案した際の動機となった性質でもあります。また、どの頂点を一つ削除してもハミルトン閉路を持つグラフになるため、「準ハミルトングラフ」に分類され、これも最小の例の一つです。ハミルトン閉路を持たない連結頂点推移グラフは、現在までに5種類しか見つかっておらず、ピーターセングラフはその一つです。
グラフの彩色性に関する議論でも、ピーターセングラフは重要な役割を果たします。隣り合う頂点が同じ色にならないように色を塗る際に必要な色の最小数である「彩色数」は3です。また、隣り合う辺が同じ色にならないように辺を彩色する際に必要な色の最小数である「彩色指数」は4となります。彩色指数が4のブリッジを持たない連結3-正則グラフであることから、ピーターセングラフは「スナーク」と呼ばれる特殊なグラフの一種に分類されます。ピーターセングラフは最小のスナークであり、1946年までこれ以外のスナークは知られていませんでした。全てのスナークはピーターセングラフをマイナーとして含むというW. T. Tutteの予想は、2001年に証明され「スナーク定理」として確立されています。
他にも、ピーターセングラフは様々な興味深い性質を持ちます。
どの2頂点をとっても、それらを結ぶ経路が最低3本存在する「3-連結グラフ」であり、ブリッジを持ちません。
互いに隣り合わない頂点の集合（独立集合）の最大サイズは4です。
グラフ上の点から最も遠い点までの距離（直径）と、中心から最も遠い点までの距離（半径）はともに2であり、直径2の3-正則グラフとしては最大の頂点数（10頂点）を持ちます。
グラフ構造の重要な特性を示す「グラフのスペクトル」は、{-2, -2, -2, -2, 1, 1, 1, 1, 1, 3} です。
閉路の中で最も短いものの長さ（内周）は5であり、内周5を持つ3-正則グラフとしては最小の例です。また、特定の条件を満たすケージグラフやムーアグラフとしても知られています。
全ての辺を通る全域木の数は2000であり、10頂点の3-正則グラフの中で最も多いことが確認されています。
* グラフの全ての頂点をちょうど一度だけ通るような辺の集合（完全マッチング）のパターン3つだけではグラフ全体を構成できない性質（1-因子分解可能ではない）を持ちます。
このように、ピーターセングラフは比較的少ない頂点数ながら、グラフ理論における基本的な定義から高度な定理に至るまで、多岐にわたる概念を理解するための豊穣な源となっています。
その名は、1898年にデンマークの数学者ジュリウス・ピーターセンが、辺を取り除いても連結性が失われない（ブリッジを持たない）3-正則グラフの中で、3色で辺を塗り分けられない最小の例として紹介したことに由来します。ただし、実際にはこれより前の1886年には既にその存在が確認されていました。
構成
ピーターセングラフの構成方法にはいくつかのアプローチがあります。一つは、5つの頂点を持つ完全グラフ `K₅` の線グラフ（元の辺を頂点とし、元のグラフで共通の頂点を持つ辺同士を辺で結んだグラフ）の補集合として得られるというものです。また、より抽象的な定義としては、クネーザーグラフ `KG₅,₂` としても知られています。これは、5つの要素からなる集合から、2つの要素を選ぶ全ての組み合わせを頂点と見なし、選ばれた2つの組み合わせが互いに共通の要素を持たない場合にその頂点間に辺を結ぶ、という規則で定義されます。
幾何学的な視点からは、ピーターセングラフは半十二面体の骨組み、すなわち頂点と辺の関係を表していると解釈できます。これは、正十二面体において、ちょうど反対側に位置する点、線、面を同じものと見なした場合に得られる構造に対応します。
埋め込み
ピーターセングラフは、平面上に辺が交差することなく描くことができない「非平面グラフ」です。非平面グラフは通常、完全グラフ `K₅` または完全2部グラフ `K₃,₃` のいずれかをマイナー（辺の縮約などによって得られる部分構造）として含みますが、ピーターセングラフはこれら両方を同時にマイナーとして持ちます。
最も一般的なピーターセングラフの図示方法は、一つの正五角形の中に五芒星形を描くものですが、この描き方では辺が5箇所で交差してしまいます。辺の交差を最小限に抑える描き方も存在し、その最小値は2であることが知られています。このため、ピーターセングラフの交叉数は2です。しかし、平面以外の曲面、例えばトーラス上では、辺を一切交差させることなく描くことが可能です。これにより、向きのある種数は1となります。また、射影平面上でも交差なしに埋め込むことができ、これは半十二面体としての構築とも対応しています。射影平面への埋め込みは、グラフの中央にクロスキャップを配置し、五芒星の辺をそれに沿わせる方法でも実現でき、この際には6個の五角形の面が現れます。このことから、ピーターセングラフの向きのない種数も1となります。
対称性
ピーターセングラフは高度な対称性を持つグラフです。全ての頂点や辺が同じように扱われる（頂点推移的かつ辺推移的）という意味で対称グラフであり、さらに強正則グラフや距離正則グラフでもあります。グラフの構造を保つ変換である自己同型写像の全体がなす群は、5つの要素の置換全体からなる対称群 `S₅` と同型です。この対称性は、クネーザーグラフ `KG₅,₂` としての性質に由来します。これほど高い対称性を持つにもかかわらず、ピーターセングラフはケイリーグラフではありません。連結かつ頂点推移的でありながらケイリーグラフではないグラフの中で、ピーターセングラフは最も小さい例として知られています。
ハミルトン路と閉路
ピーターセングラフは、グラフ理論におけるハミルトン性の議論においても重要な存在です。このグラフには、全ての頂点を一度だけ通る「ハミルトン路」は存在しますが、始点と終点が同じである「ハミルトン閉路」は存在しません。ブリッジを持たない3-正則グラフの中でハミルトン閉路を持たない最小のグラフとして、ピーターセン自身が考案した際の動機となった性質でもあります。また、どの頂点を一つ削除してもハミルトン閉路を持つグラフになるため、「準ハミルトングラフ」に分類され、これも最小の例の一つです。ハミルトン閉路を持たない連結頂点推移グラフは、現在までに5種類しか見つかっておらず、ピーターセングラフはその一つです。
彩色
グラフの彩色性に関する議論でも、ピーターセングラフは重要な役割を果たします。隣り合う頂点が同じ色にならないように色を塗る際に必要な色の最小数である「彩色数」は3です。また、隣り合う辺が同じ色にならないように辺を彩色する際に必要な色の最小数である「彩色指数」は4となります。彩色指数が4のブリッジを持たない連結3-正則グラフであることから、ピーターセングラフは「スナーク」と呼ばれる特殊なグラフの一種に分類されます。ピーターセングラフは最小のスナークであり、1946年までこれ以外のスナークは知られていませんでした。全てのスナークはピーターセングラフをマイナーとして含むというW. T. Tutteの予想は、2001年に証明され「スナーク定理」として確立されています。
その他の性質
他にも、ピーターセングラフは様々な興味深い性質を持ちます。
どの2頂点をとっても、それらを結ぶ経路が最低3本存在する「3-連結グラフ」であり、ブリッジを持ちません。
互いに隣り合わない頂点の集合（独立集合）の最大サイズは4です。
グラフ上の点から最も遠い点までの距離（直径）と、中心から最も遠い点までの距離（半径）はともに2であり、直径2の3-正則グラフとしては最大の頂点数（10頂点）を持ちます。
グラフ構造の重要な特性を示す「グラフのスペクトル」は、{-2, -2, -2, -2, 1, 1, 1, 1, 1, 3} です。
閉路の中で最も短いものの長さ（内周）は5であり、内周5を持つ3-正則グラフとしては最小の例です。また、特定の条件を満たすケージグラフやムーアグラフとしても知られています。
全ての辺を通る全域木の数は2000であり、10頂点の3-正則グラフの中で最も多いことが確認されています。
* グラフの全ての頂点をちょうど一度だけ通るような辺の集合（完全マッチング）のパターン3つだけではグラフ全体を構成できない性質（1-因子分解可能ではない）を持ちます。
このように、ピーターセングラフは比較的少ない頂点数ながら、グラフ理論における基本的な定義から高度な定理に至るまで、多岐にわたる概念を理解するための豊穣な源となっています。
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。