離散數(shù)學及其應用課件：樹

樹7.1無向樹及生成樹7.2根樹及其應用

7.1無向樹及生成樹

7.1.1無向樹定義7.1連通而不含回路的無向圖稱為無向樹(UndirectedTree),簡稱樹(Tree)。樹一定是簡單圖,常用T表示樹。圖7-1給出了具有7個頂點的所有互不同構的樹。圖7-1不同構的樹

(1)連通分支數(shù)大于等于2,且每個連通分支均是樹的非連通無向圖稱為森林(Forest)。

(2)平凡圖稱為平凡樹(OrdinaryTree),即只有一個頂點的樹。

(3)設T=<V,E>為一棵無向樹,v∈V,若d(v)=1,則稱v為T的樹葉(Leaf)。若d(v)>1,則稱v為T的分支點(BranchPoint)。

定理7.1設G=<V,E>是n階無向圖,G中有m條邊,則下面關于G是樹的命題是等價的:

(1)G連通而不含回路;

(2)G的每對頂點之間具有唯一的一條路徑;

(3)G中無回路且n=m+1;

(4)G是連通的且n=m+1;

(5)G中無回路,但在G中任意兩個不相鄰的頂點之間增加一條邊,就形成唯一的一條初級回路;

(6)G是連通的且G中每條邊都是橋;

(7)G是連通的,但刪除任何G=<V,E>一條邊后,就不連通了。

證明(1)根據(jù)無向樹的定義,(1)是顯然的。

(2)根據(jù)(1)推證(2)。

由G的連通性及定理5.5的推論可知,?u,v∈V,u與v之間存在一條路徑。若路徑不是唯一的,設T1和T2都是u到v的路徑,則必定存在由T1和T2上的邊構成的回路,這與G中無回路矛盾。

例7.1圖7-2所示的無向圖:圖(a)是一棵樹,其中b、c、d是樹葉,a、e是分支點;圖(b)是一棵樹,其中b、c、e是樹葉,a、d是分支點;圖(c)不是樹,因為a、e、d、c、a是這個圖中的簡單回路;圖(d)不是樹,因為它不連通。圖7-2無向圖

例7.2設T是一棵樹,它有三個2度結點,兩個3度結點,一個4度結點,求T的樹葉數(shù)。

例7.3如圖7-3所示,圖(b)為圖(a)的一棵生成樹T,圖(c)為T的余樹。

注意余樹不一定是樹。

考慮生成樹圖(b),可知e1、e2、e3、e4是圖(b)的樹枝,e5、e6、e7、e8是圖(b)的弦,集合{e5,e6,e7,e8}是圖(b)的補。生成樹在生活中有一定的實際意義。圖7-3生成樹及余樹

例7.4某地區(qū)需建筑6個水塔,并且這6個水塔間都有道路相通,那么至少要修筑幾條道路?

解此問題實際上是求G的生成樹的邊數(shù)的問題。

通常情況下,假設連通圖G有n個結點,m條邊。由樹的性質可知,T有n個結點,n-1條樹枝,m-n+1條弦。

問題中n=6,則有n-1=6-1=5,所以至少要修筑5條路才行。

定理7.3無向圖G具有生成樹當且僅當G是連通的。

證明(1)必要性。

如果G不連通,則它的任何生成子圖也不連通,因此不可能有生成樹,與G有生成樹矛盾,故G是連通圖。

(2)充分性。

推論1設n階無向連通圖G有m條邊,則m≥n-1。

推論2設n階無向連通圖G有m條邊,T是G的生成樹,T'是T的余樹,則T'中有m-n+1條邊。

2.基本回路和基本割集

例7.5圖7-4中圖G的生成樹,實線邊所構成的子圖是G的一棵生成樹T,求T對應的基本回路和基本回路系統(tǒng),以及基本割集和基本割集系統(tǒng)。圖7-4圖G的生成樹

7.1.3最小生成樹

定義7.5設無向連通帶權圖G=<V,E,W>,T是G的一棵生成樹。各邊帶權之和稱為T的權(Weight),記作W(T)。G的所有生成樹中帶權最小的生成樹稱為最小生成樹(MinimalSpanningTree)。

最小生成樹在實際生活中有許多重要應用。比如建設城市與城市之間的交通網(wǎng)絡,每兩個城市之間都有直達道路的造價,如果設計一個總造價最小值的交通網(wǎng)絡,就是求最小生成樹。

最小生成樹求解算法———Prim算法:

(1)在G中任意選取一個結點v1,并置U={v1},置最小生成樹的邊集TE=?。

(2)令u∈U,v∈V-U的邊(u,v)∈E中,選取權值最小的邊(u,v),將(u,v)并入TE中,同時將v并入U。

(3)重復(2),直到U=V為止。

例7.6求圖7-5(a)所示有權圖的最小生成樹。圖7-5最小生成樹的構造過程

解因為圖7-5(a)中n=6,所以按算法要執(zhí)行n-1=5次。第一步給所有的邊按照從小到大的順序排序,即選邊的順序為ab(0.5),ae(1),ao(1.5),ed(2),bc(2.5),cd(3),od(3.5),ac(4),oe(5),oc(6)。第二步選擇權最小的邊加入TE,循環(huán)執(zhí)行此步,直到構成最小生成樹為止。其構造最小生成樹的過程如圖7-5(b)~(f)所示。T的權為W(T)=0.5+1+1.5+2+3=8。

例7.7-分別用Kruskal算法和Prim算法求圖7-6中所示帶權圖的最小生成樹。圖7-6一個帶權圖

解(1)圖7-7顯示了這個最小生成樹和在Kruskal算法中每個階段上對邊的選擇過程。

(2)圖7-8顯示了這個最小生成樹和在Prim算法中每個階段上對邊的選擇過程。

從例7.7中可以看出Kruskal算法和Prim算法的區(qū)別。在Kruskal算法里,為了讓每一步過程是確定的,首先對邊排序,選擇邊不一定與已在樹里的一個頂點相關聯(lián)并且不形成回路的權最小的邊。而在Prim算法里,沒有對邊排序,在選擇邊的過程中,對添加的邊可能有多于一種的選擇,只要選擇與已在樹里的一個頂點相關聯(lián)并且不形成回路的權最小的邊即可。圖7-7-用Kruskal算法構造的最小生成樹圖7-8用Prim算法構造的最小生成樹

最小生成樹算法都是貪心算法的例子。貪心算法是在每一步驟上都做最優(yōu)選擇的算法,而不考慮下次如何選擇。這種方式稱作“局部最優(yōu)”。但是算法的每一步都是最優(yōu),并不一定產生的是全局最優(yōu)解。

如果將算法用在如圖7-9所示的有權圖中由a到d的最短路徑,將會選擇(a,b)和(b,d),但這并不是從a到d的最短路徑,因為從a到d的最短路徑是(a,c,d)。圖7-9有權圖的最短路徑

7.2根樹及其應用

7.2.1根樹的概念定義7.6一個有向圖D,如果略去有向邊的方向所得的無向圖為一棵無向樹,則稱D為有向樹。換句話說,若有向圖的基圖是無向樹,那么這個有向圖為有向樹。入度為0的頂點稱為樹根(Root),入度為1且出度為0的頂點稱為樹葉;入度為1且出度大于0的頂點稱為內點。內點和樹根統(tǒng)稱為分支點。有一種特殊結構的有向樹叫根樹。

定義7.7-一棵非平凡的有向樹,如果有一個頂點的入度為0,其余頂點的入度均為1,則稱此有向樹為根樹(RootTree)。在根樹中,從樹根到任意頂點v的通路長度稱為v的層數(shù),記為l(v)。層數(shù)相同的頂點在同一層上,層數(shù)最大的頂點的層數(shù)稱為樹高。根樹T的樹高記為h(T)。

例7.8圖7-10(a)、(b)、(c)、(d)均為有向樹,其中只有圖(c)和圖(d)為根樹。在根樹圖(d)中,a為樹根,b、d、e為分支點,其余結點均為樹葉。圖7-10有向樹

習慣上把根樹的根畫在上方,葉畫在下方,這樣就可以省去根樹的箭頭,如圖(d)的根樹可以用圖(e)表示。

在根樹中,稱從樹根到結點v的距離為該點的層次。在圖7-10所示的根樹(e)中,a的層次為0,b、d的層次為1,g、c、e、f的層次均為2,而h和i的層次為3。

一棵根樹可以看成一棵家族樹,如圖7-11所示:

(1)若頂點a鄰接到頂點b,則稱b為a的兒子,a為b的父親;

(2)若b,d同為a的兒子,則稱b,d為兄弟;

(3)若a≠c,而a可達c,則稱a為c的祖先,c為a的后代。圖7-11家族樹

定義7.8設T為一棵根樹,v為T中一個結點,且v不是樹根,稱v及其后代導出的子圖T'為T的以v為根的子樹,簡稱根子樹。

例7.9在圖7-12(a)所示的根樹里(有根a),求g的父母,d的子女,f的兄弟,m的所有祖先,b的所有后代,所有內點以及所有樹葉,并畫出根在d處的子樹。

解g的父母是b。d的子女是e。f的兄弟是h和i。m的所有祖先是g、b、a。b的所有后代是g、k、m。內點是a、b、g、c、d和e。樹葉是k、m、j、h、f和i。根在d處的子

樹如圖7-12(b)所示。圖7-12根樹T及根在d處的子樹

7.2.2二叉樹

1.二叉樹的概念

定義7.9設T為一棵根樹,若T的每個分支點至多有r個兒子,則稱T為r叉樹;若r叉樹T的每一層頂點都有規(guī)定的次序,則稱T是r叉有序樹;若T的每個分支點都恰好有r個兒子,則稱T為r叉正則樹;若r叉正則樹T是有序的,則稱T是r叉有序正則樹;若T是r叉正則樹,且所有樹葉的層數(shù)相同,都等于樹高,則稱T為r叉完全正則樹;若r叉完全正則樹T是有序樹,則稱T是r叉有序完全正則樹。

當r=2時,我們可以類似地給出二叉樹、二叉正則樹、二叉有序樹、二叉有序正則樹、二叉完全正則樹、二叉有序完全正則樹的概念。二叉樹是使用最為廣泛的r叉樹。

例7.10圖7-13所示樹中,圖(a)是一棵二叉樹;圖(b)是一棵二叉正則樹;圖(c)是一棵三叉樹;圖(d)是一棵三叉完全正則樹。圖7-13二叉樹

例7.11計算機中存儲的文件目錄,目錄可以包含子目錄和文件。圖7-14用多叉樹表示一個文件系統(tǒng)。C表示根目錄,可以表示成根樹,內點表示子目錄,樹葉表示文件或空目錄。圖7-14多叉樹表示的文件系統(tǒng)

2.二叉樹的遍歷

定義7.10對于一棵根樹的每個結點都訪問一次且僅一次稱為行遍或周游一棵樹。

對于二叉有序正則樹主要有以下3種遍歷算法。

(1)中序遍歷算法。若二叉樹非空,則依次執(zhí)行如下操作:

①在根的左子樹上執(zhí)行中序遍歷算法;

②訪問根結點;

③在根的右子樹上執(zhí)行中序遍歷算法。

(2)前序遍歷算法。若二叉樹非空,則依次執(zhí)行如下操作:

①訪問根結點;

②在根的左子樹上執(zhí)行前序遍歷算法;

③在根的右子樹上執(zhí)行前序遍歷算法。

(3)后序遍歷算法。若二叉樹非空,則依次執(zhí)行如下操作:

①在根的左子樹上執(zhí)行后序遍歷算法;

②在根的右子樹上執(zhí)行后序遍歷算法;

③訪問根結點。

例7.12假設有算術表達式

(1)用二叉有序正則樹表示。

(2)用3種方法遍歷此樹,寫出遍歷結果。

解(1)該算術表達式的二叉有序正則樹表示如圖7-15所示。圖7-15二叉有序正則樹

3.二叉搜索樹

計算機科學的一項重要任務就是在列表里搜索一些項。這個任務可以使用二叉搜索樹算法來完成。二叉搜索樹是一種二叉樹,其中任何結點的每個子女都指定為左子女或右子

女,每個結點都用一個關鍵字來標記,同時要求結點的關鍵字不僅大于它的左子樹里的所有結點的關鍵字,而且小于它的右子樹里的所有結點的關鍵字。

例7.13構造下面的一組詞的二叉搜索樹(按字母順序):

解可以放在如圖7-16所示給定單詞的二叉搜索樹上,對于任意結點v來說,v的左子樹的任意數(shù)據(jù)項都比v中的數(shù)據(jù)項小(依據(jù)字母表順序),而v的右子樹的任意數(shù)據(jù)項都比v中的數(shù)據(jù)項大。圖7-16給定單詞二叉搜索樹圖7-16給定單詞二叉搜索樹

7.2.3最優(yōu)二叉樹及其應用

1.哈夫曼樹

例7.14計算圖7-17所示帶權二叉樹的權值。圖7-17-帶權二叉樹

解圖7-17所示帶權二叉樹的權值分別為

常用哈夫曼(Huffman)算法構造最優(yōu)二叉樹。通常稱哈夫曼算法構造的最優(yōu)二叉樹為哈夫曼樹。

例7.15求帶權5、9、11、12、16、18的最優(yōu)二叉樹。

解圖7-18給出了所給權值的哈