導入
| ピーターセングラフ | |
|---|---|
 | |
| 頂点の数 | 10 |
| エッジの数 | 15 |
| 学位分布 | 3-レギュラー |
| 半径 | 2 |
| 直径 | 2 |
| メッシュ | 5 |
| 自己同型性 | 120 ( S5 ) |
| 色彩番号 | 3 |
| クロマチックインデックス | 4 |
| プロパティ | ケージ キュービック 距離推移 距離単位 規則性が高い ムーアグラフ ハイポハミルトニアン ムーアグラフ スナーク 対称 |
ピーターセン グラフは、グラフ理論において、10 個の頂点と 15 個のエッジを持つ特定のグラフです。
これは、グラフ理論のいくつかの問題の例と反例として機能する小さなグラフです。この名前は、エッジが 3 色で色付けできない最小の地峡のない立方体グラフとして 1898 年にこのグラフを紹介した数学者ジュリアス ピーターセンにちなんで命名されました。しかし、このことが初めて言及されたのは 12 年前の 1886 年でした。
Donald Knuth は、『 The Art of Programming』の中で、ピーターセン グラフは「すべてのグラフに何が当てはまるかについての多くの楽観的な予測に対する反例として機能する注目に値する構成」であると説明しています。
建物
ピーターセン グラフは、完全なグラフK 5の折れ線グラフを補ったものです。これは、クネーザー グラフK G 5.2でもあります。したがって、5 つの要素のセットの各ペアの頂点を考慮し、対応するペアが互いに素である場合は 2 つの頂点を接続することによって Petersen グラフを構築することが可能です。
幾何学的には、ピーターセン グラフは、半十二面体、つまり、反対側の頂点、エッジ、面が 2 つずつ識別される十二面体の頂点とエッジによって形成されるグラフです。
プロパティ
一般的なプロパティ
Petersen グラフは (3,5) ケージ、つまり、メッシュが 5 で立方体である頂点の数が最小のグラフです。これは固有の (3,5) ケージであり、そのサイズはムーア境界、つまりケージが持つことができる頂点の数の下限と一致します。このようなグラフはムーアグラフと呼ばれます。
ピーターセン グラフの直径、頂点の最大離心率、および半径、頂点の最小離心率は 2 に等しい。これは、すべての頂点がその中心に属することを意味する。直径2の最大の立方体グラフでもあります。
Petersen グラフは 3 つの頂点が接続され、3 つのエッジが接続されています。つまり、接続されていますが、切断するには少なくとも 3 つの頂点または 3 つのエッジを削除する必要があります。 3次のレギュラーなのでこの数値が最適です。したがって、ピーターセン グラフは最適に接続されたグラフです。
Petersen グラフには 2,000 のスパニング ツリーがあり、10 頂点の立方体グラフの中で最も多くなっています。
ダイビング
Petersen グラフは平面ではありません。非平面グラフには、完全なグラフK 5または完全な二部グラフK 3.3のいずれかが含まれます。 Petersen グラフには両方が含まれています。
最も一般的な平面図は、ピーターセン グラフを五角形に含まれる五角形の形で図式化し、5 つの交差を持ちます。この設計では、交差の数が最小限に抑えられるわけではありません。ピーターセン グラフは 2 つの交差だけで表現できます。トーラス上では、ピーターセン グラフは交差することなく表現できます。したがって、これはトーリック グラフであり、性別は 1 に等しくなります。
ピーターセン グラフを交差せずに埋め込むことができる最も単純な方向付け不可能な面は射影平面です。この埋め込みは、半十二面体からの構築によって与えられます。
ピーターセン グラフは距離単位グラフでもあります。距離 1 にあるすべての点のペアをエッジで接続することにより、ユークリッド平面上の点の集合から取得できます。このような表現では、いくつかのエッジが交差します。
代数的性質
Petersen グラフは非常に規則的です。また、対称的です。つまり、その自己同型性のグループは、そのエッジ、頂点、および円弧上で推移的に作用します。したがって、これはエッジ推移的および頂点推移的でもあります。 Petersen グラフは、頂点が 10 個ある唯一の対称立方体グラフであり、すべての対称立方体グラフを分類するカタログであるFoster Censusでの表記は F10A です。
Petersen グラフの自己同型群は対称群S 5です。ピーターセン グラフ上のS 5のアクションは、クネーザー グラフとして構築された結果として生じます。隣接する頂点を識別しないピーターセン グラフのそれ自体への準同型性は自己同型性です。 Petersen グラフの平面表現は、その対称グループ全体を表すことはできません。
高度な対称性にもかかわらず、ピーターセン グラフはケイリー グラフではなく、ケイリー グラフではない最小の頂点推移グラフです。
Petersen グラフの 特性多項式は、 ( x − 3)( x − 1) 5 ( x + 2) 4です。この特性多項式は整数根のみを許可します。したがって、ピーターセン グラフは積分グラフ、つまりスペクトルが整数で構成されるグラフです。
ハミルトニアン パスとサイクル
Petersen グラフには 240 の異なるハミルトニアン パスがありますが、ハミルトニアンではないため、ハミルトニアン サイクルはありません。これは、ハミルトニアンではない最小の非ブリッジ三次グラフです。これはハイポハミルトニアンでもあります。つまり、ピーターセン グラフから頂点を削除するだけでハミルトニアンになります。これは最小のハイポハミルトニアン グラフです。
有限の頂点推移的かつ非ハミルトニアン接続グラフとして、すべての頂点推移的グラフがハミルトニアンであると述べるロヴァース予想の変形に対する反例を提供します。しかし、予想の正規定式化にはハミルトニアン パスのみが必要なため、ピーターセン グラフによって検証されます。
有限頂点推移グラフと非ハミルトニアン グラフは 5 つだけが知られています: 完全なK 2グラフ、ピーターセン グラフ、コクセター グラフ、およびピーターセン グラフとコクセター グラフから各頂点を三角形に置き換えて得られる 2 つのグラフです。
グラフが 2 接続で、最大 3 r + 1 頂点を持つr正則の場合、 Gはハミルトニアンまたはピーターセン グラフです。
ピーターセン グラフがハミルトニアン サイクルCを認めないことを証明するには、3 つの正規のハミルトニアン グラフを記述し、それらはすべて 5 未満のメッシュを持つため、それらのどれもピーターセン グラフではないことを証明できます。頂点はサイクルCと 5 つの文字列で構成されます。弦がサイクルC内で 2 または 3 の距離にある 2 つの頂点を接続する場合、考慮されるグラフでは 3 サイクルまたは 4 サイクルが認められます。 2 つの文字列がCの 2 つの反対側の頂点を、両方とも 4 の距離にある頂点に接続すると、再び 4 サイクルが発生します。残っている唯一のケースは、メビウスのはしごです。これは、 Cの各頂点をその反対側の頂点 (つまり、距離 5 の頂点) に接続することによって形成されるグラフです。しかし、メビウスのスケールでは 4 サイクルも認められます。 Petersen グラフのメッシュは 5、つまり最短サイクルの長さは5 です。したがって、これはハミルトニアンではありません。
着色
Petersen グラフの彩色数は 3 です。つまり、エッジで接続された 2 つの頂点が異なる色になるように、その頂点を 3 色で着色することが可能です。この数は最小限です。
Petersen グラフの色指数は 4 です。したがって、同じ頂点に入射する 2 つのエッジが常に異なる色になるように、グラフのエッジには 4 つの色が付けられます。この数は最小限です。したがって、ピーターセングラフは、ブリッジのない、立方体で、メッシュが少なくとも 5 で色指数が 4 のスナーク、つまり接続されたグラフです。これは可能な限り最小のスナークであり、ダニーロ ブラヌシャが展示するまで、1898 年から 1946 年まで知られていた唯一のスナークでした。さらに 2 つの例、最初のブラヌシャ スナークと 2 番目のブラヌシャ スナークです。
WT Tutteによって推測され、2001 年に Robertson、Sanders、Seymour、Thomas によって証明された結果であるスナーク定理は、どんなスナークもピーターセン グラフをマイナーなものとして認めると述べています。
ピーターセン グラフの独特の色を数えることができます。これにより、許可される色の数に応じた関数が得られます。これは多項式関数であり、それに関連付けられた多項式は色多項式と呼ばれます。この 10 次の多項式は、厳密に 3 未満のすべての正またはゼロの整数を根として認めます。これは次と等しくなります: ( x − 2)( x − 1) x ( x 7 − 12 x 6 + 67 x 5 − 230 x 4 + 529 x 3 − 814 x 2 + 775 x − 352) 。
グラフの分数カラー インデックスは 3 であり、カラー インデックスとグラフの分数カラー インデックスの差が 1 に等しくなる可能性があることを示しています。ゴールドバーグ-シーモア予想では、これが可能な最大の差であると想定されています。
Petersen グラフのThue 数(色指数の変形) は 5 に等しくなります。