圖論 - 可遍歷性
如果可以繪製一條經過所有頂點而不重複相同路徑的路徑，則該圖是可遍歷的。基於此路徑，本章描述了尤拉路徑和歐拉回路等一些類別。
尤拉路徑
尤拉路徑包含圖 'G' 的每條邊恰好一次，並且包含圖 'G' 的每個頂點至少一次。如果連通圖 G 包含尤拉路徑，則稱其為可遍歷的。
例子
尤拉路徑 = d-c-a-b-d-e。
歐拉回路
在尤拉路徑中，如果起始頂點與其結束頂點相同，則稱為歐拉回路。
例子
尤拉路徑 = a-b-c-d-a-g-f-e-c-a。
歐拉回路定理
連通圖 'G' 可遍歷當且僅當 G 中具有奇數度的頂點數恰好為 2 或 0。如果連通圖 G 恰好有兩個奇數度頂點，則它可以包含尤拉路徑，但不能包含歐拉回路。
注意 − 此尤拉路徑以一個奇數度頂點開始，以另一個奇數度頂點結束。
例子
尤拉路徑 − b-e-a-b-d-c-a 不是歐拉回路，但它是尤拉路徑。顯然它恰好有兩個奇數度頂點。
注意 − 在連通圖 G 中，如果奇數度頂點數 = 0，則存在歐拉回路。
哈密頓圖
如果存在一個包含圖 G 所有頂點的迴路，則稱連通圖 G 為哈密頓圖。
每個迴路都是一個環路，但環路可能包含多個迴路。這樣的迴路稱為圖 G 的哈密頓迴路。
哈密頓路徑
如果連通圖包含圖 G 的每個頂點恰好一次，則稱其為哈密頓圖。這樣的路徑稱為哈密頓路徑。
例子
哈密頓路徑 − e-d-b-a-c。
注意
歐拉回路包含圖的每條邊恰好一次。
在哈密頓迴路中，可以跳過圖的一些邊。
例子
請看下面的圖：
對於上面顯示的圖：
存在尤拉路徑 – 錯誤
存在歐拉回路 – 錯誤
存在哈密頓迴路 – 正確
存在哈密頓路徑 – 正確
G 有四個奇數度頂點，因此它不可遍歷。透過跳過內部邊，該圖具有經過所有頂點的哈密頓迴路。
廣告