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/cn.aspx?n=bbs/Grad-ProbAsk/M.1597158392.A.7F5.html