若圖G中存在這樣一條路徑,使得它恰通過G中每條邊一次,則稱該路徑為歐拉路徑。若該路徑是一個圈,則稱為歐拉回路。
具有歐拉回路的圖稱為歐拉圖。具有歐拉路徑但不具有歐拉回路的圖稱為半歐拉圖。
無向圖存在歐拉回路的充要條件:
一個無向圖存在歐拉回路,當且僅當該圖所有頂點度數都為偶數,且該圖是連通圖。
有向圖存在歐拉回路的充要條件:
一個有向圖存在歐拉回路,所有頂點的入度等于出度且該圖是連通圖。
更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!