哈密頓圖
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一定不是哈密頓圖(非哈密頓圖的充分條件). |
|
|