《離散數(shù)學(xué)》PPT課件

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

1、離散數(shù)學(xué)DiscreteMathematics9/15/20212:53AM1DiscreteMath.,huangliujia第十六章樹§16.1無向樹及其性質(zhì)§16.2生成樹§16.3根樹及其應(yīng)用9/15/20212:53AM2DiscreteMath.,huangliujia定義16.1無向樹:連通無回路的無向圖平凡樹:平凡圖森林:每個(gè)連通分支都是樹的非連通的無向圖樹葉:樹中度數(shù)為1的頂點(diǎn)分支點(diǎn):樹中度數(shù)?2的頂點(diǎn)16.1無向樹及其性質(zhì)右圖為一棵12階樹.聲明:本章中所討論的回路均指簡(jiǎn)單回路

2、或初級(jí)回路9/15/20213DiscreteMath.,huangliujia無向樹的性質(zhì)定理16.1設(shè)G=是n階m條邊的無向圖，則下列等價(jià)的：（1）G是樹;（2）G中任意兩個(gè)頂點(diǎn)之間存在惟一的路徑;（3）G中無回路且m=n?1;（4）G是連通的且m=n?1;（5）G是連通的且G中任何邊均為橋;（6）G中沒有回路,但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊后所得圖中有惟一的一個(gè)含新邊的圈.證明：①?②由于G是樹，所以G是連通的，?u,v?V，u和v之間存在一條路。若路不惟一，設(shè)L1和L2都是

3、u和v之間的路，則由L1和L2上的邊組成了G中的一個(gè)回路，矛盾。9/15/20214DiscreteMath.,huangliujia②?③先證G中無回路。若G中存在某個(gè)結(jié)點(diǎn)v上的環(huán)，?u?V，由條件知u到v存在一條路L1：u…v，則u到v有另一條路L2：u…vv，矛盾。若G中存在長(zhǎng)度大于等于2的一條回路，則回路上兩個(gè)結(jié)點(diǎn)之間存在不同的路,矛盾。所以G中無回路。以下用歸納法證明m=n–1。當(dāng)n=1時(shí)，G為平凡圖，m=0=1–1=n–1。結(jié)論成立。設(shè)n≤k時(shí)，結(jié)論成立。下證n=k+1時(shí)，結(jié)論也成立。

4、設(shè)e=(u,v)是G中的一條邊，由于G中無回路，所以G-?e?有兩個(gè)連通分支G1和G2，設(shè)它們的結(jié)點(diǎn)數(shù)和邊數(shù)分別為：n1，m1和n2，m2。于是有n1≤k和n2≤k，由歸納假設(shè)知：m1=n1–1和m2=n2-1，m=m1＋m2＋1=n1-1＋n2-1＋1=n-1。9/15/20215DiscreteMath.,huangliujia③?④只須證明G是連通的。若不然,設(shè)G有s(s≥2)個(gè)連通分支G1,G2,…,Gs,Gi中均無回路，都是樹。由①?②?③可知，mi=ni–1，i=1,…,s。于是m=m

5、1＋m2＋…＋ms=n1-1＋n2-1＋…＋ns-1=n1＋n2＋…＋ns-s=n–s，由于s≥2，這與m=n–1矛盾。所以G是連通圖。④?⑤只須證明G的每一條邊均為橋。設(shè)e是G的任意邊，刪除e得子圖G1，它的邊數(shù)m1=m-1，結(jié)點(diǎn)數(shù)n1=n，m1=m–1=n-1-1=n-2=n1-2＜n1-1，由習(xí)題14的第49題知G1不是連通圖，所以e是橋。⑤?⑥由于G中每一條邊均為橋，因而G中無回路。又因?yàn)镚連通，所以G是樹。由①?②知，?u,v?V，u≠v，u與v之間存在一條惟一的路。在u與v之間增加一條

6、新邊,得到G的一條回路,顯然這條回路是惟一的。⑥?①只須證明G是連通的，?u,v?V，u≠v，在u與v之間增加一條新邊(u,v)就產(chǎn)生G的一個(gè)惟一的回路，故結(jié)點(diǎn)u和結(jié)點(diǎn)v連通。由于u與v是任意的，所以G是連通圖。9/15/20216DiscreteMath.,huangliujia無向樹的性質(zhì)(續(xù))定理16.2設(shè)T是n階非平凡的無向樹，則T中至少有兩片樹葉.由上式解出x?2.證設(shè)T有x片樹葉，由握手定理及定理9.1可知，9/15/20217DiscreteMath.,huangliujia例題例1

7、已知無向樹T中,有1個(gè)3度頂點(diǎn),2個(gè)2度頂點(diǎn),其余頂點(diǎn)全是樹葉.試求樹葉數(shù),并畫出滿足要求的非同構(gòu)的無向樹.解用樹的性質(zhì)m=n?1和握手定理.設(shè)有x片樹葉，于是n=1+2+x=3+x,2m=2(n?1)=2?(2+x)=1?3+2?2+x解出x=3，故T有3片樹葉.T的度數(shù)列為1,1,1,2,2,3有2棵非同構(gòu)的無向樹,如圖所示9/15/20218DiscreteMath.,huangliujia例題例2已知無向樹T有5片樹葉,2度與3度頂點(diǎn)各1個(gè),其余頂點(diǎn)的度數(shù)均為4.求T的階數(shù)n,并畫出滿足要

8、求的所有非同構(gòu)的無向樹.解設(shè)T的階數(shù)為n,則邊數(shù)為n?1,4度頂點(diǎn)的個(gè)數(shù)為n?7.由握手定理得2m=2(n?1)=5?1+2?1+3?1+4(n?7)解出n=8,4度頂點(diǎn)為1個(gè).T的度數(shù)列為1,1,1,1,1,2,3,4有3棵非同構(gòu)的無向樹9/15/20219DiscreteMath.,huangliujia16.2生成樹定義16.2設(shè)G為無向連通圖G的生成樹:G的生成子圖并且是樹生成樹T的樹枝:G在T中的邊生成樹T的弦:G不在T中的邊注意：不一定連通,也不一定不含回路.生成樹T的