哈密頓圖
h哈密頓通路(回路)與哈密頓圖 通過圖G的每個結點一次，且僅一次的通路(回路)，就是哈密頓通路(回路). 存在哈密頓回路的圖就是哈密頓圖.
判斷哈密頓圖是較為睏難的.
h哈密頓圖的充分條件和必要條件
(1) 在無嚮簡單圖G=<V,E>中½V½³3,任意不同結點 ,則G是哈密頓圖.(充分條件，定理4)
(2) 有嚮完全圖D＝<V,E>, 若 ，則圖D是哈密頓圖. (充分條件，定理5推論)
(3) 設無嚮圖G=<V,E>,"V1ÌV，則P(G－V1)£½V1½(必要條件，定理3)
若此條件不滿足，即$V1ÌV，使得P(G－V!)>½V1½,則G一定不是哈密頓圖(非哈密頓圖的充分條件). |
|
|