離散題庫6-46 (89 成大工科) 相異Euler circuits個數

[蔡忠緯]

想請問上圖這題計算相異Euler circuits個數的解答 (2n)!/2 是否正確?

如果依照解答的算法，K2,4應該有 4!/2 = 12 條相異Euler circuits，我實際列出來之後發現其中會同時包含(a, 1, b, 3, a, 2, b, 4)和(a, 2, b, 4, a, 1, b, 3)這種順序相同但起點不同的迴路，我自己的理解這兩條應該是同一條迴路。

接著我嘗試了以下的算法：

(1) 先計算所有的Euler circuits共 4*(2n)!

(a, v1, b, v2, a, ..., b, v2n)

(b, v1, a, v2, b, ..., a, v2n)

(v1, a, v2, b, v3, ..., v2n, b)

(v1, b, v2, a, v3, ..., v2n, a)

(2) 每條迴路有n個a / n個b / 其他2n個點，共經過4n個點，去掉順序相同僅起點不同的迴路後剩下 4*(2n)!/4n = 2*(2n-1)!

(3) 最後無向迴路順逆方向視為相同，得到相異Euler circuits應為 2*(2n-1)!/2 = (2n-1)!

但是我實際用這個方式去列K2,4的相異Euler circuits卻找到9條而不是3!的6條，不太確定哪裡觀念有錯，網路上也大多討論相異Hamiltonian cycles的計算。

希望助教或好心同學能解說下這題，謝謝！