定義：
歐拉回路：每條邊恰好只走一次，并能回到出發(fā)點的路徑
歐拉路徑：經(jīng)過每一條邊一次，但是不要求回到起始點
①首先看歐拉回路存在性的判定：
一、無向圖
每個頂點的度數(shù)都是偶數(shù)，則存在歐拉回路。
二、有向圖（所有邊都是單向的）
每個節(jié)頂點的入度都等于出度，則存在歐拉回路。
三.混合圖歐拉回路
混合圖歐拉回路用的是網(wǎng)絡流。
把該圖的無向邊隨便定向，計算每個點的入度和出度。如果有某個點出入度之差為奇數(shù)，那么肯定不存在歐拉回路。因為歐拉回路要求每點入度 = 出度，也就是總度數(shù)為偶數(shù)，存在奇數(shù)度點必不能有歐拉回路。
好了，現(xiàn)在每個點入度和出度之差均為偶數(shù)。那么將這個偶數(shù)除以2，得x。也就是說，對于每一個點，只要將x條邊改變方向（入>出就是變?nèi)耄?gt;入就是變出），就能保證出 = 入。如果每個點都是出 = 入，那么很明顯，該圖就存在歐拉回路。
現(xiàn)在的問題就變成了：我該改變哪些邊，可以讓每個點出 = 入？構(gòu)造網(wǎng)絡流模型。首先，有向邊是不能改變方向的，要之無用，刪。一開始不是把無向邊定向了嗎？定的是什么向，就把網(wǎng)絡構(gòu)建成什么樣，邊長容量上限1。另新建s和t。對于入 > 出的點u，連接邊(u, t)、容量為x，對于出 > 入的點v，連接邊(s, v)，容量為x（注意對不同的點x不同）。之后，察看是否有滿流的分配。有就是能有歐拉回路，沒有就是沒有。歐拉回路是哪個？查看流值分配，將所有流量非 0（上限是1，流值不是0就是1）的邊反向，就能得到每點入度 = 出度的歐拉圖。
由于是滿流，所以每個入 > 出的點，都有x條邊進來，將這些進來的邊反向，OK，入 = 出了。對于出 > 入的點亦然。那么，沒和s、t連接的點怎么辦？和s連接的條件是出 > 入，和t連接的條件是入 > 出，那么這個既沒和s也沒和t連接的點，自然早在開始就已經(jīng)滿足入 = 出了。那么在網(wǎng)絡流過程中，這些點屬于“中間點”。我們知道中間點流量不允許有累積的，這樣，進去多少就出來多少，反向之后，自然仍保持平衡。
所以，就這樣，混合圖歐拉回路問題，解了。
②.歐拉路徑存在性的判定
一。無向圖
一個無向圖存在歐拉路徑，當且僅當 該圖所有頂點的度數(shù)為偶數(shù) 或者 除了兩個度數(shù)為奇數(shù)外其余的全是偶數(shù)。
二。有向圖
一個有向圖存在歐拉路徑，當且僅當 該圖所有頂點的度數(shù)為零 或者 一個頂點的度數(shù)為1，另一個度數(shù)為-1，其他頂點的度數(shù)為0。
三。混合圖歐拉路徑
其實整篇文章只有這部分是我寫的哈，灰常不好意思，只是網(wǎng)上的同志們寫的太好了，實在沒有必要重復勞動，不知道大家有沒有發(fā)現(xiàn)，求歐拉路徑的第一步一定是求歐拉回路，在混合圖上也不例外，如何判斷混合圖歐拉回路問題的存在性呢？首先，我們用上文所說的方法判斷該圖是否存在歐拉回路，如果存在，歐拉路徑一定存在。如果歐拉回路不存在，那么我們枚舉歐拉路徑的起點和終點，連接一條無向邊，然后再用最大流判斷是否存在歐拉回路即可。
OJ上的幾道題 ：POJ 1386 HDOJ 3472