各エッジまたは各頂点を 1 回だけ交差する必要があるという制限はありません。
そのようなパスの存在に必要かつ十分なグラフのプロパティ (オイラーパスの存在のためのノードの次数など)、または存在するか存在しないかを証明する既知のアルゴリズム (おそらく開始エッジからすべてのエッジを通る最小パスを見つける)?
いくつかの可能性を検討しましたが、最も強力なものは、強く接続されたコンポーネントを単一のスーパーノードに折りたたむことであり、結果のグラフがすべてのエッジをカバーする単純な「リンクされたリスト」のようなグラフであるかどうかを確認します (これは単純で、開始ノードから歩いているだけです/スーパーノードは常に現在のノードから単一のエッジを話し、発信エッジ (スーパーノードの場合はすべての内部エッジ) を訪問済みとしてカウントし、リーフ ノードに到達すると、すべてのエッジがカウントされたかどうかを確認します)。このソリューションでは、元のエッジが冗長になったとしてもすべての元のエッジを保存することが重要です (たとえば、接続されたコンポーネント A、B、C をスーパーノード S に折りたたんだ後、F から A、F から B、F から C へのエッジがなければならない場合)。簡略化されたグラフで同じスーパーノード S を指していても、すべて保存されます)。表現が不適切でしたら申し訳ありませんが、
もっと簡単な方法はありますか？または、サイクル/接続されたコンポーネントを処理するためのより良いアルゴリズムですか? グラフが非巡回の場合、解くのは非常に簡単に見えるからです。