離散數(shù)學(xué)-哈密頓圖復(fù)習(xí)

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

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

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

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

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

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

【離散數(shù)學(xué)-哈密頓圖復(fù)習(xí)】相關(guān)文章：

離散數(shù)學(xué)-歐拉圖復(fù)習(xí)10-09

離散數(shù)學(xué)-二部圖復(fù)習(xí)10-09

離散數(shù)學(xué)-圖論基礎(chǔ)復(fù)習(xí)10-09

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

探尋刑法司考規(guī)律，預(yù)測來年復(fù)習(xí)重點(diǎn)(圖)10-13

離散數(shù)學(xué)分層次實(shí)驗(yàn)教學(xué)設(shè)計(jì)應(yīng)用論文03-26

條形圖與扇形圖教學(xué)設(shè)計(jì)02-24

另有所圖成語01-16

唯利是圖成語01-20