[理工] 離散6-46
想請問上圖這題計算相異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://www.ptt.cc/bbs/Grad-ProbAsk/M.1597158392.A.7F5.html
推
08/13 03:44,
4年前
, 1F
08/13 03:44, 1F
推
08/23 23:33,
4年前
, 2F
08/23 23:33, 2F