ハミルトニアンパスとオイラーパスの違いを教えてください。彼らは似ているようです!
9 に答える
オイラー パスは、すべてのエッジを 1 回だけ通過するパスです。最初の頂点で終了する場合は、オイラー サイクルです。
ハミルトニアン パスは、すべての頂点を 1 回だけ (すべてのエッジではなく) 通過するパスです。最初の頂点で終わる場合、それはハミルトン サイクルです。
オイラー パスでは、頂点を複数回通過することがあります。
ハミルトニアン パスでは、すべてのエッジを通過することはできません。
グラフ理論の定義
(一般性の高い順)
Walk : 1 つのエッジの終わりが次のエッジの始まりを示す一連のエッジ
Trail : エッジを繰り返さないウォーク。すべてのトレイルは散歩です。
Path : 各頂点が最大 1 回横断されるウォーク。(パスはオープン ウォークを指すために使用されていましたが、現在は定義が変更されています) 頂点を最大 1 回通過するというプロパティは、エッジも最大 1 回交差することを意味します。したがって、すべてのパスはトレイルです。
ハミルトニアン パスとオイラー トレイル
ハミルトニアン パス:グラフ内のすべての頂点を訪れます(パスであるため、正確に 1 回)
オイラー トレイル:グラフ内のすべてのエッジを1 回だけ訪れます (これはトレイルであるため、頂点は複数回交差する可能性があります)。
オイラー パスは各エッジを 1 回だけ訪れる必要がありますが、ハミルトン パスは各頂点を 1 回だけ訪れる必要があります。
それらは関連していますが、依存も相互排他もありません。グラフにオイラー サイクルがある場合、ハミルトニアン サイクルがある場合とない場合があり、その逆もあります。
オイラー サイクルは、グラフ内のすべてのエッジを 1 回だけ訪れます。グラフに 3 つ以上のエッジを持つ頂点がある場合、定義により、サイクルはそれらの頂点を複数回通過します。その結果、頂点は繰り返すことができますが、エッジは繰り返すことができません。
ハミルトニアン サイクルは、グラフ内のすべての頂点を 1 回だけ訪れます(巡回セールスマン問題と同様)。その結果、エッジも頂点も繰り返すことができません。
ハミルトニアン パスはすべてのノード (または頂点) を 1 回だけ訪れ、オイラー パスはすべてのエッジを 1 回だけ通過します。
オイラーパスは、グラフのすべてのエッジ(注) を1 回だけ使用するグラフです。オイラー回路は、すべてのエッジをカバーした後、開始点に戻るオイラー パスです。
ハミルトン パスは、すべての頂点 (注) を 1 回だけカバーするグラフです。このパスよりも開始点に戻るとき、このパスはハミルトン回路と呼ばれます。