資源描述：
《《離散數(shù)學(xué)》PPT課件》由會員上傳分享，免費在線閱讀，更多相關(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無向樹:連通無回路的無向圖平凡樹:平凡圖森林:每個連通分支都是樹的非連通的無向圖樹葉:樹中度數(shù)為1的頂點分支點:樹中度數(shù)?2的頂點16.1無向樹及其性質(zhì)右圖為一棵12階樹.聲明:本章中所討論的回路均指簡單回路
2、或初級回路9/15/20213DiscreteMath.,huangliujia無向樹的性質(zhì)定理16.1設(shè)G=是n階m條邊的無向圖，則下列等價的：（1）G是樹;（2）G中任意兩個頂點之間存在惟一的路徑;（3）G中無回路且m=n?1;（4）G是連通的且m=n?1;（5）G是連通的且G中任何邊均為橋;（6）G中沒有回路,但在任何兩個不同的頂點之間加一條新邊后所得圖中有惟一的一個含新邊的圈.證明：①?②由于G是樹，所以G是連通的，?u,v?V，u和v之間存在一條路。若路不惟一，設(shè)L1和L2都是
3、u和v之間的路，則由L1和L2上的邊組成了G中的一個回路，矛盾。9/15/20214DiscreteMath.,huangliujia②?③先證G中無回路。若G中存在某個結(jié)點v上的環(huán)，?u?V，由條件知u到v存在一條路L1：u…v，則u到v有另一條路L2：u…vv，矛盾。若G中存在長度大于等于2的一條回路，則回路上兩個結(jié)點之間存在不同的路,矛盾。所以G中無回路。以下用歸納法證明m=n–1。當n=1時，G為平凡圖，m=0=1–1=n–1。結(jié)論成立。設(shè)n≤k時，結(jié)論成立。下證n=k+1時，結(jié)論也成立。
4、設(shè)e=(u,v)是G中的一條邊，由于G中無回路，所以G-?e?有兩個連通分支G1和G2，設(shè)它們的結(jié)點數(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)個連通分支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é)點數(shù)n1=n，m1=m–1=n-1-1=n-2=n1-2＜n1-1，由習題14的第49題知G1不是連通圖，所以e是橋。⑤?⑥由于G中每一條邊均為橋，因而G中無回路。又因為G連通，所以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的一個惟一的回路，故結(jié)點u和結(jié)點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個3度頂點,2個2度頂點,其余頂點全是樹葉.試求樹葉數(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度頂點各1個,其余頂點的度數(shù)均為4.求T的階數(shù)n,并畫出滿足要
8、求的所有非同構(gòu)的無向樹.解設(shè)T的階數(shù)為n,則邊數(shù)為n?1,4度頂點的個數(shù)為n?7.由握手定理得2m=2(n?1)=5?1+2?1+3?1+4(n?7)解出n=8,4度頂點為1個.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的
