歐拉圖及歐拉路淺談

「總是這樣一波三折 舍近求遠」

歐拉路我們将其稱為是一個圖中從某一節點 \(s\) 出發，恰好經過圖中每條邊各一次，但是可以重複經過圖中節點的路。

歐拉回路就是指就是從某點 \(s\) 出發最後仍回到 \(s\) 的歐拉路。

存在歐拉路的圖被稱為歐拉圖。

存在歐拉路但是不存在歐拉回路的圖叫做半歐拉圖。

一張無向圖為歐拉圖，僅當無向圖連通，并且每個節點的度數為偶數。

證明： 等價于判定是否存在歐拉回路，而每條邊都要經過，然後回到最開始等價于是進行出去與回來的反複操作，是以判定正确。

一張無向圖中存在歐拉路，僅當無向圖連通，并且恰好隻有兩個節點 \(s\) 和 \(t\) 的度數為奇數其他均為偶數。

證明： 等價于是不在回到起點的歐拉回路，聯合上面證明是以顯然。

一張無向圖是半歐拉圖當且僅當這個圖是連通的，并且恰好有 \(2\) 個奇度數節點。

證明: 等價于判斷處在歐拉路。

所有點屬于一個強連通分量且每個頂點的入度和出度相同。

将所有有向邊變成無向邊時，所有點屬于一個強連通分量。

最多隻有一個頂點的出度與入度差為 \(1\) 。

最多隻有一個頂點的入度與出度差為 \(1\) 。

所有其他頂點的入度與出度相同。

求有向圖字典序最小的歐拉路徑。

模闆歐拉回路，按照上面的方法模拟就是了。