2017年計算機等級考試四級離散數(shù)學(xué)——歐拉圖復(fù)習(xí)

定義1： 經(jīng)過圖中每條邊一次且僅一次并且行遍圖中每個頂點的通路，稱為歐拉通路或歐拉跡。存在歐拉回路的圖稱為歐拉圖。
    定理1： 無向圖G具有歐拉通路，當(dāng)且僅當(dāng)G是連通圖且有零個或兩個奇度頂點。若無奇度頂點，則通路為回路；若有兩個奇度頂點，則他們是每條歐拉通路的端點。
    推論 無向圖G為歐拉圖（具有歐拉回路）當(dāng)且僅當(dāng)G是連通圖，且G中無季度頂點。
    定理2： 一個有向圖D具有歐拉通路，當(dāng)且僅當(dāng)D是連通的，且除了兩個頂點外，其余頂點的入度均等于出度。這兩個特殊的頂點中，一個頂點的入度比出度大1，另一個頂點的入度比出度小1。