哈密爾頓顯示週期使用Mathematica

Question

我嘗試使用Mathematica的找漢密爾頓週期在下面的圖：

g = Graph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 6, 
    2 \[UndirectedEdge] 4, 1 \[UndirectedEdge] 3, 
    3 \[UndirectedEdge] 4, 4 \[UndirectedEdge] 5, 
    5 \[UndirectedEdge] 6, 3 \[UndirectedEdge] 9, 
    4 \[UndirectedEdge] 7, 7 \[UndirectedEdge] 8, 
    8 \[UndirectedEdge] 11, 5 \[UndirectedEdge] 8, 
    5 \[UndirectedEdge] 12, 6 \[UndirectedEdge] 12, 
    9 \[UndirectedEdge] 10, 10 \[UndirectedEdge] 11, 
    11 \[UndirectedEdge] 12, 9 \[UndirectedEdge] 15, 
    15 \[UndirectedEdge] 16, 16 \[UndirectedEdge] 17, 
    16 \[UndirectedEdge] 19, 19 \[UndirectedEdge] 20, 
    20 \[UndirectedEdge] 23, 20 \[UndirectedEdge] 17, 
    17 \[UndirectedEdge] 18, 15 \[UndirectedEdge] 21, 
    18 \[UndirectedEdge] 24, 21 \[UndirectedEdge] 22, 
    22 \[UndirectedEdge] 23, 23 \[UndirectedEdge] 24, 
    3 \[UndirectedEdge] 15, 14 \[UndirectedEdge] 15, 
    14 \[UndirectedEdge] 12, 22 \[UndirectedEdge] 15, 
    12 \[UndirectedEdge] 18, 11 \[UndirectedEdge] 13, 
    13 \[UndirectedEdge] 14, 13 \[UndirectedEdge] 10, 
    1 \[UndirectedEdge] 10, 12 \[UndirectedEdge] 24}, 
    VertexLabels -> "Name"] 

然後

EdgeList[g, 4 \[UndirectedEdge] _] 

可見，4與2,3,5連接， 7

但代碼

First[FindHamiltonianCycle[g]] 

收益不對勁，即

{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 4, 4 \[UndirectedEdge] 8, 
8 \[UndirectedEdge] 9, 9 \[UndirectedEdge] 6, 6 \[UndirectedEdge] 3, 
3 \[UndirectedEdge] 11, 11 \[UndirectedEdge] 21, 
21 \[UndirectedEdge] 19, 19 \[UndirectedEdge] 15, 
15 \[UndirectedEdge] 14, 14 \[UndirectedEdge] 16, 
16 \[UndirectedEdge] 17, 17 \[UndirectedEdge] 18, 
18 \[UndirectedEdge] 22, 22 \[UndirectedEdge] 20, 
20 \[UndirectedEdge] 13, 13 \[UndirectedEdge] 23, 
23 \[UndirectedEdge] 24, 24 \[UndirectedEdge] 10, 
10 \[UndirectedEdge] 12, 12 \[UndirectedEdge] 7, 
7 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 1} 

爲什麼數學採取從4邊緣8，因爲它不存在嗎？算法中有錯誤還是我做錯了？

我正在使用Mathematica 8。

Answer 1

我在Windows 7上使用8.0.4，我不明白這一點。它看起來像一個bug那麼固定在8.0.4

g = Graph[{UndirectedEdge[1, 2], UndirectedEdge[1, 6], UndirectedEdge[2, 4], 
UndirectedEdge[1, 3], UndirectedEdge[3, 4], UndirectedEdge[4, 5], 
UndirectedEdge[5, 6], UndirectedEdge[3, 9], UndirectedEdge[4, 7], 
UndirectedEdge[7, 8], UndirectedEdge[8, 11], UndirectedEdge[5, 8], 
UndirectedEdge[5, 12], UndirectedEdge[6, 12], UndirectedEdge[9, 10], 
UndirectedEdge[10, 11], UndirectedEdge[11, 12], UndirectedEdge[9, 15], 
UndirectedEdge[15, 16], UndirectedEdge[16, 17], UndirectedEdge[16, 19], 
UndirectedEdge[19, 20], UndirectedEdge[20, 23], UndirectedEdge[20, 17], 
UndirectedEdge[17, 18], UndirectedEdge[15, 21], UndirectedEdge[18, 24], 
UndirectedEdge[21, 22], UndirectedEdge[22, 23], UndirectedEdge[23, 24], 
UndirectedEdge[3, 15], UndirectedEdge[14, 15], UndirectedEdge[14, 12], 
UndirectedEdge[22, 15], UndirectedEdge[12, 18], UndirectedEdge[11, 13], 
UndirectedEdge[13, 14], UndirectedEdge[13, 10], UndirectedEdge[1, 10], 
UndirectedEdge[12, 24]}, VertexLabels -> "Name"]; 

r = First[FindHamiltonianCycle[g]] 

給

{UndirectedEdge[1, 2], UndirectedEdge[2, 4], UndirectedEdge[4, 7], 
    UndirectedEdge[7, 8], UndirectedEdge[8, 5], UndirectedEdge[5, 6], 
    UndirectedEdge[6, 12], UndirectedEdge[12, 24], UndirectedEdge[24, 18], 
    UndirectedEdge[18, 17], UndirectedEdge[17, 16], UndirectedEdge[16, 19], 
    UndirectedEdge[19, 20], UndirectedEdge[20, 23], UndirectedEdge[23, 22], 
    UndirectedEdge[22, 21], UndirectedEdge[21, 15], UndirectedEdge[15, 14], 
    UndirectedEdge[14, 13], UndirectedEdge[13, 11], UndirectedEdge[11, 10], 
    UndirectedEdge[10, 9], UndirectedEdge[9, 3], UndirectedEdge[3, 1]} 

你可以看到邊緣4<->8是不存在的。驗證

In[7]:= Cases[r, UndirectedEdge[4, 8]] 
Out[7]= {}