如何確定有向圖是否具有從某個節點開始消耗所有邊的路徑？

Question

有沒有限制，你必須越過每個邊緣只有一次，或每個頂點。

對於這種路徑的存在（如歐拉路徑存在的節點度數），還是某種已知算法證明存在或不存在該圖的某些屬性是必要和充分的？ t一個（也許找到從開始的所有邊的最小路徑）？

我已經考慮了幾種可能性，其中最強的是將強連通的組件摺疊成單個超節點，然後檢查得到的圖形是否僅僅是一個「鏈接列表」的圖形 - 覆蓋所有邊緣（這很簡單，只是從起始節點/超節點總是從當前節點講話一個單獨的邊緣，計算出訪問邊緣（以及任何內部邊緣，如果它是超級節點），當你到達一個葉節點時，看看是否所有的邊都被計算在內）。在這個解決方案中，重要的是保留所有原始邊緣，即使它們變得冗餘（例如，如果在將連接的組件A，B，C摺疊成超級節點S之後，從F到A，F到B，F到C的邊緣必須即使它們在簡化圖中指向相同的超級節點S也都被保留）。很抱歉，如果表達不正確，我會在等待答案時嘗試實施此解決方案。

有沒有更簡單的方法？或者一些更好的算法來處理循環/連接組件？因爲當圖形是非循環的時候，它似乎很容易解決。

Answer 1

如果圖形是強連通的，那麼您可以從每個其他節點到達每個節點。由於您可以在此路徑中重新使用邊，因此您必須使用每條邊。採取一些優勢，e。 e通向節點v，您可以從該節點隨後到達每個其他頂點，因此可以到達每個其他邊緣。從這些，你可以回到v。根據需要重複。

因此回答這個問題是否有一些保證這種路徑存在的圖的屬性...如果圖是強連通的，我會說是。 （注意，對於這樣的路徑，這不是必需的 - 例如，在沒有分支的單個單向路徑的情況下）。但這似乎是唯一的邊緣情況（我能想到）。

強連通性的測試可以通過蠻力檢查全部方法來完成。我相信你也可以調整max-flow，min-cut算法。