1. 首頁 > 生活經驗 > >

歐拉回路的定義是什么

生活百科回路


歐拉回路的定義是什么

文章插圖
若圖G中存在這樣一條路徑，使得它恰通過G中每條邊一次，則稱該路徑為歐拉路徑 。若該路徑是一個圈，則稱為歐拉回路 。
具有歐拉回路的圖稱為歐拉圖 。具有歐拉路徑但不具有歐拉回路的圖稱為半歐拉圖 。
無向圖存在歐拉回路的充要條件：
一個無向圖存在歐拉回路 ， 當且僅當該圖所有頂點度數都為偶數,且該圖是連通圖 。
有向圖存在歐拉回路的充要條件：
【歐拉回路的定義是什么】一個有向圖存在歐拉回路，所有頂點的入度等于出度且該圖是連通圖 。