《離散數(shù)學(xué)》：學(xué)習(xí)筆記.pdf

《《離散數(shù)學(xué)》：學(xué)習(xí)筆記.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、《離散數(shù)學(xué)》：學(xué)習(xí)筆記我做學(xué)習(xí)筆記的目的是將復(fù)雜的概念及公式壓縮成幾頁(yè)并以圖文并茂的形式表示出來(lái)，如此會(huì)便于去記憶理解，這樣即使在若干年重回該領(lǐng)域研究時(shí)也可以快速掌握知識(shí)點(diǎn)。但光靠這是不行的，有扎實(shí)的基礎(chǔ)知識(shí)還需要反復(fù)的練習(xí)做題，希望同學(xué)能好好努力，爭(zhēng)取拿到一個(gè)很高的分?jǐn)?shù)。第七章圖的基本概念A(yù)a,a,Bb,b則A&a,b,a,b,a,b, a,b無(wú)序積n

2、V

3、VGv,v,…,v,GV,Eev,vdv2m握手定理EGe

4、,e,…,e,頂點(diǎn)集邊m

5、E

6、邊頂點(diǎn)(或結(jié)點(diǎn))端點(diǎn)度數(shù)：V做為邊端點(diǎn)的次數(shù)概念：：：：關(guān)聯(lián)e環(huán)v1、有限圖：即V、E都是有窮集合e2、n階圖：頂點(diǎn)數(shù)為n

7、V

8、ve.3、零圖：邊E#e/ve0v4、平凡圖：E#且

9、V

10、10/e15、多重圖：含平行邊相鄰6、簡(jiǎn)單圖：不含平行邊和環(huán)孤立點(diǎn)v平行邊17、n階無(wú)向完全圖K：所有v與v相鄰dv4dv/1dv4dv018、子圖G&,母圖G：G'(G V&(V且E&(Edv132m246129、真子圖：G'(G V&

11、(V且E&)E0101111)、j列元素之和為210、生成子圖：G'(GV'V?211000C2)、i行元素之和為dvMG>001110B3)、所有元素之和為2m11、導(dǎo)出子圖：與子集V關(guān)聯(lián)的所有邊構(gòu)成的圖>B>000001B4)、孤立點(diǎn)元素都為0與子集E關(guān)聯(lián)的所有頂點(diǎn)構(gòu)成的圖=000000A5)、列jj&列平行邊12、補(bǔ)圖G*：

12、V

13、不變，兩簡(jiǎn)單圖互成完全圖K13、連通圖：任意兩頂點(diǎn)連通ae1414、連通分支p G：根據(jù)連通關(guān)系R劃分出若干個(gè)等價(jià)的b5子集V構(gòu)成的導(dǎo)出子圖d23cG6G

14、同構(gòu)的，對(duì)應(yīng)關(guān)系：a71,b72,c73,d74,e75PG1GPGFV'2PGFE'2(兩兩)連通當(dāng)v;v,回路15、點(diǎn)割集/邊割集：刪掉頂點(diǎn)/邊，使形成非連通圖點(diǎn)割集只為1稱(chēng)割點(diǎn)Γv;eve…e

15、)生成樹(shù)T：無(wú)向連通圖G的生成子圖（且為樹(shù)）樹(shù)枝：T的邊v/v0基本公式：弦：除了樹(shù)枝外的邊tF1余樹(shù)：所有弦集合的導(dǎo)出子圖snFtv.vIrF1基本回路：T+1根弦形成回路。所有回路稱(chēng)系統(tǒng)僅正則樹(shù)能用基本割集：即樹(shù)枝與其對(duì)應(yīng)弦。所有割集稱(chēng)系統(tǒng)dv2m根樹(shù)：1個(gè)頂點(diǎn)入度為0，其余頂點(diǎn)入度為1的樹(shù)mnF1分支點(diǎn)s：dvH2(包括樹(shù)根，內(nèi)點(diǎn))Q樹(shù)根：入度為0的頂點(diǎn)WTωlv求總傳輸位數(shù)內(nèi)點(diǎn)：入度為1，出度>0的頂點(diǎn)(樹(shù))權(quán)層數(shù)(碼長(zhǎng))樹(shù)葉t：入度為1，出度為0的頂點(diǎn)帶權(quán)(概率

16、)層數(shù)l：從樹(shù)根到任意頂點(diǎn)的長(zhǎng)度例：badcedbecbecdeddcee樹(shù)高：最大的層數(shù)根層19路家族樹(shù)：父親、兒子、兄弟、祖先、后代(分枝)權(quán)子孫之和r元樹(shù)：最多有r個(gè)兒子一層811r元正則樹(shù)：每個(gè)爸爸都有r個(gè)兒子WT143R343R442R542R64242r元完全正則樹(shù)：所有樹(shù)葉層數(shù)相同二層4456前綴碼：左樹(shù)枝標(biāo)0，左樹(shù)枝標(biāo)1cde最優(yōu)前綴碼：即最優(yōu)r元樹(shù)的前綴碼三層帶權(quán)(概率)13碼字：前綴碼從樹(shù)頂?shù)綐?shù)葉組成的碼字ab等長(zhǎng)碼：位數(shù)相同的碼字前綴碼：000傳a，001傳b，01傳c，10傳d，11

17、傳eHuffman算法：(二元樹(shù))1、以2個(gè)最小帶權(quán)為樹(shù)葉連成分支，分支權(quán)為和2、分支權(quán)與其它樹(shù)葉之間選最小權(quán)繼續(xù)連成分支3、重復(fù)2，直到分支權(quán)和樹(shù)葉用完