圖論-最小生成樹

圖論及其應用應用數(shù)學學院1精選課件本次課主要內(nèi)容最小生成樹(一)、克魯斯克爾算法(二)、管梅谷的破圈法(三)、Prim算法(四)、計算機中的樹簡介2精選課件最小連接問題：交通網(wǎng)絡(luò)中，常常關(guān)注能把所有站點連接起來的生成樹，使得該生成樹各邊權(quán)值之和為最小。例如：假設(shè)要在某地建造5個工廠，擬修筑道路連接這5處。經(jīng)勘探，其道路可按下圖的無向邊鋪設(shè)?，F(xiàn)在每條邊的長度已經(jīng)測出并標記在圖的對應邊上，如果我們要求鋪設(shè)的道路總長度最短，這樣既能節(jié)省費用，又能縮短工期，如何鋪設(shè)？v1v2v3v4v5122434553精選課件v1v2v3v4v51223不難發(fā)現(xiàn)：最小代價的連接方式為：最小連接問題的一般提法為：在連通邊賦權(quán)圖G中求一棵總權(quán)值最小的生成樹。該生成樹稱為最小生成樹或最小代價樹。(一)、克魯斯克爾算法4精選課件克魯斯克爾(Kruskal):1928年生，一家3弟兄都是數(shù)學家，1954年在普林斯頓大學獲博士學位，導師是Erd?s,他大部分研究工作是數(shù)學和語言學，主要在貝爾實驗室工作。1956年發(fā)表包含克魯斯克爾算法論文，使他名聲大振。1、算法思想從G中的最小邊開始，進行避圈式擴張。2、算法(1)、選擇邊e1,使得其權(quán)值最小；(2)、若已經(jīng)選定邊e1,e2,…,ek,則從E-｛e1,e2,…,ek｝中選擇邊ek+1,使得：(a)、G[e1,e2,…,ek+1]為無圈圖(b)、ek+1的權(quán)值w(ek+1)盡可能小。5精選課件(3)、當(2)不能進行時，停止。例1用克魯斯克爾算法求下圖的最小生成樹。3v721546789101112v1v2v3v4v5v6v86精選課件解：過程如下：1v5v821v1v5v8321v1v4v5v83v7215v1v4v5v83v72156v1v4v5v8v37精選課件3v72156v1v4v5v8v3v683v72156v1v4v5v8v3v68v292、算法證明定理1由克魯斯克爾算法得到的任何生成樹一定是最小生成樹。證明：設(shè)G是一個n階連通賦權(quán)圖，用T*=G[｛e1,e2,…,en-1｝]表示由克魯斯克爾算法得到的一棵生成樹，我們證明：它是最小生成樹。8精選課件設(shè)T是G的一棵最小生成樹。若T*≠T由克魯斯克爾算法容易知道：T∩T*≠Φ。于是令f(T)=k表示T*中的邊ei不在T中的最小i值。即可令T=G[｛e1,e2,…,ek-1,e'k,…,e'n｝]考慮：T∪ek,則由樹的性質(zhì)，它必然為G中圈。作T1=T∪ek-e,容易知道：T1還為G的一棵生成樹。設(shè)e是圈T∪ek中在T中，但不在T*中的邊。由克魯斯克爾算法知道：所以：這說明T1是最小樹，但這與f(T)的選取假設(shè)矛盾！所以：T=T*.9精選課件例2在一個邊賦權(quán)G中，下面算法是否可以產(chǎn)生有最小權(quán)值的生成路？為什么？算法:(1)選一條邊e1,使得w(e1)盡可能?。?/p>

(2)若邊e1,e2,…,ei已經(jīng)選定，則用下述方法從E\｛e1,..,ei｝中選取邊ei+1：

(a)G[｛e1,e2,…,ei

,ei+1｝]為不相交路之并；

(b)w(ei+1)是滿足(a)的盡可能小的權(quán)。

(3)當(2)不能繼續(xù)執(zhí)行時停止。

解：該方法不能得到一條最小生成路。10精選課件

例如，在下圖G中我們用算法求生成路：3122343667910用算法求出的生成路為：12269311精選課件直接在圖中選出的一條生成路為：123366

后者的權(quán)值小于前者。(二)、管梅谷的破圈法

在克魯斯克爾算法基礎(chǔ)上，我國著名數(shù)學家管梅谷教授于1975年提出了最小生成樹的破圈法。12精選課件

管梅谷（１９３４－）。我國著名數(shù)學家，曾任山東師范大學校長。中國運籌學會第一、二屆常務(wù)理事，第六屆全國政協(xié)委員。從事運籌學及其應用的研究，對最短投遞路線問題的研究取得成果，冠名為中國郵路問題，該問題被列入經(jīng)典圖論教材和著作。

管梅谷教授1957年至1990年在山東師范大學工作。1984年至1990年擔任山東師范大學校長，1990年至1995年任復旦大學運籌學系主任。1995年至今任澳大利亞皇家墨爾本理工大學交通研究中心高級研究員，國際項目辦公室高級顧問及復旦大學管理學院兼職教授。

自1986年以來，管教授致力于城市交通規(guī)劃的研究，在我國最早引進加拿大的交通規(guī)劃EMMEⅡ軟件，取得一系列重要研究成果。13精選課件

破圈法求最小生成樹的求解過程是：從賦權(quán)圖G的任意圈開始，去掉該圈中權(quán)值最大的一條邊，稱為破圈。不斷破圈，直到G中沒有圈為止，最后剩下的G的子圖為G的最小生成樹。

證明可以參看《數(shù)學的認識與實踐》4，(1975),38-41。3122343667910

例3用破圈法求下圖G的最小生成樹。14精選課件312234366710

解：

過程如下：312234667103122366710312266710312266731226615精選課件(三)、Prim算法

Prim算法是由Prim在1957年提出的一個著名算法。作者因此而出名。

Prim(1921---)1949年在普林斯頓大學獲博士學位，是Sandia公司副總裁。

Prim算法：

對于連通賦權(quán)圖G的任意一個頂點u，選擇與點u關(guān)聯(lián)的且權(quán)值最小的邊作為最小生成樹的第一條邊e1;

在接下來的邊e2,e3,…,en-1,在于一條已經(jīng)選取的邊只有一個公共端點的的所有邊中，選取權(quán)值最小的邊。

用反證法可以證明該算法。即證明：由Prim算法得到的生成樹是最小生成樹。(證明略)16精選課件例4用Prim算法求下圖的最小生成樹。554432176v1v2v3v4v5解：過程如下：1v1v231v1v2v317精選課件431v1v2v3v44321v1v2v3v4v5

最小生成樹權(quán)值為：w(T)=10.例5連通圖G的樹圖是指這樣的圖，它的頂點是G的生成樹T1,T2,…,Tτ,Ti與Tj相連，當且僅當它們恰有n-2條公共邊。證明任何連通圖的樹圖是連通圖。證明：只需證明,對任意Ti與Tj

，在樹圖中存在連接它們的路即可！18精選課件對任意Ti與Tj,設(shè)｛e1,e2,…,ek｝(k<n-2)是它們的公共邊。由樹的性質(zhì)：使得：。該圈中：作：則Ti與Ti+1有n-2條邊相同，于是，它們鄰接。此時，Ti+1與Tj有k+1條邊相同。如此這樣作下去，可以得到連接Ti與Tj的一條路為：所以，連通圖G的樹圖是連通的。19精選課件(四)、計算機中的樹簡介在計算機科學中，常常遇到所謂的根樹。定義2：一棵樹T，如果每條邊都有一個方向，稱這種樹為有向樹。對于T的頂點v來說，以點v為終點的邊數(shù)稱為點v的入度，以點v為起點的邊數(shù)稱為點v的出度。入度與出度之和稱為點v的度。u7u5u4u3u2u1u6有向樹T注：指出上圖中頂點的入度、出度和度。20精選課件定義3：一棵非平凡的有向樹T，如果恰有一個頂點的入度為0，而其余所有頂點的入度為1，這樣的的有向樹稱為根樹。其中入度為0的點稱為樹根，出度為0的點稱為樹葉，入度為1，出度大于1的點稱為內(nèi)點。又將內(nèi)點和樹根統(tǒng)稱為分支點。倒置根樹T根樹T注：根樹常畫成倒置形式，方向由上指向下。21精選課件定義4：對于根樹T，頂點v到樹根的距離稱為點v的層數(shù)；所有頂點中的層數(shù)的最大者稱為根樹T的樹高。上圖中，根樹高為3；倒置根樹T2176435891011樹根1：0層；點2，3，4：第1層；余類推。22精選課件計算機中數(shù)據(jù)結(jié)構(gòu)常采用根樹結(jié)構(gòu)。族譜圖是根樹。定義5：對于根樹T，若規(guī)定了每層頂點的訪問次序，這樣的根樹稱為有序樹。注：一般次序為從左至右。有時也用邊的次序代替頂點次序。定義6：對于根樹T，由點v及其v的后代導出的子圖，稱為根樹的子根樹。倒置根樹T2176435891011根樹T的對應點2的子根樹2591023精選課件定義7：對于根樹T，若每個分支點至多m個兒子，稱該根樹為m元根樹；若每個分支點恰有m個兒子，稱它為完全m元樹。3元根樹T2176435891011完全3元根樹T2176435891011對于完全m元樹T，有如下性質(zhì)：定理2在完全m元樹T中，若樹葉數(shù)為t,分支點數(shù)為i,則：24精選課件證明：一方面，由樹的性質(zhì)得：另一方面，由握手定理得：由(1)與(2)消去m(T)得：例6一臺計算機，它有一條加法指令，可以計算3個數(shù)的和。如果要求9個數(shù)的和，問至少執(zhí)行多少次加法指令？解：用3個頂點表示3個數(shù)，用一個父結(jié)點表示3個數(shù)的和。問題轉(zhuǎn)化為求一棵有9個葉點的完全3元樹的分支點數(shù)。25精選課件即：m=3,t=9,求i=?由定理2得：i=4,至少要執(zhí)行4次。兩種可能情況是：x6x5x4x3x2x1x7x8x9x1x2x3x4x5x6x7x8x9在m元樹中，應用最廣泛的是二元樹，原因是它在計算機中容易處理。26精選課件對于一棵有序樹，常要轉(zhuǎn)化為二元樹。方法是：

(1)從根開始，保留每個父親同其最左邊兒子的連線，撤銷與別的兒子的連線；

(2)兄弟間用從左至右的有向邊連接；

(3)按如下方法確定二元樹中結(jié)點的左右兒子：直接位于給定結(jié)點下面的兒子，作為左兒子，對于同一水平線上與給定結(jié)點右鄰的結(jié)點，作為右兒子，依此類推。例7將下根樹轉(zhuǎn)化為二元樹。v1v2v3v4v5v6v7v8v9根樹Tv10v1127精選課件解：v1v2v3v4v5v6v7v8v9v10v11v1v2v3v4v5v6v7v8v9v10v1128精選課件二元樹的遍歷問題找到一種方法，能系統(tǒng)訪問根結(jié)點，使得每個結(jié)點恰好訪問一次。有三種常用方法：

(1)先根次序遍歷：

1）訪問根；

2）按先根次序遍歷根的左子樹；

3）按先根次序遍歷根的右子樹；即：先左后右！例如：v1v2v3v4v5v6v7v8v9v10v12v1129精選課件先根次序遍歷次序為：v1v2v4v6v7v3v5v8v9v10v11v12.

(2)中根次序遍歷：

2）訪問根；

1）按中根次序遍歷根的左子樹；

3）按中根次序遍歷根的右子樹；v1v2v3v4v5v6v7v8v9v10v12v11中根次序遍歷次序為：v6v4v7v2v1v8v5v11v10v12v9v3.30精選課件

(3)后根次序遍歷：

3）訪問根；

1）按后根次序遍歷根的左子樹；

2）按后根次序遍歷根的右子樹；v1v2v3v4v5v6v7v8v9v10v12v11后根次序遍歷次序為：v6v7v4v