68

ハミルトニアンパスとオイラーパスの違いを教えてください。彼らは似ているようです!

4

9 に答える 9

130

オイラー パスは、すべてのエッジを 1 回だけ通過するパスです。最初の頂点で終了する場合は、オイラー サイクルです。

ハミルトニアン パスは、すべての頂点を 1 回だけ (すべてのエッジではなく) 通過するパスです。最初の頂点で終わる場合、それはハミルトン サイクルです。

オイラー パスでは、頂点を複数回通過することがあります。

ハミルトニアン パスでは、すべてのエッジを通過することはできません。

于 2010-07-16T21:37:53.450 に答える
13

グラフ理論の定義

(一般性の高い順)

  • Walk : 1 つのエッジの終わりが次のエッジの始まりを示す一連のエッジ

  • Trail : エッジを繰り返さないウォーク。すべてのトレイルは散歩です。

  • Path : 各頂点が最大 1 回横断されるウォーク。(パスはオープン ウォークを指すために使用されていましたが、現在は定義が変更されています) 頂点を最大 1 回通過するというプロパティは、エッジも最大 1 回交差することを意味します。したがって、すべてのパスはトレイルです。

ハミルトニアン パスとオイラー トレイル

  • ハミルトニアン パス:グラフ内のすべての頂点を訪れます(パスであるため、正確に 1 回)

  • オイラー トレイル:グラフ内のすべてのエッジを1 回だけ訪れます (これはトレイルであるため、頂点は複数回交差する可能性があります)。

于 2013-01-21T15:50:48.033 に答える
9

オイラー パスは各エッジを 1 回だけ訪れる必要がありますが、ハミルトン パスは各頂点を 1 回だけ訪れる必要があります。

于 2010-07-16T21:37:08.327 に答える
4

それらは関連していますが、依存も相互排他もありません。グラフにオイラー サイクルがある場合、ハミルトニアン サイクルがある場合とない場合があり、その逆もあります。


オイラー サイクルは、グラフ内のすべてのエッジを 1 回だけ訪れます。グラフに 3 つ以上のエッジを持つ頂点がある場合、定義により、サイクルはそれらの頂点を複数回通過します。その結果、頂点は繰り返すことができますが、エッジは繰り返すことができません。

ハミルトニアン サイクルは、グラフ内のすべての頂点を 1 回だけ訪れます(巡回セールスマン問題と同様)。その結果、エッジも頂点も繰り返すことができません。

于 2010-07-16T21:46:03.943 に答える
3

ハミルトニアン パスはすべてのノード (または頂点) を 1 回だけ訪れ、オイラー パスはすべてのエッジを 1 回だけ通過します。

于 2010-07-16T21:37:26.970 に答える
0

オイラーパスは、グラフのすべてのエッジ(注) を1 回だけ使用するグラフです。オイラー回路は、すべてのエッジをカバーした後、開始点に戻るオイラー パスです。

ハミルトン パスは、すべての頂点 (注) を 1 回だけカバーするグラフです。このパスよりも開始点に戻るとき、このパスはハミルトン回路と呼ばれます。

于 2012-10-08T18:06:12.473 に答える