離散數(shù)學(xué)-哈密頓圖復(fù)習(xí)
定義1: 經(jīng)過圖中每個(gè)頂點(diǎn)一次且僅一次的通路稱為哈密頓通路。存在哈密頓回路的圖稱為哈密頓圖。定理1: 設(shè)無向圖G=
則
p(G-V1)<=|V1|
其中,p(G-V1)為從G中刪除V1(刪除V1中各頂點(diǎn)及關(guān)聯(lián)的邊)后所得到的圖的連通分支。
定理2: 設(shè)G是n(n>=3)階無向簡(jiǎn)單圖,如果G中任何一對(duì)不相鄰的.頂點(diǎn)度數(shù)之和都大于等于n,則G是哈密頓圖。
推論: 設(shè)G是n(n>=3)階無向簡(jiǎn)單圖,如果G中任何一對(duì)不相鄰的頂點(diǎn)的度數(shù)之和都大于等于n,則G是哈密頓圖。
定理3: 在n(n>=2)階有向圖D=
推論: n(n>=3)階有向完全圖為哈密頓圖。http://www.dgxbdz.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ù)測(cè)來年復(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