1  2  3  4  5  6  7  8  9  10  11  12   Contents

Fleury's Algorithm

        有了尤拉的定理之後，我們很容易判斷一個圖是否存在一個尤拉迴圈。然而，如果給定的圖相當的複雜，我們如何有系統地找到尤拉迴圈呢？

        對於點數相當大的圖，下面的演算法可以讓我們利用電腦來幫忙找出尤拉廻圈。

Fleury's Algorithm

任給一連通圖G，圖中每個點均有偶數秩。

1. 令 ，任選中G的一點 ，定義 。

2. 假設路徑已經找到，從找一條邊不在上，而且除非別無選擇不為中的橋。
   （其中為中所有的邊）
   令的另一端點為，定義 用 取代 。

3. 若 等於G的邊數，則停止（此時即為所求之尤拉廻圈）；否則回到步驟2。

．我們稱某邊為一連通圖中的橋（bridge），
    如果將此邊從圖中去掉則新圖不再是連通圖。

    例如：下圖中的紅邊即為橋

        上述演算法簡單的說就是要避開橋，除非該邊是剩下的唯一邊。由於一開始的圖中每一個點都有偶數秩，所以如果沒有走過全部的邊表示途中在有選擇的情況下選擇了橋，那是演算法所避免的情形；因此不會剩下邊沒走過。

以下圖為例：

        若我們從I點開始，去掉{I , B}邊，接着去掉{B , D}邊，

注意此時{C, D}邊為橋，因此我們不能再去掉{C, D}邊，我們去掉{D, E}邊，接着我們去掉{E, F}邊、此時{F, G}邊為橋，但我們別無選擇，只能去掉此邊。

接下來自然地我們依序去掉{G, E}邊、{E, H}邊、{H, D}邊、{D, C}邊，

此時{C, I}邊為橋不能去掉，所以我們先掉{C, A}邊，再依序去掉{A, B}邊、{B, C}邊、{C, I}邊。如果把去掉的邊依先後順序加以排列，賦予數字1, 2, …，我們則得一尤拉迴圈如下：