ハミルトン分解

数学の一分野であるグラフ理論において、与えられたグラフのハミルトン分解は、グラフの辺をハミルトン閉路に分割することです。ハミルトン分解は、無向グラフと有向グラフの両方について研究されてきました。無向グラフの場合、ハミルトン分解は、各因数が連結されているグラフの2 因数分解として記述することもできます。

無向グラフにハミルトン分解が存在するためには、グラフは連結かつ偶数次で正則でなければならない。このような分解を持つ有向グラフは強く連結されており、すべての頂点は互いに同じ入次数と出次数を持つ必要があるが、この次数は偶数である必要はない。^[1]

奇数の頂点を持つすべての完全グラフは、ハミルトン分解を持つ。この結果は、完全グラフを同型な 2 因子に分解するオーバーヴォルフアッハ問題の特殊なケースであり、1892 年にエドゥアール・リュカスによってワレキに帰せられた。ワレキの構築では、頂点を正多角形に配置し、この頂点の部分集合内の完全グラフを多角形をジグザグに横切るハミルトン経路で覆い、各経路は他の経路から の倍数だけ回転する。経路の端を残りの頂点で接続することで、すべての経路をハミルトン閉路に完成させることができる。^[2]${\displaystyle n}$${\displaystyle n-1}$${\displaystyle (n-1)/2}$${\displaystyle \pi /(n-1)}$

-正則グラフの頂点を、置換された頂点の辺の各端点に 1 つずつ頂点が属するクリークに拡張しても、グラフがハミルトン分解を持つかどうかは変わりません。この拡張プロセスの逆、クリークを 1 つの頂点に縮小すると、大きいグラフのハミルトン分解が元のグラフのハミルトン分解に変換されます。逆に、ワレツキの構築をクリークに適用すると、小さいグラフのハミルトン分解が拡張されたグラフのハミルトン分解に拡張されます。^[3]${\displaystyle 2k}$${\displaystyle 2k}$

有向グラフの場合、完全グラフの一種の類似物はトーナメントである。これは、異なる頂点のすべてのペアが、一方から他方へ単一の有向辺で接続されているグラフである。例えば、このようなグラフは、各競技者が他の競技者と対戦するスポーツの総当たり戦のトーナメントの結果を表すことができる。各ゲームの敗者から勝者へは辺が向けられている。 1968年のポール・ケリーの予想^[4] に答えて、ダニエラ・キューンとデリック・オストゥスは、十分に大きな通常のトーナメントにはハミルトン分解が存在することを2012年に証明した。^[5]

4-正則平面グラフの場合、グリンバーグの定理から追加の必要条件を導くことができる。これらの条件を満たさず、ハミルトン分解を持たない4-正則平面グラフの例は、ハーシェルグラフのメディアルグラフである。^[6]

グラフ上のプリズムは、2頂点完全グラフとの直積である。例えば、サイクルグラフ上のプリズムは、幾何プリズムのグラフである。3正則グラフ上のプリズムとして得られる4正則グラフは、ハミルトン分解に関して特に研究されてきた。基礎となる3正則グラフが3頂点連結である場合、結果として得られる4正則プリズムには常にハミルトンサイクルがあり、テストされたすべての例においてハミルトン分解がある。この観察に基づいて、アルスパックとローゼンフェルドは1986年に、3正則3頂点連結グラフ上のすべてのプリズムはハミルトン分解を持つと推測した。^{[7] [8]}

3-正則3頂点連結グラフの多くのクラスは、ハミルトン分解を伴うプリズムを持つことが知られている。特に、これは3-正則グラフが平面かつ二部グラフである場合、ハリングラフである場合、それ自体がプリズムまたはメビウスラダーである場合、または4で割り切れる位数の一般化ピーターセングラフである場合に発生する。^{[8] [9]}

ハミルトン分解を持たない頂点推移グラフ（すべての頂点が他のすべての頂点と対称であるグラフ）は無数に存在する。特に、頂点が群の元を記述し、その要素が群の生成元による乗算を記述するケイリーグラフに当てはまる。ハミルトン分解を持たない6正則ケイリーグラフは無数に存在する。また、ハミルトン分解を持たない任意の大きさの偶数次数のケイリーグラフも存在する。これらのグラフを構築する1つの方法は、対称性を維持し、ハミルトン分解の存在を変えることのないクリークによる反復展開を使用することである。^[3]

4-正則無向グラフには、偶数のハミルトン分解があります。さらに強いことは、4-正則グラフの2つの辺とに対して、同じサイクルに属するハミルトン分解の数は偶数であるということです。-正則グラフにハミルトン分解がある場合、少なくとも3倍の階乗個の分解があります。 ${\displaystyle e}$${\displaystyle f}$${\displaystyle e}$${\displaystyle f}$${\displaystyle 2k}$

${\displaystyle (3k-2)\cdot (3k-5)\cdots 7\cdot 4\cdot 1.}$

例えば、ハミルトン分解を持つ4正則グラフには少なくとも4つのハミルトン分解があり、ハミルトン分解を持つ6正則グラフには少なくとも28のハミルトン分解があります。したがって、ハミルトン分解が一意であるグラフはサイクルグラフのみであることがわかります。^[10]

任意のグラフがハミルトン分解を持つかどうかをテストすることは、有向グラフと無向グラフの両方においてNP完全である。 ^[11] 特に、この問題は指定された偶数次の正則グラフ、例えば4正則グラフに対してNP完全である。

立方グラフの線グラフは4-正則であり、その基となる立方グラフがハミルトン閉路を持つ場合のみ、ハミルトン分解を持つ。^{[12] [13]}結果として、ハミルトン閉路問題の困難なインスタンスの線グラフを含むグラフのクラスに対しては、ハミルトン分解はNP完全のままである。例えば、4-正則平面グラフは立方平面グラフの線グラフを含むため、ハミルトン分解はNP完全である。一方、この同値性は、基となる立方グラフが簡単なハミルトン閉路問題を持つ場合、4-正則線グラフのハミルトン分解が容易であることも意味する。

偶数次のランダム正則グラフはほぼ確実にハミルトン分解を持ち、さらに強力なランダム多項式時間アルゴリズムがあり、これは入力として偶数次のランダム正則グラフが与えられた場合にほぼ確実にハミルトン分解を見つけます。^[14]

• 線形樹状性、最大次数2のサブグラフへの異なる種類の制約付き分割