第8章 Euler路徑與迴路
8.1 每條邊恰一次，頂點可以重訪
trail（跡）是每步有邊且沒有重複用邊的 walk；可以多次走到同一頂點。Euler 跡用完圖的每條邊恰一次，若起終點相同稱 Euler 迴路。本章的「Euler 路徑」指這種跡，不要求頂點互異；它也不是走遍每個頂點恰一次的問題。
一條 Euler 跡經過中途頂點時，每次進、出配成一對。若起終點不同，兩端各多一次未配對，故正好兩個奇度頂點；若封閉，全部為偶度。所有有邊的頂點還必須在同一分量，因一路走不過互不相連的邊塊。孤立點不影響。頂點非空而無邊時，可停在任一頂點，視為長度零的迴路；空頂點圖不在此約定內。
若圖至少有一條邊、有邊部分連通且全偶度，從任一有邊頂點沿未用邊走到不能再走。若停在非起點，該點用過的邊數為奇數，原度數為偶數，所以仍有未用邊，矛盾。故先得封閉跡。若仍有未用邊，從封閉跡上一點走到某條未用邊的端點，再接上該邊。這段 walk 的第一條未用邊，其出發點已在封閉跡上。扣掉原跡後，各點剩餘度數仍為偶數，於此走出另一封閉跡並插回。每次至少多用一邊，有限次後用完。
若正好兩個奇度點且有邊部分連通，暫加一條連接兩點的專用邊，使所有度數為偶數。即使已有同端點的邊，也把專用邊視為不同一條。前面的度數配對與插接按邊身分進行，仍適用。把所得封閉跡旋轉到以專用邊為第一步，刪去這一步，餘下即為原圖的 Euler 跡。
8.2 四個例題
例題1 用插接把兩圈接起來
邊為 AB、BC、AC、CD、DE、CE。A,B,C,A 是第一圈。當它走到 C 時插入 C,D,E,C，得 A,B,C,D,E,C,A。C 重訪，但六條邊各用一次，所以是 Euler 迴路。
例題2 兩奇點要做兩端
邊為 AB、BC、AC、CD。A、B 度 2，C 度 3，D 度 1。可從 D 走 D,C,A,B,C，恰用四邊。因起終點不同，這是一條 Euler 跡而非迴路。
例題3 全偶還可能走不完
兩個不相連的三角形，每點度數皆 2，但從第一塊不可能跨到第二塊。有邊頂點不在同一分量，所以沒有 Euler 跡或迴路。
例題4 孤立點不改邊走訪
頂點 A、B、C、D，前三點成三角形，D 孤立。A,B,C,A 仍用完全部邊，D 不需要訪問。若四點都孤立，停在 A 即可用完零條邊。
8.3 練習
- B10-C08-Q01 A 到 E，邊 AB、BC、CD、DE。Euler 跡端點？
- B10-C08-Q02 四點星形 AB、AC、AD 有 Euler 跡嗎？
- B10-C08-Q03 三角形 A,B,C,A,B 是 trail 嗎？
- B10-C08-Q04 四環 AB、BC、CD、AD 給一條 Euler 迴路。
- B10-C08-Q05 在上題四環加 AC，應從哪兩點之一出發？
- B10-C08-Q06 有兩塊各只有一條邊 AB、CD，會有 Euler 跡嗎？
- B10-C08-Q07 若 Euler 迴路沿途到達同一頂點兩次，會違反定義嗎？
- B10-C08-Q08 頂點 A、B 但無邊，寫一條 Euler 迴路。
- B10-C08-Q09 若某點度數為 1，能有 Euler 迴路嗎？
- B10-C08-Q10 三角形接 CD 的例題，A,C,D,B 是 Euler 跡嗎？
8.4 完整解答
Q01
A、E 度 1，其餘度 2，有邊部分連通。A,B,C,D,E 恰用完，端點 A、E；不能閉合。
Q02
A 度 3，B、C、D 各 1，有四個奇度點，超出最多兩端，所以沒有。
Q03
不是。第一步與最後一步都是同一條無向邊 AB，雖然每步都有邊，也不符合不重用。
Q04
A,B,C,D,A 順著環走，四條邊依序 AB、BC、CD、DA，最後回到 A。
Q05
新增邊使 A、C 度數從 2 變 3，只有它們是奇點。可走 A,B,C,D,A,C，從 A 到 C，反向也合法。
Q06
沒有。兩個有邊分量無法相互到達；也有四個奇度點。任一理由都足以排除。
Q07
不會。Euler 條件限制的是邊各一次，不限制頂點；例題1在 C 匯合兩圈就是合法的。
Q08
序列 (B) 不走任何邊，起終點都是 B；圖中沒有邊漏掉。
Q09
不能。封閉跡在每個點使用的入與出必成對；該點唯一的邊無法成對，所以不可能用完後閉合。
Q10
不是，D 到 B 需要 DB，但圖沒有這條邊；也沒用完四條。先逐步檢查鄰接，再檢查用邊清單。