データ構造入門：オイラーグラフとハミルトングラフの基本を解説

この記事では、グラフ理論における重要な概念であるオイラーグラフとハミルトングラフについて解説します。これらを理解する前に、まずグラフにおける「トレイル(小道)」という基本的な概念を押さえておきましょう。

トレイル(小道)とは何か

トレイルとは、辺の列 (v₁, v₂), (v₂, v₃), …, (v_k−1, v_k) で構成される道のことです。このとき、頂点 (v₁, v₂, …, v_k) は同じ頂点を複数回通っても構いませんが、すべての辺は互いに異なる(重複しない)必要があります。

上図のグラフを例にとると、{(B, A), (A, C), (C, D), (D, A), (A, F)} はトレイルの一例です。ただし、頂点 A を2回訪問しているため、これは「単純路(シンプルパス)」とはみなされません。また、始点と終点が同じ頂点になるトレイルは「閉じたトレイル(閉路)」と呼ばれます。

オイラー路(Eulerian Trail)

グラフ G(V, E) におけるオイラー路とは、グラフ内のすべての辺をちょうど1回ずつ通るトレイルのことです。特に、始点に戻ってくる閉じたオイラー路を持つグラフは「オイラーグラフ」と呼ばれます。

言い換えれば、ある頂点から出発して、すべての辺を1回ずつたどりながら出発点へ戻れるとき、そのグラフはオイラーグラフであるといえます。数学者レオンハルト・オイラーは、次の有名な定理を証明しました。

グラフがオイラーグラフであるのは、そのすべての頂点の次数(接続する辺の数)が偶数であるとき、かつそのときに限る。

ハミルトン閉路(Hamiltonian Cycle)

ハミルトン閉路とは、グラフ G のすべての頂点をちょうど1回ずつ通って出発点に戻る閉路のことです。一見するとオイラー路と似ていますが、オイラー路が「辺」に着目するのに対し、ハミルトン閉路は「頂点」に着目する点が大きな違いです。

グラフがハミルトングラフであるための十分条件を与える定理は、これまでに数多く提案されています。しかしながら、任意のグラフがハミルトングラフかどうかを判定する問題は、計算量理論においてNP完全問題として知られており、効率的な解法はまだ発見されていません。