ハミルトン路

ハミルトン路と関連する概念の概要

ハミルトン路（Hamiltonian path）とは、特定のグラフ理論において、すべての頂点を一度だけ訪れる経路のことを指します。この道が閉じられていて、最初の頂点に戻ることができる場合には、ハミルトン閉路（Hamiltonian circuit）と呼ばれます。これらを含むグラフはハミルトングラフ（Hamiltonian graph）と称し、ハミルトン路は含まれていますが、ハミルトン閉路は含まないようなグラフは準ハミルトングラフ（quasi-Hamiltonian graph）と分類されます。

ハミルトン路の判定問題

与えられたグラフがハミルトン路を持っているかどうかを判断する問題は、計算論においてNP完全問題として知られています。つまり、与えられたグラフがハミルトン路を含むかどうかを効率的に判定するアルゴリズムは存在しないと考えられています。また、ハミルトングラフかどうかを検証するには、ハミルトン閉路問題を参照する必要があります。2023年現在、ハミルトングラフかどうかを簡単に判定するための確立した定理はまだ見つかっていないのが現状です。

ハミルトングラフの性質

ハミルトングラフにはいくつかの重要な性質が存在します。

• - ディラックの定理: 頂点数が3以上で、最小次数が頂点数の半分以上である単純グラフはハミルトングラフです。
• - 隣接頂点の条件: グラフGの頂点数が3以上であれば、もし隣接していない2つの頂点uとvが存在し、d(u) + d(v)が頂点数以上であれば、グラフGに(u, v)を加えたG + (u, v)もハミルトングラフとなります。
• - グラフの削除条件: グラフGがハミルトングラフであり、もし辺(u, v)が存在し、d(u) + d(v)がn + 2以上であれば、辺eを削除したグラフG - eもハミルトングラフです。

完全グラフの特性

さらに、完全グラフとハミルトン路に関連する特性も興味深いです。完全グラフK2n+1（頂点数が奇数）はn個のハミルトン閉路に分解されることが示されています。一方、完全グラフK2n（頂点数が偶数）はn-1個のハミルトン閉路と1個の1-正則な全域部分グラフに分解できる特性があります。

関連する定理と概念

ハミルトン路およびその関連概念には、以下のような重要な定理や概念も存在します。

• - 閉路グラフ: 特定の形式のグラフで、すべての頂点を一度だけ訪れて閉じる経路が存在します。
• - ディラックの定理やオーレの定理: ハミルトングラフに関する重要な理論で、特定の条件のもとでハミルトン路や閉路の存在を保証します。
• - Bondy–Chvátalの定理: グラフの構造に関する知見を提供します。
• - オイラー路: すべての辺を一度だけ通る経路ですが、ハミルトン路とは異なる特性を持っています。

これらの理論を通じて、ハミルトン路の研究が進められており、さらなる発見が期待されています。

もう一度検索