離散數(shù)學-哈密頓圖復習

定義1： 經(jīng)過圖中每個頂點一次且僅一次的通路稱為哈密頓通路。存在哈密頓回路的圖稱為哈密頓圖。

定理1： 設無向圖G=是哈密頓圖，V1是V的任意的非空子集，
則
p(G-V1)<=|V1|
其中，p(G-V1)為從G中刪除V1(刪除V1中各頂點及關聯(lián)的邊)后所得到的圖的連通分支。

定理2： 設G是n(n>=3)階無向簡單圖，如果G中任何一對不相鄰的.頂點度數(shù)之和都大于等于n,則G是哈密頓圖。

推論： 設G是n(n>=3)階無向簡單圖，如果G中任何一對不相鄰的頂點的度數(shù)之和都大于等于n，則G是哈密頓圖。

定理3： 在n(n>=2)階有向圖D=中，如果所有有向邊均用無向邊代替，所得無向圖中含生成子圖Kn，則有向圖中存在哈密頓圖。

推論： n(n>=3)階有向完全圖為哈密頓圖。http://fnhaliao.com/

【離散數(shù)學-哈密頓圖復習】相關文章：

離散數(shù)學-歐拉圖復習10-09

離散數(shù)學-二部圖復習10-09

離散數(shù)學-圖論基礎復習10-09

離散數(shù)學趣味題目10-09

探尋刑法司考規(guī)律，預測來年復習重點(圖)10-13

離散數(shù)學分層次實驗教學設計應用論文03-26

條形圖與扇形圖教學設計02-24

另有所圖成語01-16

唯利是圖成語01-20