案例ab鋼鐵的配礦問題教學(xué)用教案

2023/6/8管理運籌學(xué)課程組391

第二節(jié)最小樹問題一、樹及其性質(zhì)定義1：無圈的連通圖稱為樹。樹一般用T表示。定理1：任給樹T=（V，E），若n（T）≥2，則

T中至少有兩個懸掛點。證明：設(shè)Q=（v1，v2，…，vk）是G中含邊數(shù)最多的一條初等鏈，因n（T）≥2，并且T是連通的，故鏈Q中至少有一條邊，從而v1與vk是不同的。現(xiàn)證v1是懸掛點，即d（v1）=1。2023/6/8管理運籌學(xué)課程組392反證法：如d（v1）≥2，則存在邊[v1，vm]，使m≠2，若vm不在Q上，v1v2vkvm

那么（vm，v1，v2，…，vk）比Q鏈邊數(shù)多一條，與Q是邊數(shù)最多的鏈矛盾。若vm在Q上v1v2vkvm

（v1，v2，…，vm，v1）是圈，與T是樹矛盾。所以必有d（v1）=1，即v1是懸掛點。同理可證：vk也是懸掛點。所以G至少有兩個懸掛點。2023/6/8管理運籌學(xué)課程組393（1）T是一個樹。

（2）T無圈，且m=n-1。

（3）T連通，且m=n-1。定理2圖T=（V，E），p=n，q=m，則下列關(guān)于樹的說法是等價的。邊數(shù)=點數(shù)-1

（4）T無圈，但每加一條新邊即得唯一一個圈。

（5）T連通，但每丟掉一條邊就不連通。

（6）T中任意兩點，有唯一鏈相連。先證明（6）→（1）2023/6/8管理運籌學(xué)課程組394證明：（1）→（2）由于T是樹，由定義知T連通且無圈。只須證明m=n-1。歸納法：當n=2時，由于T是樹，所以兩點間顯然有且僅有一條邊，滿足m=n-1。

假設(shè)n=k-1時命題成立，即有k-1個頂點時，T有k-2條邊。

當n=k時，因為T連通無圈，k個頂點中至少有一個點次為1。設(shè)此點為u，即u為懸掛點，設(shè)連接點u的懸掛邊為[v，u]，從T中去掉[v，u]邊及點u

，不會影響T的連通性，得圖T’，T’為有k-1個頂點的樹，所以T’有k-2條邊，再把（v，u）、點u加上去，可知當T有k個頂點時有k-1條邊。2023/6/8管理運籌學(xué)課程組395（2）→（3）只須證T是連通圖。反證法設(shè)T不連通，可以分為l個連通分圖（l≥2），設(shè)第i個分圖有ni個頂點，

因為第i個分圖是樹，所以有ni-1條邊，l個分圖共有邊數(shù)為：與已知矛盾。所以T為連通圖。

（3）→（4）、（4）→（5）、（5）→（6）、及（6）→（1）的證明略。2023/6/8管理運籌學(xué)課程組396定理2：圖T是樹，則T中的邊數(shù)m等于點數(shù)n減1，

即：m=n-1

證明：如圖圖T是樹，則依樹的定義，則T是連通圖，對于m=n-1可以用數(shù)學(xué)歸納法證明。（1）當n=1時，m=0，m=n-1成立。（2）當n=1時，m=1，m=n-1成立。（3）假設(shè)當n=k時，m=n-1成立。2023/6/8管理運籌學(xué)課程組397

（4）對于k+1個頂點的圖T而言，由樹的性質(zhì)1可知，T中至少有兩個懸掛點。設(shè)v1是T的一個懸掛點，考慮圖T-｛v1｝，則圖T-｛v1｝的頂點數(shù)為K，由歸納假設(shè)可得：，因為，，則，證畢。

2023/6/8管理運籌學(xué)課程組398

證明：必要性因T是連通的，故任兩個點之間至少有一條鏈。但如果某兩個點之間有兩條鏈的話，那么圖T中含有圈，這與樹的定義矛盾，從而任兩個點之間恰有一條鏈。

充分性設(shè)圖T中任兩個點之間恰有一條鏈，那么易見T是連通的，如果T中含有圈，那么這個圈上的兩個頂點之間有兩條鏈，這與假設(shè)矛盾，故T不含圈，于是T是樹。定理3：圖T是樹的充分必要條件是任意兩個頂點之間恰有一條鏈。2023/6/8管理運籌學(xué)課程組399

（1）T是無圈圖（2）T是連通圖（3）T中邊數(shù)為點數(shù)減1，即（4）T中減去一條邊則不連通（5）T中加一條邊則恰有一個圈（6）T中至少有兩個懸掛點

根據(jù)樹的定義及其三個性質(zhì)的證明，我們可以歸納出樹T的六個基本性質(zhì)，即：2023/6/8管理運籌學(xué)課程組3910二、圖的支撐樹

定義2設(shè)圖T=[V，E’]是圖G=（V，E）的支撐子圖，如果T是一個樹，則稱T是G的一個支撐樹。v1v3v2v4v5v6（a）v3v1v2v4v5v6（b）（b）是（a）的一個支撐樹。2023/6/8管理運籌學(xué)課程組3911定理4：圖G有支撐樹的充分必要條件是圖G是連通的。證明：必要性是顯然的。充分性：設(shè)G是連通的，如果G不含圈，則G本身是一個樹，從而是它自身的一個支撐樹。

現(xiàn)設(shè)G含圖，從圈中任意去掉一條邊，得G的一個支撐子圖G1，如G1不含圈，則G1是G的一個支撐樹；如G1含圈，則從G1中任取一圈，從圈中再任意去掉一條邊，得G的一個支撐子圖G2，如此重復(fù)，終可得G的一個不含圈的支撐子圖Gk，于是Gk是G的一個支撐樹。2023/6/8管理運籌學(xué)課程組3912（一）破圈法2023/6/8管理運籌學(xué)課程組39132023/6/8管理運籌學(xué)課程組3914例題破圈法求解v2v5e7e3e2v3v1v4e8e1e4e6e5v5v2v5e7e2v3v1v4e8e1e4e6e5v5v2e7e2v3v1v4e8e1e6e5（1）（2）（3）2023/6/8管理運籌學(xué)課程組3915v2e7e2v3v1v4e8e1e5v2e7e2v3v1v4e1e5（4）（5）2023/6/8管理運籌學(xué)課程組3916

在圖中任取一條邊e1，找一條與e1不構(gòu)成圈的邊e2，再找一條與{e1，e2}不構(gòu)成圈的邊e3。一般設(shè)已有{e1，e2，…，ek}，找一條與{e1，e2，…，ek}中任何一些邊不構(gòu)成圈的邊ek+1，重復(fù)這個過程，直到不能進行為止。（二）避圈法2023/6/8管理運籌學(xué)課程組3917v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v52023/6/8管理運籌學(xué)課程組3918三、最小支撐樹問題

定義3給定無向網(wǎng)絡(luò)圖G=（V，E，W），對于G的任一邊ek=[vi，vj]有一個非負權(quán)w（ek）=wij（wij≥0）,T=（V，E’）是G的一個支撐樹，稱為樹T的權(quán)。

如果支撐樹T*的權(quán)w（T*）是G的所有支撐樹的權(quán)中最小的，則稱T*是G的最小支撐樹（簡稱最小樹）。即最小樹問題，即求網(wǎng)絡(luò)G的最小支撐樹。2023/6/8管理運籌學(xué)課程組3919定理5設(shè)T是網(wǎng)絡(luò)的支撐樹，而任意一個樹外的邊，唯一決定一個圈，除e外，的其它邊都屬于T，如果T是G的最小支撐樹，則e是的最大邊。證明若T是最小支撐樹，因為T∪｛e｝含有一個圈C（e），任取一個邊e’∈C（e），

T∪｛e｝-｛e’｝仍然是連通不含圈的、即是一個樹，記T’=｛e｝-｛e’｝，則：因為T是最小樹，所以

,由于的任意性，則e是C（e）中的最大邊。2023/6/8管理運籌學(xué)課程組3920定理6設(shè)T是網(wǎng)絡(luò)G=(V,E,W)的支撐樹，則對于任意一條樹上的邊，e∈T,唯一決定一個G的割集,除了e外，上的其他邊都不屬于T，如果T是G的最小支撐樹，則e是的最小邊。

證明:設(shè)T-e有兩個連通子圖，它們的頂點集合分別是V1和V2，且e’∈

。因為T’=T-｛e｝∪｛e’｝是連通的，它也是G的支撐樹，而且：如果T是最小樹，則.因此。于是得證。2023/6/8管理運籌學(xué)課程組3921四最小支撐樹的算法（一）避圈法（Kruskal）思想：在圖中取一條最小權(quán)的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈（每一步中，如果有兩條或兩條以上的邊都是最小權(quán)的邊，則從中任選一條）。2023/6/8管理運籌學(xué)課程組3922Kruskal算法步驟：第1步：把G=(V,E)的邊按權(quán)由小到大排好，即要求w（e1）≤w

（e2）≤…≤w

（em）

圖G，p=n

，q=m，令i=1，j=0，E0=，第2步：如果（V，Ei-1ei）含圈，Ei=Ei-1，轉(zhuǎn)第3步，否則轉(zhuǎn)第4步；第3步：i換成i+1，如果i≤m，轉(zhuǎn)第2步，否則結(jié)束，

G沒有最小樹；取的邊數(shù)最小樹的邊集不要這條邊檢查過的邊數(shù)2023/6/8管理運籌學(xué)課程組3923第4步：令Ei=Ei-1ei，j換成j+1，如果j=n-1，結(jié)束，（V，Ei）是所求最小樹，否則轉(zhuǎn)第3步。取這條邊2345674v3v1v2v4v5v6152023/6/8管理運籌學(xué)課程組39242345674v3v1v2v4v5v6152345674v3v1v2v4v5v6152345674v3v1v2v4v5v6152345674v3v1v2v4v5v6152023/6/8管理運籌學(xué)課程組39252345674v3v1v2v4v5v615v62345674v3v1v2v4v5152345674v3v1v2v4v5v6152023/6/8管理運籌學(xué)課程組3926解：將各邊按權(quán)從小到大排為：w23≤w24≤w45≤w

56≤w

46≤w12≤w35≤w13≤w25i=1，j=0，E0=

，n=6，m=9

（V,E0e23）無圈，E1=E0e23={e23}，j=1<n-1,i=2,（V,E1e24）無圈,E2=E1e24={e23,e24}，j=2<n-1,i=3,（V,E2e45）無圈，E3=E2e45={e23,e24,e45}，

j=3<n-1,i=4,（V，E3e56）無圈，E4=E3e56={e23,e24,e45,e56}，

j=4<n-1,i=5,（V，E4e46）含圈，E5=E4,2023/6/8管理運籌學(xué)課程組3927i=6,（V，E5e12）無圈，

E6=E5e12={e23,e24,e45,e56,e12},j=5=n-1,結(jié)束。（V，E6）是所求的最小樹。2345674v3v1v2v4v5v6152023/6/8管理運籌學(xué)課程組3928問題1若要求前述網(wǎng)絡(luò)中點v2與v5必須直接連通，如何處理？討論：2345674v3v1v2v4v5v615------包含指定邊的最小樹。問題2有沒有比Kruskal算法更好的算法？2023/6/8管理運籌學(xué)課程組3929（二）反圈法(PRIM)

思想:

在n-1個獨立割集中（這n-1個獨立割集由網(wǎng)絡(luò)中不同的點集所確定），取每個割集的一條最小權(quán)邊，構(gòu)成一個支撐樹，它是一棵最小樹。從圖G（V，E）中任取一個頂點放入樹T中的點集VT中，對于將圖G分成VT、兩部分的割集來說，選取一權(quán)最小邊放入樹T的邊集ET中，并將該邊所關(guān)聯(lián)的頂點放入VT中，重復(fù)上述步驟，直至G中所有的頂點都選入VT為止。

2023/6/8管理運籌學(xué)課程組3930步驟:

第一步：

初始化令：i＝1（i為已在樹里點的數(shù)），ET＝Φ（ET為最小生成樹T的邊集），VT＝{v1}（把v1放入最小生成樹T的點集v1中）。Φ

第二步：對于頂點，比較vi到Vt中所有頂點的邊權(quán)，選取權(quán)最小的邊，作為該點到Vt中點的權(quán)的標號，記為DIST[vi]，并記錄下該最小權(quán)邊在VT中所關(guān)聯(lián)的頂點，記λ[vi]，如果與Vt中所有頂點都不關(guān)聯(lián)，則DIST[vi]＝∞,λ[vi]＝0。2023/6/8管理運籌學(xué)課程組3931第三步對于，比較DIST[vi]，選取，如果DIST[vK]為∞，則輸出“圖不連通”，算法結(jié)束；否則將vK放入VT中，i＝i+1，將[vk，λ[vk]]放入ET中，如果i＝n（n為網(wǎng)絡(luò)的頂點數(shù)），則輸出最小支撐樹，算法結(jié)束；否則轉(zhuǎn)步驟二。2023/6/8管理運籌學(xué)課程組3932例題：如圖所示是一個無向網(wǎng)絡(luò)，試用反圈法求最小支撐樹。2726141943v2v1v3v5v7v62028v4182224242023/6/8管理運籌學(xué)課程組3933第一輪：i＝1，ET＝{Φ}，λ[j]=0(j=1,2…6)，

DIST[j]=∞(j=1,2…6)選擇節(jié)點v1,VT={1}，

DIST[2]＝43，λ[2]＝1；

DIST[3]＝27，λ[3]＝1；√

DIST[4]＝∞，λ[4]＝0；

DIST[5]＝∞，λ[5]＝0；

DIST[6]＝∞，λ[6]＝0；

DIST[7]＝∞，λ[7]＝0。如圖，其中虛線表示未選邊，實線表示已選邊。v143v3v2272023/6/8管理運籌學(xué)課程組3934第二輪：選擇節(jié)點v3，i＝2，VT＝{1，3}，

ET＝{[1，3]}。DIST[2]＝28，λ[2]＝3；DIST[4]＝26，λ[4]＝3；DIST[5]＝14，λ[5]＝3；√DIST[6]＝∞，λ[6]＝0；DIST[7]＝∞，λ[7]＝0。如下圖v143v3v22728v4v526142023/6/8管理運籌學(xué)課程組3935第三輪：選擇節(jié)點v5，i＝3，VT＝{1，3，5}，ET＝{[1，3]，[3，5]}。DIST[2]＝28，λ[2]＝3；DIST[4]＝19，λ[4]＝5；√DIST[6]＝24，λ[6]＝5；DIST[7]＝∞，λ[7]＝0。如圖：v143v3v22728v4v526141924v62023/6/8管理運籌學(xué)課程組3936第四輪：選擇節(jié)點v4，i＝4，VT＝{1，3，4，5}，

ET＝{[1，3]，[3，5]，[4，5]}。DIST[2]＝20，λ[2]＝4；DIST[6]＝18，λ[6]＝4；√DIST[7]＝∞，λ[7]＝0。見圖：v2v143v32728v4v526141924v618202023/6/8管理運籌學(xué)課程組3937第五輪：選擇節(jié)點v6，i＝5，VT＝{1，3，4，5，6}，ET＝{[1，3]，[3，5]，[4，5]，[4，6]}。DIST[2]＝20，λ[2]＝4；√DIST[7]＝22，λ[7]＝6。見下圖：v143v32728v4v5141924v61820v722v22023/6/8管理運籌學(xué)課程組3938第六輪：選擇節(jié)點v2，i＝6，VT＝{1，2，3，4，5，6}，ET＝{[1，3]，[3，5]，[4，5]，[4，6]，[2，4]}。

DIST[7]＝22，λ[7]＝6。見下圖：v1v327v4v5141924v61820v722v22023/6/8管理運籌學(xué)課程組3939第七輪：選擇節(jié)點v7，i＝7，VT＝{1，2，3，4，5，6，7}，ET＝{[1，3]，[3，5]，[4，5]，[4，6]，[2，4]，[6，7]}，得到最小支撐樹。見下圖：v1v327v4v51419v61820v722v22023/6/8管理運籌學(xué)課程組39402345674v3v1v2v4v5v6152023/6/8管理運籌學(xué)課程組39412023/6/8管理運籌學(xué)課程組3942v62345674v3v1v2v4v5512023/6/8管理運籌學(xué)課程組3943（三）破圈法

思想：設(shè)G（k）是G的連通生成子圖（開始G（0）

=G

），若G（k）中不包含圈，則它是最小支撐樹；若G（k）中包含圈，設(shè)C（k）是

G（k）中的一個圈，取C（k）上的一條權(quán)最大的邊e（k），令G（k+1）=G（k）-{e（k）

}，重復(fù)上述過程，直到找不到圈為止。2023/6/8管理運籌學(xué)課程組3944例下圖是一個無向網(wǎng)絡(luò)，使用破圈法，求最小

支撐樹。2726141943v2v1v3v5v7v62028v4182224242023/6/8管理運籌學(xué)課程組3945算法步驟如下：解：第一輪：G（0）=G

，找到圈C（0），最大權(quán)邊

e（0）＝[1,2]，w(e（0）)=43，去掉該邊。見下圖：v2v7242726141943v1v3v5v62028v4182224C（0）2023/6/8管理運籌學(xué)課程組3946第二輪：

G（1）=G（0）-e（0）

，找到圈C（1）

，最大權(quán)邊e（1）＝[2，3]，w(e（1）)=28

，去掉該邊。見下圖：v2v72427261419v1v3v5v62028v4182224C（1）2023/6/8管理運籌學(xué)課程組3947第三輪：G（2）=G（1）-e（1），找到圈C（2），最大權(quán)邊e（2）＝[2，7]，w(e（2）