歐拉道路與歐拉回路

歐拉道路與歐拉回路

歐拉道路：通過圖G中每條邊一次且僅一次的道路稱作該圖的歐拉道路。

歐拉回路：通過圖G中每條邊一次且僅一次的回路稱作該圖的歐拉回路。

歐拉圖：存在歐拉回路的圖稱為歐拉圖。

歐拉在1736年給出了歐拉道路/回路存在的必要條件，在1873年希爾霍爾策首次給出了刻畫歐拉圖的充要條件。

定理

(a)無向圖G是歐拉圖（存在歐拉回路）當且僅當G是連通的且所有頂點都是偶數度

(b)無向圖G存在歐拉道路當且僅當G是連通的且奇數度頂點不超過2個

下面證明(a):

1、(必要性)如果是歐拉圖，從一個起點出發，經過每個頂點必定是一進一出，再回到起點，這樣所有的點都是偶數度

2、(充分性)從任一點出發，構造G的一條簡單回路C(想想為什麼一定可以)，如果C已經包含所有邊，那G就是歐拉圖；

若C不是G的回路，則從G中删去C的各邊和孤立頂點（如果存在），得到G1，顯然G1中個頂點的度還是偶數。原圖是連通的，G1和C必然存在公共頂點u。從u出發，在G1中得到回路C1。将C和C1連接配接起來得到包含邊數比原來更多的G的一條簡單回路。由于邊是有限的，這個過程一定會結束。最後得到包含所有邊的回路，就是歐拉回路。

下面證明(b):

在(a)的基礎上簡單證明

首先，易知，奇數度頂點不超過隻能是0個或2個（握手定理保證不可能存在奇數個奇頂點）。奇數度頂點為0就是情況(a)

若有兩個奇數度頂點，我們認為地在之間添加一條虛拟的邊，這個每個頂點都是偶數度了，是以就存在歐拉回路。而這個歐拉回路一定包含我們虛拟的邊，把虛拟的邊删去，就得到包含圖中所有邊的歐拉道路。必要性證明略。

推廣到有向圖

有向圖存在歐拉道路的兩個條件：

1、最多隻能有兩個點的入度不等于出度，而且必須是其中一個點的出度且比入度大1（把它作為起點），另一個的入度比出度大1（把它作為終點）。

2、在忽略邊的方向後，圖必須是連通的。

參考連結：中國大學mooc 離散數學 劉铎

個性簽名：時間會解決一切