圖論講義1圖路樹

1、圖論與網(wǎng)絡(luò)流理論(Graph Theory and Network Flow Theory講授:高隨祥中科院研究生院專業(yè)基礎(chǔ)課學(xué)時 /學(xué)分:60/3本課程適合基礎(chǔ)數(shù)學(xué)、應(yīng)用數(shù)學(xué)、計算數(shù)學(xué)、運籌學(xué)與控制論、概率論與數(shù) 理統(tǒng)計各專業(yè)的碩士學(xué)位研究生作為專業(yè)基礎(chǔ)課, 也可供物理學(xué)、 化學(xué)、 天文學(xué)、 地學(xué)、生物科學(xué)、計算機(jī)科學(xué)與技術(shù)、計算機(jī)軟件、管理科學(xué)與工程以及通信、 信號等學(xué)科專業(yè)的碩士研究生選修。 主要講授圖論與網(wǎng)絡(luò)流理論的基本概念、 方 法和定理, 介紹該領(lǐng)域重要的問題以及典型的算法, 展示圖論與網(wǎng)絡(luò)流模型及方 法的廣泛應(yīng)用。 為學(xué)習(xí)者將來從事有關(guān)方面的理論研究打下基礎(chǔ), 也為進(jìn)行應(yīng)用 性研

2、究提供一種有力的工具。內(nèi)容提要第一章 圖的基本概念圖的基本概念;二部圖及其性質(zhì);圖的同構(gòu);關(guān)聯(lián)矩陣與鄰接矩陣。路、圈與連通圖;最短路問題。樹及其基本性質(zhì);生成樹;最小生成樹。第二章 圖的連通性割點、割邊和塊;邊連通與點連通;連通度; Whitney 定理;可靠通信網(wǎng)絡(luò)的設(shè)計。 第三章 匹配問題匹配與最大匹配;完美匹配;二部圖的最大匹配;指派問題與最大權(quán)匹配。第四章 歐拉圖與哈密爾頓圖歐拉圖;中國郵遞員問題;哈密爾頓圖;旅行商問題。第五章 支配集、獨立集、覆蓋集與團(tuán)支配集、點獨立集、點覆蓋集、邊覆蓋集與團(tuán)的概念及其求法。第六章 圖的著色問題點著色;邊著色;平面圖;四色猜想;色多項式;色數(shù)的應(yīng)用。

3、第七章 網(wǎng)絡(luò)流理論有向圖;網(wǎng)絡(luò)與網(wǎng)絡(luò)流的基本概念;最大流最小割定理;求最大流的標(biāo)號算法;最小費 用流問題;最小費用最大流;網(wǎng)絡(luò)流理論的應(yīng)用。主要參考書1 J.A. Bondy and U.S. Murty, Graph theory with applications, 1976, 有中譯本(吳望名等譯 。 2 B.Bollobas, Modern graph theory (現(xiàn)代圖論 ,科學(xué)出版社, 2001。3 蔣長浩,圖論與網(wǎng)絡(luò)流,中國林業(yè)出版社, 2001。4 田豐,馬仲蕃,圖與網(wǎng)絡(luò)流理論,科學(xué)出版社, 1987。5 徐俊明,圖論及其應(yīng)用,中國科技大學(xué)出版社, 1998。6 王樹禾,圖

4、論及其算法,中國科技大學(xué)出版社, 1994。7 殷劍宏,吳開亞,圖論及其算法,中國科技大學(xué)出版社, 2003?？己朔绞?:平時成績+期末閉卷筆試第一章 圖的基本概念§1.1 圖的基本概念1. 圖 (graph:一集元素及它們之間的某種關(guān)系。具體地說,圖是一個二元組 , (E V ,其中 集合 V 稱為 頂點集 ,集合 E 是 V V ×的一個子集(無序?qū)?元素可重復(fù) ,稱為 邊集 。 例 1.1.1 , (E V G =,其中2. 圖的圖示通常, 圖的頂點可用平面上的一個點來表示, 邊可用平面上的線段來表示 (直的或曲的 。 這樣畫出的平面圖形稱為圖的圖示。 注 :(1由于

5、表示頂點的平面點的位置的任意性,同一個圖可以畫出形狀迥異的很多圖示。 比如下圖是例 1.1中圖的另一個圖示: (2圖的圖示直觀易懂,因此以后一般說到一個圖,我們總是畫出它的一個圖示來表示。3. 一些概念和術(shù)語(1 點與邊的關(guān)聯(lián) (incident(2 點與點的相鄰(adjacent (3 邊與邊的相鄰(4 邊的端點(end vertices(5 環(huán)邊 (loop(6 重邊 (multiedge(7 簡單圖 (simple graph(8 完全圖 (complete graph(9 圖的頂點數(shù)(圖的階 、邊數(shù) (10 頂點 v 的度 (degree:d (v = 頂點 v 所關(guān)聯(lián)的邊的數(shù)目(環(huán)邊

6、計兩次 。(11 圖 G 的最大度:(| (max (G V v v d G G =圖 G 的最小度:(| (min (G V v v d G G =(12正則圖 (regular graph:每個頂點的度都相等的圖。(13 圖的補(bǔ)圖 (complement:設(shè) G 是一個圖, 以 (G V 為頂點集, 以 ( , (| , (G E y x y x 為邊集的圖稱為 G 的補(bǔ)圖,記為 。2 ( (=G V v v d證明:按每個頂點的度來計數(shù)邊,每條邊恰數(shù)了兩次。推論 1.1.1 任何圖中,奇度頂點的個數(shù)總是偶數(shù)(包括 0 。4. 子圖子圖 (subgraph:如果 ( (G V H V 且

7、( (G E H E ,則稱圖 H 是 G 的子圖,記為 G H 。生成子圖 (spanning subgraph: 若 H 是 G 的子圖且 ( ( V H V G =,則稱 H 是 G 的生成子圖。 點導(dǎo)出子圖 (induced subgraph:設(shè) (G V V ,以 V 為頂點集,以兩端點均在 V 中的邊 的全體為邊集所組成的子圖,稱為 G 的由頂點集 V 導(dǎo)出的子圖,簡稱為 G 的點導(dǎo)出子圖, 記為 V G .邊導(dǎo)出子圖 (edge-induced subgraph:設(shè) (G E E ,以 E 為頂點集,以兩端點均在 E 中 的邊的全體為邊集所組成的子圖, 稱為 G 的由邊集 E 導(dǎo)

8、出的子圖, 簡稱為 G 的邊導(dǎo)出子圖, 記為 E G .5. 路和圈途徑 (walk:圖 G 中一個點邊交替出現(xiàn)的序列 k k i i i i i i v e e v e v w L 2110=。跡 (trail:邊不重的途徑。路 (path: 頂點不重復(fù)的跡。(注:簡單圖中的路可以完全用頂點來表示, k i i i v v v P L 10=閉途徑 (closed walk :起點和終點相同的途徑。閉跡 (closed trail:起點和終點相同的跡,也稱為回路(circuit .圈 (cycle: 起點和終點相同的路。注:(1途徑(閉途徑 、跡(閉跡 、路(圈上所含的邊的個數(shù)稱為它的 長度

9、 。(2簡單圖 G 中長度為奇數(shù)和偶數(shù)的圈分別稱為 奇圈 (odd cycle和 偶圈 (even cycle。(3 對任意 (, G V y x , 從 x 到 y 的具有最小長度的路稱為 x 到 y 的 最短路 (shortest path , 其長度稱為 x 到 y 的 距離 (distance,記為 , (y x d G 。(4圖 G 的直徑 (diameter: (, | , (maxG V y x y x d D G =.(5簡單圖 G 中最短圈的長度稱為圖 G 的 圍長 (girth,最長圈的長度稱為圖 G 的 周長 (circumference。例 1.1.2 設(shè) G 是一個簡

10、單圖,若 2 (G ,則 G 中必含有圈。證明:設(shè) G 中的最長路為 k v v v P L 10=。因 2 (0v d ,故存在與 1v 相異的頂點 v 與 0v 相 鄰。若 P v ,則得到比 P 更長的路,這與 P 的取法矛盾。因此必定 P v ,從而 G 中有 圈。證畢。例 1.1.3 設(shè) G 是簡單圖,若 3 (G , 則 G 必有偶圈。證明:設(shè) k v v v P L 10=是 G 的最長路。因為 3 (0v d , 所以存在兩個與 1v 相異的頂點 v v , 與 0v 相鄰。 v v , 必都在路 P 上, 否則會得到比 P 更長的路。無妨設(shè) (, , j i v v v v

11、j i <=。若 j i , 中有奇數(shù),比如 i 是奇數(shù),則路 P 上 0v 到 i v 的一段與邊 i v v 0構(gòu)成一個偶圈; 若 j i , 都是偶數(shù),則路 P 上 i v 到 j v 的一段與邊 i v v 0及 j v v 0構(gòu)成一個偶圈。證畢。 例 1.1.4設(shè) G 是簡單圖,若 3 (G , 則 G 中各個圈長的最大公因數(shù)是 1或 2。證明:由上例知, G 中有長分別為 1, 1+j i 和 2+i j 的圈。若 1, 1+j i , 2+i j 三 數(shù)有公因數(shù) 2>m , 則 (|j i m , 于是 2|m , 這是不可能的。 因此 1, 1+j i , 2+i

12、j 三數(shù)的公因數(shù)必不超過 2。從而各個圈長的最大公因數(shù)是 1或 2。證畢。6. 二部圖二部圖 (bipartite graph:若圖 G 的頂點集可劃分為兩個非空子集 X 和 Y ,使得任一條邊都 有一個端點在 X 中, 另一個端點在 Y 中, 則稱 G 為二部圖 (或偶圖 , 記為 G = , (E Y X U , , (Y X 稱為 G 的一個劃分。完全二部圖 (complete bipartite graph:在二部圖 , (E Y X G U =中,若 X 的每個頂點與 Y 的每個頂點有邊連接,則稱 G 為完全二部圖;若 m X =|, n Y =|,則記此完全二部圖為 n m K ,

13、 。定理 1.1.2一個圖是二部圖當(dāng)且僅當(dāng)它不含奇圈。證明: 必要性 :設(shè) 010v v v v C k L =是二部圖 , (E Y X G U =的一個圈。無妨設(shè) X v 0, 由二部圖的定義知, Y v 1, X v 2, L ,一般地, X v i 2, Y v i +12, (L , 1, 0=i 。 又因 X v 0,故 Y v k ,因而 k 是奇數(shù)。注意到圈 C 上共有 1+k 條邊,因此是偶圈。 充分性 :設(shè) G 不含奇圈。取 (G V u ,令 , (| (odd v u d G V v X =, , (| (even v u d G V v Y =。任取一條邊 21v v

14、 e =,欲證 21, v v 分屬于 X 和 Y 。設(shè) P , Q 分別是 u 到 21, v v 的最短路。 (1如果 12v v Q P +=或 21v v P Q +=,則 21, v v 到 u 的距離奇偶性相反, 21, v v 分屬于 X 和 Y 。(2否則,設(shè) u 是 P 與 Q 的最后一個公共頂點,因 P 的 , (u u 段和 Q 的 , (u u 段都是 u 到 u 的最短路,故這兩段長度相等。假如 P , Q 的奇偶性相同, 則 P 的 , (1v u 段和 Q 的 , (2v u 段奇偶性相同, 這兩段與邊 e 構(gòu)成一個奇圈,與定理條件矛盾。可見 P , Q 的奇偶性

15、不同,從而 21, v v 分屬于 X 和 Y 。這便證明了 G 是一個二部圖。 證畢。 7. 連通性圖中兩點的連通 :如果在圖 G 中 u , v 兩點有路相通,則稱頂點 u , v 在圖 G 中連通。 連通圖 (connected graph :圖 G 中任二頂點都連通。圖的連通分支 (connected branch, component :若圖 G 的頂點集 V (G 可劃分為若干非空子集V V V , , , 21L , 使得兩頂點屬于同一子集當(dāng)且僅當(dāng)它們在 G 中連通, 則稱每個子圖 i V G 為圖 G 的一個連通分支(, , 2, 1L =i 。 注 :(1圖 G 的連通分支是

16、 G 的一個極大連通子圖。 (2圖 G 連通當(dāng)且僅當(dāng) 1=。例 1.1.5設(shè)有 2n 個電話交換臺, 每個臺與至少 n 個臺有直通線路, 則該交換系統(tǒng)中任二臺均 可實現(xiàn)通話。證明:構(gòu)造圖 G 如下:以交換臺作為頂點,兩頂點間連邊當(dāng)且僅當(dāng)對應(yīng)的兩臺間有直通線 路。問題化為:已知圖 G 有 2n 個頂點,且 n G (,求證 G 連通。事實上,假如 G 不連通,則至少有一個連通分支的頂點數(shù)不超過 n 。在此連通分支中, 頂點的度至多是 1n 。這與 n G (矛盾。證畢。 例 1.1.6若圖中只有兩個奇度頂點,則它們必連通。證明:用反證法。假如 u 與 v 不連通,則它們必分屬于不同的連通分支。將

17、每個分支看成一 個圖時,其中只有一個奇度頂點。這與推論 1.1.1矛盾。證畢。由前已知, 同一個圖有不同形狀的圖示。 反過來, 兩個不同的圖也可以有形狀相同的圖 示。比如: 可見 1G 和 2G 的頂點及邊之間都一一對應(yīng), 且連接關(guān)系完全相同, 只是頂點和邊的名稱 不同而已。這樣的兩個圖稱為是 同構(gòu)的 (isomorphic。從數(shù)學(xué)上看,同構(gòu)的兩個圖,其頂點間可建立一一對應(yīng),邊之間也能建立一一對應(yīng),且 若一圖的兩點間有邊,則在另一圖中對應(yīng)的兩點間有對應(yīng)的邊。嚴(yán)格的數(shù)學(xué)定義如下。 定義 1.1.1 兩個圖 (, (G E G V G =與 (, (H E H V H =,如果存在兩個一一映射:(

18、 (:H V G V , ( (:H E G E ,使得對任意 ( , (G E v u e =,都有 (,(HE v u 且 = (e (, (v u ,則稱圖 G 與 H 同構(gòu)。記為 H G . 9. 圖的矩陣表示 (1關(guān)聯(lián)矩陣= (G M m m m m m m m m m e e e v v v L L L L L L L L M 2122221112112121, 其中 ij m 表示頂點 i v 與邊 j e 關(guān)聯(lián)的次數(shù)。 (2鄰接矩陣= (G A v v v a a a a a a a a a v v v v v v L L L L L L L L M 2122221112112

19、121, 其中 ij a 表示頂點 i v 與 j v 相鄰的次數(shù)。 =021010011 (G M , =110 (G A 。 可見:(1 M(G和 A(G的元素是 0, 1或 2。若 G 是簡單圖,則只有 0和 1;(2 A(G是對稱矩陣;(3 M(G中每列之和=2; M(G中第 i 行之和=v i 的度;若 G 中無環(huán)邊,則 A(G中第 i 行(列之和=M(G中第 i 行之和=v i 的度。 圖在計算機(jī)上處理時, 可以以關(guān)聯(lián)矩陣或鄰接矩陣的形式存于計算機(jī)中。 因鄰接矩陣比 關(guān)聯(lián)矩陣小又是對稱矩陣,故通常使用鄰接矩陣的上三角部分。§1.2 最短路問題一、賦權(quán)圖對圖 G 的每條邊

20、e ,賦以一個實數(shù) w (e ,稱為邊 e 的權(quán)。每個邊都賦有權(quán)的圖稱為賦權(quán)圖。權(quán)在不同的問題中會有不同的含義。 例如交通網(wǎng)絡(luò)中, 權(quán)可能表示運費、 里程或道路的 造價等。設(shè) H 是賦權(quán)圖 G 的一個子圖, H 的權(quán)定義為 (H W =( (H E e e w ,特別地,對 G 中一條路 P , P 的權(quán)為 (P W =( (P E e e w 。二、 最短路問題給定賦權(quán)圖 G 及 G 中兩點 u , v ,求 u 到 v 的具有最小權(quán)的路(稱為 u 到 v 的最短路 。 注 :賦權(quán)圖中路的權(quán)也稱為路的長,最短 (u , v 路的長也稱為 u , v 間的距離,記為 d (u , v 。 最短

21、路問題是一個優(yōu)化問題, 屬于網(wǎng)絡(luò)優(yōu)化和組合優(yōu)化的范疇。 對這種優(yōu)化問題的解答 一般是一個算法。最短路問題有很多算法,其中最基本的一個是 Dijkstra 算法。三、 Dijkstra 算法 1. 算法思想若路 k k u u u u P 110=L 是從 0u 到 k u 的最短路,則 110=k u u u P L 必是 0u 到 1k u 的最 短路?；谶@一原理,算法由近及遠(yuǎn)地逐次求出 0u 到 其它各點 的最短路。下面通過例子說明具體做法。 (1令 00u S =, 00S V =,求 0u 到 0中最近點的最短路,結(jié)果找到 1u 。(2令 :100u S S U =, 00S V =

22、,求 0u 到 0中最近點的最短路。此時除了考慮 0u 到0的直接連邊外,還要考慮 0u 通過 1u 向 0的連邊,即選取 0中一點 u 使得, ( , (min , (0, 000v u w u u d u u d v S u +=。 (*結(jié)果找到 2u 。一般地,若 , , , 10k k u u u S L =以及相應(yīng)的最短路已找到。則可應(yīng)用 (*式來選取新的u ,獲得 0u 到 u 的最短路。2.算法實現(xiàn)-標(biāo)號法 標(biāo)號方法:初始時, 0: (0=u l , =: (v l , (0u v 。然后算法逐步修改 中頂點的標(biāo)號。 第 i 步時, (,( (, (min: (i i i v v

23、 u w u l v l v l +=。Dijkstra 算法:Step 1. Let 0: (0=u l , =: (v l ,(0u v , :00u S = and 0:=i 。 Step 2. for every i v , ( (, (min: (v u w u l v l v l i i +=。 Take i v 0 such that( (0v l v l iv =。 Denote the vertex 0v by 1+i u , let 11+=i i i u S S U 。Step 3. if 1=i , then stop, else, 1:+=i i , go to st

24、ep 2. 3. 算法有效性一個圖論算法稱為是有效算法(或好算法 ,如果在任何圖上施行這個算法所需要的計 算量(時間復(fù)雜性都可由 和 的一個多項式為其上界。 Dijkstra 算法是好算法。它的計 算量為 (2O 。全部迭代過程需要做21(次加法和 1(次比較。(step2中第 1式需要 1i 次加法, 1i 次比較。第 2式需要 1i 次比較。而=+=1 2( 1( 1(1L i i 21( 。§1.3 樹及其性質(zhì)不含圈的圖稱為森林 , 不含圈的連通圖稱為 樹 (tree 。 定理 1.3.1 下列命題等價: (1 G 是樹;(2 G 中無環(huán)邊且任二頂點之間有且僅有一條路; (3

25、G 中無圈且 1=; (4 G 連通且 1=;(5 G 連通且對任何 (G E e , e G 不連通; (6 G 無圈且對任何 (E e , e G +恰有一個圈。 證明:(1 (2G 是樹 G 連通 (, G V v u ,存在路 , (v u P 。若還存在一條路 , (v u P , (v u P ,則必存在 w , w 是路 P 與 P 除了 v 之外最后一個 公共頂點。 P 的 , (v w 段與 P 的 , (v w 段構(gòu)成圈, 這與 G 是樹矛盾。 故只存在唯一的 , (v u 路。(2 (3若 G 有圈,則此圈上任二頂點間有兩條不同的路,與前提條件矛盾。 下面用歸納法證明 1

26、=。1=時, 0=,結(jié)論真。假設(shè) k 時結(jié)論真,我們來證明當(dāng) 1+=k 時,也有 1=成立。當(dāng) 1+=k 時,任取 (, G V v u ?？紤]圖 uv G G =,因 G 中 u 、 v 間只有一條路, 即邊 uv ,故 G 不連通且只有兩個連通分支,設(shè)為 21, G G 。注意到 21, G G 分別都連通且任二 頂點間只有一條路,由歸納法假設(shè), 1 ( (11=G G , 1 ( (22=G G 。因此1 (1 1 ( 1 (1 ( ( (2121=+=+=G G G G G G 。歸納法完成。 (3 (4用反證法。若 G 不連通,設(shè) w G G G , , , 21L 是其連通分支(2

27、w ,則 1=i i (因i G 是 連 通 無 圈 圖 , 由 已 證 明 的 (1和 (2知 , 對 每 個 i G , (3 成 立 。 這 樣 ,w w wi i w i i =11,這與 1=矛盾。(4 (521 ( (=G e G ,但每個連通圖必滿足 1(見下列命題 ,故圖 e G 不連通。命題 若圖 H 連通,則 1 ( (H H 。證明:對 做數(shù)學(xué)歸納法。2, 1=時, 1顯然成立。假設(shè) k 的連通圖都 1。對于 1+=k 的連通圖 H ,任取 (H V v ,考慮 v H 。若 v H 連通,則由歸納假設(shè), 11 ( (=k v H v H ,而1 (1 1(1 1(1 (

28、 (=+=+H k k v H H 。若 v H 不 連 通 , 設(shè) w H H H , , , 21L 是 其 連 通 分 支 (2w 。 由 歸 納 假 設(shè) , 1 ( (i i H H , (w i , , 2, 1L = 。故w k w v H w H H v H wi i w i i = ( ( ( (11,而 1 (1 1( ( ( (=+=+H k w w k w v H H 。歸納法完成。(5 (6先證 G 中無圈:若 G 中有圈,刪去圈上任一邊仍連通,矛盾。再證 e G +恰含一個圈:因 G 連通且已證 G 無圈,故 G 是樹。由(2 ,任二頂點間僅 有一條路相連,故 e G

29、 +中必有一個含有 e 的圈;另一方面,若 e G +中有兩個圈含有 e , 則 e G +G e =中仍含有一個圈,矛盾。(6 (1只需證 G 連通。任取 (, G V v u ,若 u 、 v 相鄰,則 u 與 v 連通。否則, uv G +恰含 一個圈,故 u 與 v 在 G 中連通。由 u 、 v 的任意性,圖 G 連通。定理證畢。推論 1.3.1 非平凡樹至少含兩個 1度頂點(葉子 。證明:設(shè) T 是一個非平凡樹。因 T 連通,故對每個頂點 i v ,都有 1 (i v d 。若對所有 i v 都有 2 (i v d ,則 2 (1=i i v d 。另一方面, 22 1(22 (1

30、=i i v d 。這兩方面矛盾。故 T 至少有一個 1度頂點,設(shè)為 u 。除此之外,其余 1個頂點的度數(shù)之和 為 32。若這些點的度都大于或等于 2,則其度數(shù)之和 22 1(2=。這與 32矛盾。故除 u 之外 T 還至少有一個度為 1 的頂點。證畢。§1.4 生成樹與最小生成樹一、生成樹(spanning tree定義 1.4.1 設(shè) T 是圖 G 的一個子圖,如果 T 是一棵樹,且 ( (G T =,則稱 T 是 G 的一 個生成樹。定理 1.4.1 每個連通圖都有生成樹。證明:設(shè) G 是一個連通圖。令 G G A =|是 G 的連通子圖且 ( (G G =。易見 A 非 空。

31、 從 A 中取邊數(shù)最少的一個,記為 T 。下證 T 是 G 的生成樹。顯然只需證明 T 是樹即可。事實上,已知 T 連通,下證 T 無圈。若 T 有圈 C ,則去掉 C 上任一條邊 e , e T 仍連通。從而 A e T 。但 e T 比 T 少一條邊,這與 T 的取法矛盾。證畢。推論 1.4.1 若 G 連通,則 1。證明:取 G 的生成樹 T ,則 1 (1 ( ( (=G T T G 。證畢。二、最小生成樹問題問題描述:在賦權(quán)圖 G 中,求權(quán)最小的生成樹。即:求 G 的一棵生成樹 T ,使得=Te T e w T w (min (。 算法:1. Kruskal算法step1. take

32、 (1G E e such that 1:,(min (=i e w e w Ge . Step2. find , , , (211i i e e e G E e L +such that(1 G121, , , , +i i e e e e L does not contain any cycle, and(2 1+i e is the one with minimum weight that meet (1.Step3. if i +1 =1 (G , stop; else, 1:+=i i , go to step2.定理 1.4.2 設(shè) 1 (21, , , G e e e L 是 K

33、ruskal 算法獲得的邊, 則邊導(dǎo)出子圖 G1 (21, , , G e e e L 是 G 的最小生成樹。證明:記 =*T G1 (21, , , G e e e L 。顯然 *T 無圈,因此 *T 是森林。設(shè)它有 w 個連通分支, 則 *( ( ( 1( 1 1( T T w T G G =+=+=。但 *T 是 G 的子圖, 故 ( (*G T =, 于是1 (1 ( (*=T G T 。由定理 1.3.1的(3 , *T 是一棵樹,從而是 G 的一棵生成樹。下證其最優(yōu)性,用反證法。假設(shè) *T 不是最小權(quán)生成樹(下稱最優(yōu)樹 。對 G 的任一棵生成樹 T ,記 , , , |min (1

34、21=e e e e i T f i L 且 T e i 。選取一棵 使 (T f 最大的最優(yōu)樹,記為 T 。 (T 不會是 *T 。設(shè) k T f = (。由 (T f 的定義, 121, , , k e e e L 既在 *T 上也在 T 上, 但 k e 不在 T 上。 因此 k e T +含有一個圈 C 。 C 上必有一條邊 *T e k 。 顯然 k k e e T T += (也是一棵生成樹, 且 ( ( ( (k k e w e w T w T w +=。按 照 算 法 , k e 是 使 Gk e e e , , , 21L 中 無 圈 的 邊 中 權(quán) 最 小 的 。 注 意G

35、kk e e e e , , , , 121L 是 T 的子圖,也無圈。故由算法規(guī)則知: ( (k k e w e w 。由前式, ( (T w T w 這說明 T 也是最優(yōu)樹,但 ( (T f k T f =>,這與 T 的取法矛盾。證畢。 例 1.4.1 欲建設(shè)一個連接 5個城市的光纖通信網(wǎng)絡(luò)。各城市間線路的造價如圖所示,求一個 2. Prim 算法 step1. 任取 (0G V v ,令 00v S =, 00 (S G V =, 0:=i 。step2. 求 i S 到 i 間權(quán)最小的邊 i e ,設(shè) i e 的屬于 i 的端點為 i v ,令 :1i i i v S S U =+, 11 (+=i i S G V 。Step3. 若 1=i ,停止;否則,令 1:+=i i ,繼續(xù) step2。習(xí)題一1. 證明:2。2. 如果 <, 2,則連通圖 G 至少有兩個 1度頂點。3. 如果 1+=,則存在 (G V v 使得 3 (v d 。4. 在 k 度正則圖 G 中, 2(mod0k 。5. 晚會上大家握手言歡。證明:握過