0

標準的な定義に基づくと、オイラー パスは、すべてのエッジを 1 回だけ訪れるグラフ内のパスです。

現在、有向グラフでオイラー パスを見つけようとしています。オイラー回路のアルゴリズムを知っています。グラフにオイラー回路がある場合、オイラーパスがあることは自明のようです。 ソース:geeksforgeeks

[画像ソース: geeksforgeeks.org]

したがって、オイラー回路を持つ上記の有向グラフには、オイラーパスもあります。

ここでエッジを削除すると、4 から 0 に変更され、オイラー回路ではなくなります。

  1. 頂点 0 から DFS を開始すると、まだオイラー パスがあります。
  2. 頂点 3 から開始する場合、オイラー パスがありません

それで、有向グラフがオイラーパスであるためにオイラー回路になければならないというのは要件ですか？私は、オイラーパスはオイラー回路よりも制限が少ないはずだと考えました。

オイラーパスにはなるがオイラー回路にはならない有向グラフはありますか。

4

3 に答える 3

4

それで、有向グラフがオイラーパスであるためにオイラー回路になければならないというのは要件ですか？

いいえ

オイラー経路はオイラー回路よりも制限が少ないはずだと思いました。

正しい

オイラーパスにはなるがオイラー回路にはならない有向グラフはありますか。

はい

あなたの混乱は、異なるノードから開始する有向グラフを DFS すると、異なるノードから開始すると一部のノードにアクセスできない可能性があるため、異なる結果が得られる可能性があるという事実に由来すると思います。これは、オイラー パス/トレイルの定義とは関係ありません。有向グラフでオイラー パスの検索を「実装」するには、すべてのノードから DFS を実行する必要があります。すべての結果が False を返した (オイラー パスが見つからなかった) 場合にのみ、オイラー パスが存在しないことが確実にわかります。 . オイラー サイクルがある場合は、DFS を開始してオイラー パスを見つけることができるノードが必要です。

于 2014-12-20T21:40:10.727 に答える
1

はい、オイラー経路であるがオイラー回路ではないグラフがたくさんあります。を削除した後のグラフと同じ4->0です。

グラフにオイラー回路がある場合、オイラー パスを見つけるのは簡単です。すべてのノードから開始すると、すべてのノードが回路内にあるため、オイラー パスを見つけることができますが、オイラー回路がない場合は開始できません。オイラーパスを見つけたい任意のノードから。ノードの 1 つだけがパスの開始となり、他のノードを選択するとパスが見つからない可能性があるためです。

簡単な方法の 1 つは、すべてのノードから dfs を実行し、それらのいずれかから始まるオイラー パスがあるかどうかを確認することです。これは、O( V 2 + E * V)の複雑さがあるため、最も効率の悪いアルゴリズムです。

複数の優れたアプローチがあり、そのうちの 1 つをここで見つけることができます。O( V + E )の複雑さを持ちV、以前のアルゴリズムよりも時間が優れています。

于 2014-12-21T07:50:42.163 に答える
-1

グラフがオイラー回路/パスを持つための要件:

  • 回路 (パスとしてもカウントされます): 次数が奇数の頂点はありません
  • パス (回路なし): 2 つの頂点の次数が奇数です。この場合、パスは奇数頂点の 1 つで始まり、他の頂点で終わります。
于 2016-12-20T19:33:07.503 に答える