http://www.csie.ntnu.edu.tw/~u91029/Circuit.html

Circuit

經過圖上各處的一條環狀路線。在圖論中，Circuit常與Cycle這個字混用，不過Circuit比較強調「經過圖上各處」這件事情。

下面是要介紹的內容：

一、以邊為主：

Euler Circuit：經過圖上所有邊剛好一次的環。

Euler Trail：經過圖上所有邊剛好一次的路徑。

Chinese Postman Problem：經過圖上所有邊「至少一次」的環，經過的邊盡量少。

                         當邊有權重時，則經過的邊的總權重盡量少。

Edge-disjoint Path Cover：覆蓋圖上所有邊的一群路徑，路徑不重疊但可以相交。

                          請見本站文件「Cover」。

二、以點為主：

Hamilton Circuit：經過圖上所有點剛好一次的環。

Hamilton Path：經過圖上所有點剛好一次的路徑。

Travelling Salesman Problem：經過圖上所有點剛好一次的環，「邊有權重」。

Knight's Tour：移動騎士經過西洋棋盤上所有格子剛好一次的環。

Vertex-disjoint Path Cover：覆蓋圖上所有點的一群路徑，路徑不重疊也沒必要相交。

                            請見本站文件「Cover」。

...

Hamilton Circuit（Hamilton Cycle）
註：Hamilton可改為Hamiltonian

Hamilton Circuit是指圖上所有點恰好都經過一次的一條連續路線，這條路線的起點和終點要相同。

一張圖可能有許多種Hamilton Circuit。

Hamilton Path
註：Hamilton可改為Hamiltonian

圖上所有點都恰好經過一次的一條路徑。

Hamilton Circuit去掉一條邊，就形成了Hamilton Path。連接Hamilton Path的起點和終點，補上一條邊，就形成了Hamilton Circuit。

Hamilton Circuit本身也是Hamilton Path，是起點和終點相同的Hamilton Path，而且可以在任何一點當起點。

演算法

暫且用backtracking試試看吧，依序枚舉路徑上的各個點，時間複雜度為O(V!)。

Hamilton Circuit</span>"><br /> <br /> int V = 10;<pre> </pre><pre> </pre><pre> </pre>// 點的總數，一共十個。<br /> bool adj[10][10];<pre> </pre>// adjacency matrix<br /> bool visit[10];<pre> </pre><pre> </pre>// 紀錄已經經過的點<br /> <br /> bool backtrack(int n)<br /> {<br /> <pre> </pre>if (n == V)<br /> <pre> </pre>{<br /> <pre> </pre><pre> </pre>int x = solution[V-1], y = solution[0];<br /> <pre> </pre><pre> </pre>if (adj[x][y])<br /> <pre> </pre><pre> </pre>{<br /> <pre> </pre><pre> </pre><pre> </pre>// 找到一組解<br /> <pre> </pre><pre> </pre>}<br /> <pre> </pre><pre> </pre>return;<br /> <pre> </pre>}<br /> <br /> <pre> </pre>int x = solution[n-1];<br /> <pre> </pre>for (int y=0; y<N; ++y)<br /> <pre> </pre><pre> </pre>if (adj[x][y] && !visit[y])<br /> <pre> </pre><pre> </pre>{<br /> <pre> </pre><pre> </pre><pre> </pre>visit[y] = true;<br /> <pre> </pre><pre> </pre><pre> </pre>solution[n] = y;<br /> <pre> </pre><pre> </pre><pre> </pre>backtrack(n+1);<br /> <pre> </pre><pre> </pre><pre> </pre>visit[y] = false;<br /> <pre> </pre><pre> </pre>}<br /> }<br /> <br /> void HamiltonCircuit()<br /> {<br /> <pre> </pre>visit[0] = true;<pre> </pre>// <span class="fgY1">Hamilton Circuit</span>從哪一點開始都行，<br /> <pre> </pre>solution[0] = 0;<pre> </pre>// 所以直接第一個點設定為第0點，<br /> <pre> </pre>backtrack(1);<pre> </pre><pre> </pre>// 然後從下一個點開始backtrack。<br /> }<br /> <br />

演算法

一、隨機走出一條路徑，盡量長：

　　如果是路徑，則從步驟二開始；如果恰好形成環，則從步驟三開始。

　　輪流進行步驟二與步驟三，直到形成Hamilton Circuit為止。

　　如果無法操作表示此無向圖無Hamilton Circuit。



二、路徑變環：

　　路徑(p1, p2, ..., pk)。

　　路徑上找到一條邊(pi, pi+1)，同時原圖又有邊(pi, pk)與邊(pi+1, p1)，

　　去掉邊(pi, pi+1)、接上邊(pi, pk)與邊(pi+1, p1)，

　　形成環(p1, p2, ..., pi, pk, pk-1, ..., pi+1, p1)。



三、環變路徑：

　　環(p1, p2, ..., pk, p1)。

　　環上找到一點pi，同時原圖又有邊(pi, q)連到環外一點q，

　　就去掉邊(pi, pi+1)、接上邊(pi, q)，

　　形成路徑(q, pi, pi-1, ..., p2, p1, pk, pk-1, ..., pi+1)。

　　或者去掉邊(pi, pi-1)、接上邊(pi, q)，

　　形成路徑(q, pi, pi+1, ..., pk-1, pk, p1, p2, ..., pi-1)。

UVa 775