全辺を1回通るオイラー路
無向辺の一覧から、各辺を正確に1回通る経路の存在と実際の通過順を確認します。
例の値が入力されています。直接確認するか、値を変更してみてください。
入力はブラウザで処理されます。再読み込みすると例の値に戻ります。
使い方と例
辺のある頂点が連結し、奇数次数の頂点が0または2個ならHierholzer法で経路を構成します。
辺1–2、2–3、3–1は1→2→3→1の順で各辺を1回通れます。
1〜50ノード・1〜200辺です。並行辺と自己ループを別々の辺として保持します。辺のない孤立頂点は通過対象から除外します。 浮動小数点の結果は最大有効数字12桁で表示します。
よくある質問
オイラー路は頂点を再訪できますか?
はい。制限は各辺を1回使うことであり、各頂点を1回だけ訪れる問題とは異なります。
オイラー路がない場合に追加辺を提案しますか?
いいえ。存在しないことを示すだけで、辺の複製や最短迂回路は計算しません。
計算基準と参考資料
- NetworkX: Eulerian paths
無向グラフの各辺を1回ずつ使う経路。