1. 概要

この記事では、グラフ理論の2つの一般的な概念であるハミルトニアンパスとオイラーパスについて説明します。 まず、両方の概念の一般的な定義を示し、いくつかの例を示します。 また、各概念のいくつかの重要なプロパティをリストします。

最後に、2つの概念の大まかな違いを示します。

2. 定義

ハミルトニアンパスとオイラーパスの両方が、2つの頂点間のパスを見つけるためのグラフ理論で使用されます。 それらがどのように異なるかを見てみましょう。

2.1. ハミルトンパス

ハミルトンパスは、グラフの各頂点に1回だけアクセスするパスです。ハミルトンパスは、有向と無向グラフの両方に存在できます。

このスコープでパスの定義について説明することが重要です。これは、すべての頂点が異なるエッジと頂点のシーケンスです。 パス内のエッジのシーケンスは、有限および無限にすることができます。

したがって、パスが頂点を繰り返さずに特定のグラフのすべての頂点をカバーする場合、それはハミルトンパスです。

2.2. オイラーパス

オイラーパスは、各エッジを1回だけ訪問する必要がある散歩ですが、頂点を再訪問することはできます。 オイラーパスは、有向グラフと無向グラフで見つけることができます。

オイラーパスの定義を完了するために、ウォークの定義について説明しましょう。 ウォークは、単純に一連の頂点とエッジで構成されます。 各頂点とエッジは、1回の歩行で複数回表示される可能性があります。 オイラーパスは、各エッジが1回だけ表示されるように制限することにより、歩行を制限します。

つまり、ウォークがグラフのすべてのエッジを1回だけカバーする場合、それはオイラーパスです。

3. 例

3.1. ハミルトンパスの例

いくつかのグラフを見て、ハミルトンパスがあるかどうかを調べてみましょう。

まず、上記のランダムなパスを使用して、経験的に試してみます。 しかし、それはハミルトニアンですか？

ハミルトンパスの定義に従って、パスは、頂点に2回以上アクセスすることなく、グラフのすべての頂点をカバーします。 したがって、パスはハミルトンパスであると言えます。このグラフのハミルトンパスの別の例はです。

別のグラフを取り、それを呼び出しましょう：

私たちの方法をもう一度試して、ランダムなパスを取りましょう。 ハミルトニアンですか？

定義によれば、パスに頂点を複数回含めることはできません。 ここでは、頂点が2回繰り返されていることがわかります。 したがって、パス はハミルトンパスではありません。実際、このグラフにはハミルトンパスはありません。

3.2. オイラーパスの例

それでは、オイラーパスについても同じことを試してみましょう。

グラフでウォークを定義しましょう。 ランダムに選択したサンプルウォークインはです。 Eluerパスの定義に従っていますか？ 確認してみましょう。

散歩は端をカバーします。 それでは、私たちの仕事がオイラーパスの定義を満たしているかどうかを見てみましょう。 オイラーパスの定義に従って、ウォークはエッジを2回以上繰り返さずに、すべてのエッジをカバーする必要があります。 サンプルウォークは、エッジを繰り返さずにグラフのすべてのエッジをカバーしていることがわかります。

したがって、ウォークABCDBEDはオイラーパスであると結論付けることができます。のオイラーパスの別の例はです。

別のグラフを検討するときが来ました。

ここでも、同じ手順に従います。 グラフのランダムウォークを選択しています。 選択したウォークがユーカーパスの定義を満たしているかどうかを調べてみましょう。

それがカバーするエッジはです。 ウォークはグラフのすべてのエッジをカバーしますが、エッジの繰り返しがあり、これはオイラーパスの定義に反します。

したがって、ウォーク はオイラーパスではないと結論付けることができます。グラフを詳細に分析すると、グラフにオイラーパスを含めることができないことがわかります。 の頂点を繰り返さずにすべてのエッジをカバーすることはできません。

4. プロパティ

ハミルトニアンパスとオイラーパスに関連するいくつかの興味深いプロパティがあります。 それらを調べてみましょう。

4.1. ハミルトンパスのプロパティ

の単純なグラフ 頂点にハミルトンパスが含まれている場合

  • グラフには、別個の隣接していない頂点のペアが含まれています
  • そのようなペアごとに、（頂点ペアの次数） （そのペアの最短パスの長さ） ≥

連結グラフの場合、別個の頂点のランダムなペアはです。 今プロパティによると：。

ここで、、は頂点の次数を示し、はの頂点の数を示します。 もう1つの表記は、との間の最短経路を示すために使用されます。

このプロパティをグラフで確認してみましょう。 2つの異なる隣接していない頂点AとDを選択することによって：

.

これは、ここの頂点の総数よりも大きくなります。 したがって、このプロパティは。

ハミルトンパスの場合、常に異なる頂点で開始および終了します。このプロパティは、定義から導出できます。 グラフでは、パスがハミルトンパスであることを示しました。 頂点から始まり、で終わります。 したがって、それはプロパティに従います。

4.2. オイラーパスのプロパティ

グラフにオイラーパスがある場合、グラフには奇数度のほとんどの2つの頂点が含まれている必要があります。

グラフでは、奇数次数の頂点は次数と。 他のすべての頂点の次数は同じです。 したがって、グラフにはオイラーパスがあります。

一方、グラフには4つの奇数次数の頂点があります。 したがって、グラフにオイラーパスを含めることはできません。

オイラーを持つグラフ内のすべての非ゼロ頂点は、単一の連結成分に属している必要があります。 

5. 高レベルの比較

このセクションでは、ハミルトニアンとオイラーパスに関して説明したすべての理論を要約し、整理された表形式で提示しましょう。

6. 結論

この記事では、ハミルトニアンとオイラーパスについて詳しく説明しました。 読者が基本を理解できるように、一般的な定義とそれに続くいくつかの例を示しました。 最後に、説明したすべてのポイントを収集し、2つの概念の高レベルの比較を示しました。