奧爾定理(離散數學中圖論的一個定理)

如果一個總點數至少為3的簡單圖G滿足：G的任意兩個點u和v度數之和至少為n，即deg(u)+deg(v)≥n，那么G必然有哈密頓迴路。

它描述了簡單圖擁有哈密頓迴路的一個充分條件。

基本介紹

• 中文名：奧爾定理
• 外文名：ORE's Theorem
• 表達式：deg(u)+deg(v)≥n → G有哈密頓通路
• 提出者：奧斯丁·歐爾
• 套用學科：離散數學
• 適用領域範圍：圖論

如果一個總點數至少為3的簡單圖G滿足：G的任意兩個點u和v度數之和至少為n，即deg(u)+deg(v)≥n，那么G必然有哈密頓迴路。

相關概念：

簡單圖：沒有重邊和環的無向圖。

度數：某點所連線的邊的數目。

哈密頓迴路：經過圖的所有的點的一條迴路。