歐拉回路的定義是什麼
來源:生活大全幫 2.09W
若圖G中存在這樣一條路徑,使得它恰通過G中每條邊一次,則稱該路徑為歐拉路徑。若該路徑是一個圈,則稱為歐拉迴路。
具有歐拉回路的圖稱為歐拉圖。具有歐拉路徑但不具有歐拉回路的圖稱為半歐拉圖。
無向圖存在歐拉回路的充要條件:
一個無向圖存在歐拉回路,當且僅當該圖所有頂點度數都為偶數,且該圖是連通圖。
有向圖存在歐拉回路的充要條件:
一個有向圖存在歐拉回路,所有頂點的入度等於出度且該圖是連通圖。
若圖G中存在這樣一條路徑,使得它恰通過G中每條邊一次,則稱該路徑為歐拉路徑。若該路徑是一個圈,則稱為歐拉迴路。
具有歐拉回路的圖稱為歐拉圖。具有歐拉路徑但不具有歐拉回路的圖稱為半歐拉圖。
無向圖存在歐拉回路的充要條件:
一個無向圖存在歐拉回路,當且僅當該圖所有頂點度數都為偶數,且該圖是連通圖。
有向圖存在歐拉回路的充要條件:
一個有向圖存在歐拉回路,所有頂點的入度等於出度且該圖是連通圖。