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為止。

　　如果無法操作表示此無向圖無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