https://imgur.com/SQvV84z 想請問上圖這題計算相異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的計算。 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.77.135.239 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1597158392.A.7F5.html