我需要將無向圖拆分為最少數量的子路徑（可以重復頂點，但不能重復邊）。有什么演算法嗎？如何實施？
例如，對于下面給定的圖表，它可能是：
BACI、CDEGFC 或 BACDEGFC、CI
uj5u.com熱心網友回復：
假設您的圖是連接的并且有 k 個奇數度的頂點。那么答案是 k/2 和 1 的最大值。如果您的圖表未連接，那么每個連接組件也是如此。
讓我們首先考慮沒有奇數度頂點的情況。從任何頂點開始，并繼續前進到任意鄰居（沿著未使用的邊），直到回到起始頂點。你知道你可以留下你能到達的任何頂點，因為它們都有相同的度數。
如果這用完所有邊緣，那么你就完成了。如果沒有，請選擇與未使用的邊相鄰的頂點并重復。繼續這樣做。完成后，您將有多個回圈，例如 r，并且每個回圈將與另一個回圈共享至少一個頂點。接下來，以自然的方式合并相鄰的回圈。例如，在一個非常簡單的情況下，我們有兩個共享一個頂點的三角形：abc 和 cde，我們用這兩個小回圈完成我們的程序：abca 和 cdec。我們在相遇的地方合并這些：abcdeca
a---b
\ /
c
/ \
d---e
現在，奇數度頂點的問題是，任何軌跡都將使用與其中每個頂點相鄰的 2 條邊，除了開始和結束（如果不同）它只使用 1。這意味著如果有奇數頂點，將為每一對相同的單獨的蹤跡。您可以應用與以前相同的程序，但始終從奇數度頂點開始。您將被迫在奇數度頂點處結束。盡可能合并，但你總是會得到每對奇數頂點一個軌跡。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/532364.html
標籤：算法图论无向图