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