歐拉鏈

簡介

若P為連通無向圖G的一條鏈，G的每一條邊在P中恰出現一次，則稱P為歐拉鏈。

若無向圖G含有一條閉的歐拉鏈，則稱圖G為歐拉圖。顯然，一個圖G若能一筆畫出，這個圖必然是歐拉圖或含有歐拉鏈。

①若且唯若連通圖G的全部頂點都是偶次頂點時，圖G才是歐拉圖。

②當連通圖G恰有兩個奇次頂點時G才有歐拉鏈。

如圖8-27(a)就是一個歐拉圖，圖8-27(b)就不是歐拉圖，但有歐拉鏈{V_s,V₁,V_s,V₂,V_s,V₃,V₁}。

在圖8—28(a)中，因所有頂點均為偶次，故是歐拉圖。在圖8—29(b)中，恰有兩個奇次頂點，故有歐拉鏈。