圖論課件--最小生成樹

1、1,圖論及其應用,應用數(shù)學學院,2,本次課主要內(nèi)容,最小生成樹,(一)、克魯斯克爾算法,(二)、管梅谷的破圈法,(三)、Prim算法,(四)、計算機中的樹簡介,3,最小連接問題：,交通網(wǎng)絡中，常常關注能把所有站點連接起來的生成樹，使得該生成樹各邊權值之和為最小。例如：,假設要在某地建造5個工廠，擬修筑道路連接這5處。經(jīng)勘探，其道路可按下圖的無向邊鋪設?，F(xiàn)在每條邊的長度已經(jīng)測出并標記在圖的對應邊上，如果我們要求鋪設的道路總長度最短，這樣既能節(jié)省費用 ，又能縮短工期 ，如何鋪設？,4,不難發(fā)現(xiàn)：最小代價的連接方式為：,最小連接問題的一般提法為：,在連通邊賦權圖G中求一棵總權值最小的生成樹。該生成樹

2、稱為最小生成樹或最小代價樹。,(一)、克魯斯克爾算法,5,克魯斯克爾(Kruskal):1928年生，一家3弟兄都是數(shù)學家，1954年在普林斯頓大學獲博士學位，導師是Erds,他大部分研究工作是數(shù)學和語言學，主要在貝爾實驗室工作。1956年發(fā)表包含克魯斯克爾算法論文，使他名聲大振。,1、算法思想,從G中的最小邊開始，進行避圈式擴張。,2、算法,(1)、選擇邊e1,使得其權值最?。?(2)、若已經(jīng)選定邊e1, e2, ek, 則從E- e1, e2, ek 中選擇邊ek+1,使得：,(a)、Ge1, e2, ek+1為無圈圖,(b)、ek+1的權值w(ek+1)盡可能小。,6,(3)、當(2)不

3、能進行時，停止。,例1 用克魯斯克爾算法求下圖的最小生成樹。,7,解：過程如下：,8,2、算法證明,定理1 由克魯斯克爾算法得到的任何生成樹一定是最小生成樹。,證明：設G是一個n階連通賦權圖，用T*=Ge1,e2,en-1表示由克魯斯克爾算法得到的一棵生成樹，我們證明：它是最小生成樹。,9,設T是G的一棵最小生成樹。若T*T,由克魯斯克爾算法容易知道：TT*。,于是令f (T)= k 表示T*中的邊ei不在T中的最小i值。即可令T=Ge1,e2,ek-1, ek,en,考慮：Tek ,則由樹的性質(zhì)，它必然為G中圈。,作 T1= T ek- e ,容易知道：T1還為G的一棵生成樹。,設e是圈T

4、ek中在T中，但不在T*中的邊。,由克魯斯克爾算法知道：,所以：,這說明T1是最小樹，但這與f(T)的選取假設矛盾！所以：T = T*.,10,例2 在一個邊賦權G中，下面算法是否可以產(chǎn)生有最小權值的生成路？為什么？,算法: (1) 選一條邊e1,使得w(e1)盡可能??；,(2) 若邊e1,e2,ei已經(jīng)選定，則用下述方法從Ee1,.,ei中選取邊ei+1：,(a) G e1,e2,ei ,ei+1為不相交路之并；,(b) w(ei+1)是滿足(a)的盡可能小的權。,(3)當 (2)不能繼續(xù)執(zhí)行時停止。,解：該方法不能得到一條最小生成路。,11,例如，在下圖G中我們用算法求生成路：,用算法求出

5、的生成路為：,12,直接在圖中選出的一條生成路為：,后者的權值小于前者。,(二)、管梅谷的破圈法,在克魯斯克爾算法基礎上，我國著名數(shù)學家管梅谷教授于1975年提出了最小生成樹的破圈法。,13,管梅谷（）。我國著名數(shù)學家，曾任山東師范大學校長。中國運籌學會第一、二屆常務理事，第六屆全國政協(xié)委員。從事運籌學及其應用的研究，對最短投遞路線問題的研究取得成果 ，冠名為中國郵路問題，該問題被列入經(jīng)典圖論教材 和著作。,管梅谷教授1957年至1990年在山東師范大學工作。1984 年至1990年擔任山東師范大學校長，1990年至1995年任復旦 大學運籌學系主任。1995年至今任澳大利亞皇家墨爾本理工 大

6、學交通研究中心高級研究員，國際項目辦公室高級顧問及 復旦大學管理學院兼職教授。,自1986年以來，管教授致力于城市交通規(guī)劃的研究，在 我國最早引進加拿大的交通規(guī)劃EMME軟件，取得一系列重 要研究成果 。,14,破圈法求最小生成樹的求解過程是：從賦權圖G的任意圈開始，去掉該圈中權值最大的一條邊，稱為破圈。不斷破圈，直到G中沒有圈為止，最后剩下的G的子圖為G的最小生成樹。,證明可以參看數(shù)學的認識與實踐4，(1975),38-41。,例3 用破圈法求下圖G的最小生成樹。,15,解： 過程如下：,16,(三)、Prim算法,Prim算法是由Prim在1957年提出的一個著名算法。作者因此而出名。,P

7、rim(1921-) 1949年在普林斯頓大學獲博士學位，是Sandia公司副總裁。,Prim算法：,對于連通賦權圖G的任意一個頂點u，選擇與點u關聯(lián)的且權值最小的邊作為最小生成樹的第一條邊e1;,在接下來的邊e2,e3,en-1 ,在于一條已經(jīng)選取的邊只有一個公共端點的的所有邊中，選取權值最小的邊。,用反證法可以證明該算法。即證明：由Prim算法得到的生成樹是最小生成樹。(證明略),17,例4 用Prim算法求下圖的最小生成樹。,解：過程如下：,18,最小生成樹權值為：w (T) =10.,例5 連通圖G的樹圖是指這樣的圖，它的頂點是G的生成樹T1,T2,T, Ti與Tj相連，當且僅當它們恰

8、有n-2條公共邊。證明任何連通圖的樹圖是連通圖。,證明：只需證明,對任意Ti與Tj ，在樹圖中存在連接它們的路即可！,19,對任意Ti與Tj , 設e1,e2,ek(k n-2) 是它們的公共邊。,由樹的性質(zhì)：,使得： 。該圈中：,作：,則Ti與Ti+1有n-2條邊相同，于是，它們鄰接。此時，Ti+1與Tj有k+1條邊相同。,如此這樣作下去，可以得到連接Ti與Tj的一條路為：,所以，連通圖G的樹圖是連通的。,20,(四)、計算機中的樹簡介,在計算機科學中，常常遇到所謂的根樹。,定義2：一棵樹T，如果每條邊都有一個方向，稱這種樹為有向樹。對于T的頂點v來說，以點v為終點的邊數(shù)稱為點v的入度，以點

9、v為起點的邊數(shù)稱為點v的出度。入度與出度之和稱為點v的度。,注：指出上圖中頂點的入度、出度和度。,21,定義3：一棵非平凡的有向樹T，如果恰有一個頂點的入度為0，而其余所有頂點的入度為1，這樣的的有向樹稱為根樹。其中入度為0的點稱為樹根，出度為0的點稱為樹葉，入度為1，出度大于1的點稱為內(nèi)點。又將內(nèi)點和樹根統(tǒng)稱為分支點。,注：根樹常畫成倒置形式，方向由上指向下。,22,定義4：對于根樹T，頂點v到樹根的距離稱為點v的層數(shù)；所有頂點中的層數(shù)的最大者稱為根樹T的樹高。,上圖中，根樹高為3 ；,樹根1：0層； 點2，3，4：第1層；余類推。,23,計算機中數(shù)據(jù)結(jié)構常采用根樹結(jié)構。族譜圖是根樹。,定義

10、5：對于根樹T，若規(guī)定了每層頂點的訪問次序，這樣的根樹稱為有序樹。,注：一般次序為從左至右。有時也用邊的次序代替頂點次序。,定義6：對于根樹T，由點v及其v的后代導出的子圖，稱為根樹的子根樹。,24,定義7：對于根樹T，若每個分支點至多m個兒子，稱該根樹為m元根樹；若每個分支點恰有m個兒子，稱它為完全m元樹。,對于完全m元樹T，有如下性質(zhì)：,定理2 在完全m元樹T中，若樹葉數(shù)為t , 分支點數(shù)為i , 則：,25,證明：一方面，由樹的性質(zhì)得：,另一方面，由握手定理得：,由(1)與(2)消去m (T)得：,例6 一臺計算機，它有一條加法指令，可以計算3個數(shù)的和。如果要求9個數(shù)的和，問至少執(zhí)行多少

11、次加法指令？,解：用3個頂點表示3個數(shù)，用一個父結(jié)點表示3個數(shù)的和。問題轉(zhuǎn)化為求一棵有9個葉點的完全3元樹的分支點數(shù)。,26,即：m=3 , t= 9,求i=? 由定理2得：,i=4,至少要執(zhí)行4次。兩種可能情況是：,在m元樹中，應用最廣泛的是二元樹，原因是它在計算機中容易處理。,27,對于一棵有序樹，常要轉(zhuǎn)化為二元樹。方法是：,(1) 從根開始，保留每個父親同其最左邊兒子的連線，撤銷與別的兒子的連線；,(2) 兄弟間用從左至右的有向邊連接；,(3) 按如下方法確定二元樹中結(jié)點的左右兒子：直接位于給定結(jié)點下面的兒子，作為左兒子，對于同一水平線上 與給定結(jié)點右鄰的結(jié)點，作為右兒子，依此類推。,例

12、7 將下根樹轉(zhuǎn)化為二元樹。,28,解：,29,二元樹的遍歷問題,找到一種方法，能系統(tǒng)訪問根結(jié)點，使得每個結(jié)點恰好訪問一次。有三種常用方法：,(1) 先根次序遍歷：,1） 訪問根；,2）按先根次序遍歷根的左子樹；,3）按先根次序遍歷根的右子樹；,即：先左后右！例如：,30,先根次序遍歷次序為：v1v2v4v6v7v3v5v8v9v10v11v12.,(2) 中根次序遍歷：,2） 訪問根；,1）按中根次序遍歷根的左子樹；,3）按中根次序遍歷根的右子樹；,中根次序遍歷次序為：v6v4v7v2v1v8v5v11v10v12v9v3.,31,(3)后根次序遍歷：,3） 訪問根；,1）按后根次序遍歷根的左子樹；,2）按后根次序遍歷根的右子樹；,后根次序遍歷次序為：v6v7v4v2v8v11v12v10v9v5v3v1.,32,最優(yōu)二元樹,定義8 設T是一棵二元樹，若對所有t片樹葉賦權值wi(1it),且權值為wi的樹葉層數(shù)為L(wi),稱：,為該賦權二元樹的權。而在所有賦權為wi的二元樹中 W(T)最小的二元樹稱為最優(yōu)二元樹。,哈夫曼算法：,(1) 初始：令S=w1,w2,wt;,(2) 從S中取出兩個權值最小者wi