第6章圖論模型6.1圖的基本概念與基本定理6.2樹與生成樹6.3最短路徑問題6.4網(wǎng)絡(luò)最大流、最小流問題

6.1圖的基本概念與基本定理

現(xiàn)今的加里寧格勒（位于現(xiàn)俄羅斯西部），在18世紀(jì)稱哥尼斯堡城（下稱哥城），是一座歷史名城，普雷格爾河流經(jīng)哥城，把哥城分為如圖6.1（a）所示的四個區(qū)域：島區(qū)（A）、東區(qū)（B）、南區(qū)（C）、北區(qū)（D），四個區(qū)域通過七個橋互相連接。哥城的居民在沿河散步欣賞景色之余，提出一個問題：能否從一點出發(fā)，走遍七座橋，且通過每座橋恰好一次，最后仍回到起始地點？圖6.1七橋問題

1736年，29歲的Euler通過研究這一問題，向彼得堡科學(xué)院遞交了一份題為《哥尼斯堡的7座橋》的論文（圖論的首篇論文）。論文的開頭是這樣寫的：討論長短大小的幾何學(xué)分支，一直被人們熱心地研究著。盡管如此，至今仍有一個幾乎完全沒有被探索過的分支，萊布尼茲最先提起過它，稱之為“位置的幾何學(xué)”。這個幾何學(xué)分支只討論與位置有關(guān)的關(guān)系，不考慮長短，也不牽涉到量的計算。在論文中，歐拉用他嫻熟的變換技巧，把A、B、C、D四塊區(qū)域抽象為四個點，而每座橋用連接兩點的一條線表示，于是得到圖6.1（b），問題變得清晰且利于思考。正是基于上述基礎(chǔ)，經(jīng)過悉心研究，確立了著名的“一筆畫原理”，從而成功地解決了哥尼斯堡七橋問題。6.1.1圖的定義、頂點的次數(shù)及圖的同構(gòu)

定義6.1有序三元組G=(V,E,ψ)稱為一個圖，其中,V={v1,v2,v3,…,vn}是有窮非空集，稱為頂點集；E稱為邊集，其中的元素叫做邊；ψ是從邊集E到頂點集V中的有序的或無序的元素所對應(yīng)的集合的映射，稱為關(guān)聯(lián)函數(shù)。

注：V中元素可以用不重合的幾何點表示（順序不限）；當(dāng)ψ(e)=uv（或(u,v)）時，u與v之間連線，連線可曲可直，表示邊e，對于有序集合{(u,v)}，則還需要在連線上畫箭頭指向v。下面引入頂點次數(shù)的相關(guān)定義：在無向圖中，與頂點v關(guān)聯(lián)的邊的數(shù)目（環(huán)算兩次）稱為v的次數(shù)，記為d(v)；在有向圖中，從v引出的邊的數(shù)目稱為v的出次，記為d+(v)，而將v引入邊的數(shù)目稱為v的入次，記為d－(v)，且v的次數(shù)d(v)=d+(v)+d－(v)。圖6.5同構(gòu)圖圖6.6非同構(gòu)圖6.1.2路徑與連通的相關(guān)概念

由上一節(jié)定義可以知道，圖主要分為連通圖和無向圖，在無向圖中可以簡單地給出以下定義：圖6.7連通圖和非連通圖

【例6.3】有一種電話交換機(jī)，每個可以同時與n個電話交換機(jī)相連，現(xiàn)有2n個電話交換機(jī)，則其中任意兩個是否可以互相通話？

分析通過上面的學(xué)習(xí)，我們可以將電話交換機(jī)視為圖G的頂點，當(dāng)且僅當(dāng)兩個交換機(jī)有直通線路時，兩個相應(yīng)的頂點連接成邊，問題可以轉(zhuǎn)化為：2n個頂點的簡單圖，每當(dāng)頂點的次數(shù)至少為n時，則G連通?？梢酝ㄟ^反

證法進(jìn)行證明。證明若G不連通，則G至少有兩個分圖，頂點最小的那個分圖的頂點數(shù)至多是n，在此分圖中頂點的次數(shù)最大的是n－1，與G中每頂點次數(shù)至少為n矛盾。

定義6.7起點和終點重合的路徑稱為圈，記為Ck

（其中k為圈所含邊的數(shù)目）；一條路徑（包括圈）所含邊的數(shù)目稱為這條路徑的長度；圈的長度為奇數(shù)的圈稱為奇圈，記為C2k+1，圈的長度為偶數(shù)的圈稱為偶圈，記為C2k；G中頂點u到v的最短路徑的長度，稱為u與v之間的距離，記為d(u，v)。通過以上的定義可以得到二部圖的一個重要判定定理。

定理6.2

G是二部圖的充要條件是G不含奇圈。6.1.3有向圖的連通性

圖6.8給出了半通路（u到v，即圖(a)）、強(qiáng)連通圖（圖(b)）、單向連通圖（圖(c)）、弱連通圖（圖(d)）、不連通圖（圖(e)）。連通圖的類型是根據(jù)連通性的強(qiáng)弱進(jìn)行劃分的，強(qiáng)連通圖的連通性最強(qiáng)，即強(qiáng)連通必然單向連通，單向連通必然是弱連通，反之則不成立。圖6.8有向圖的連通性依據(jù)定義判別有向圖是哪一類連通圖是很復(fù)雜的，因為對于結(jié)點數(shù)n比較大時需要檢查任兩點間的路徑，下面給出一個有效的判別定理。

定理6.3一個有向圖D是強(qiáng)連通的必要條件是它有一條完備回路，一個有向圖是單連通的當(dāng)且僅當(dāng)它有一條完備通路,一個有向圖是弱連通的當(dāng)且僅當(dāng)它有一條完備半通路。定義6.10在有向圖D中，最大的強(qiáng)連通子圖D1稱為D的強(qiáng)連通分圖。

最大的強(qiáng)連通子圖D1是指D1是強(qiáng)連通的子圖，且D中不再有包含D1的強(qiáng)連通子圖。如圖6.9所示的強(qiáng)連通分圖為圖6.9強(qiáng)連通分圖6.1.4圖的矩陣表示

為了便于計算機(jī)進(jìn)行計算與處理，常需要將圖數(shù)字化,即用矩陣表示圖。圖的矩陣表示形式需要依情況而定，本節(jié)介紹比較簡單的鄰接矩陣和關(guān)聯(lián)矩陣。圖6.10例圖觀察后可以發(fā)現(xiàn)無向圖的鄰接矩陣是一個對稱方陣，若G是無向圖，則A的每一行或每一列的元素之和為對應(yīng)頂點的次數(shù)。若G為簡單圖，可知A是一個對稱(0，1)矩陣，且對角線元素均為0。

有向圖的鄰接矩陣：設(shè)D=(V，E)是一個有向圖，

V={v1，v2，…，vn}，則D的鄰接矩陣A=(aij)n×n，其中

aij=m（m為vi指向vj的弧條數(shù)，m可為0）。圖6.11的關(guān)聯(lián)矩陣為

6.2樹與生成樹

樹在圖論中是一個重要概念，它是所有圖中極為簡單又極為重要的一類圖，大部分的圖論問題都可以從樹入手探討，通過樹的性質(zhì)以及相關(guān)成熟的理論進(jìn)行解決。例如在人口稀少或者交通不便的鄉(xiāng)村地區(qū)，鄉(xiāng)村道路可以讓我們在某些村落之間直接通行，但由于人口和交通因素的制約，這些地區(qū)所修建的道路非常少。假如在G地（見圖6.12（a））存在7個鄉(xiāng)村（分別記為v1，v2，…，v7）,有6條道路相連。圖6.12鄉(xiāng)村道路圖及其簡化模型以七個點和六條線段建立模型（見圖6.12（b）），即G地地圖的簡化模型，同時也是樹的基本形式。通過觀察發(fā)現(xiàn)這兩個圖有一個很好的特征：連通（即通過一點可以到達(dá)圖中任意一點）。但當(dāng)?shù)缆愤M(jìn)行維修、洪水泛濫、暴風(fēng)雪肆虐等原因造成某條道路無法通行時就無法到達(dá)每一個鄉(xiāng)村了，在此情況下可以選擇修建其他的道路來彌補(bǔ)缺陷。如何才能保證使用盡可能少的資金去修建出最短的可以通往所有村莊的道路呢？該結(jié)果的一個主要推論：若T是一個階為k+1≥2的樹，則對于T的每個端點v，子圖T-v是一個階為k的樹。這個推論對于樹的相關(guān)結(jié)論的歸納證明是很有用的，可以利用該想法證明樹的另外一個重要性質(zhì),即每個樹的邊數(shù)都比它的階少1。定理6.6每個n階樹的邊數(shù)是n－1。

證明［歸納法］我們對n進(jìn)行歸納。1階樹是唯一的，即平凡樹K1，其邊數(shù)為0。因此對于n=1，結(jié)論正確。假設(shè)對于正整數(shù)k，每個k階樹的邊數(shù)都是k－1，設(shè)T是一個k+1階樹。由定理6.5可知，T至少有兩個端點，設(shè)v是其中一個端點，則T′=T－v是一個階為k的樹。由歸納假設(shè)知，T′的邊數(shù)是m=k－1。由于T恰好比T′多了一條邊，所以T的邊數(shù)為m+1=k，從而結(jié)論成立。

【例6.10】設(shè)T為某個13階樹，其頂點的度為1、2、5。如果T恰好有3個度為2的頂點，那么T有多少個端點?

由于T有3個度為2的頂點，故T就有10個度為1或5的頂點。設(shè)T有x個度為1的端點，則T含有10－x個度為5的頂點。由T為13階樹，據(jù)定理6.6知，T有12條邊。由圖論第一定理可以得到

1×x+2×3×(10－x)=2×12

x=8圖6.13定理6.9證明的圖G的子圖T-v6.2.2生成樹的定義及構(gòu)造方法

定義6.12若T是G的生成子圖，且T是樹，則稱T為G的生成樹（spanningtree）。

定理6.10

G連通的充分條件是G有生成樹。

證明充分性：由生成樹的定義即可得。

必要性：設(shè)G連通，T是G的邊數(shù)最少的連通生成子圖，則T不含圈；否則，任意去掉圈上的一邊，T仍連通，與T是邊數(shù)最少的連通生成子圖矛盾，即可證。樹是無圈的連通圖，可得到求連通圖生成樹的兩種方法：破圈法與避圈法。

破圈法是由連通圖G開始，若G中含圈，則去掉圈上的一邊；若還含有圈，再去掉圈上的邊。不斷重復(fù)，直到不含為止，最終得到的就是G的不含圈的連通生成子圖，即生成樹。圖6.14即可以說明破圈法的過程。圖6.14破圈法生成樹避圈法是在G內(nèi)任意選擇一條邊e1，找一條不與e1形成圈的邊e2，得到{e1，e2}；在余下的邊中找一條不與{e1，

e2}形成圈的e3，得到{e1，e2，e3}。不斷重復(fù)，直到無法繼續(xù)進(jìn)行，得到{e1，e2，…，ei}，即在余下的任何一條邊中都可以找到一條邊與{e1，e2，…，ei}形成圈。圖6.15即可說明避圈法構(gòu)造生成樹的過程。圖6.15避圈法生成樹6.2.3最小生成樹（MST）問題及其算法

再次回到引出樹的概念的例子，其中有7個村和6條公路，因此可以在任意兩個鄉(xiāng)村之間走動。但不可否認(rèn)的是，任意兩個鄉(xiāng)村之間都只有唯一的道路可以通行，例如在v1和v7之間通行，必須要經(jīng)過v2、v4，也就是從v1到v7

是非常不方便的，這是目前無法改變的事實。如果為了減少這段路程，而修建一條新的路直接連接v1和v7，但是這樣做可能要花費一大筆費用，并且需要考慮當(dāng)?shù)氐娜丝诩案鞣N因素。在最初修建公路時，如何確定圖中的六條路就是需要的那幾條呢？首先我們知道，無論如何修建總能形成一個連通圖，而我們的目的就是得到一個由最優(yōu)路徑組成的連通圖。假定我們對于每段路的修建造價都有了一個較為精確的估計（若在兩個村莊之間經(jīng)過造價過高的路段如因特殊的地貌（如流沙、高山等）引起，則不予考慮）。設(shè)G是連通圖并且對它的每條邊都分配一個數(shù)值，該值稱為邊的成本（在圖論中一般被稱為權(quán)值）。圖G的邊e的權(quán)值可記為ω(e)，這樣的圖稱為賦權(quán)圖。對于G的任一子圖H，H的權(quán)值ω(H)定義為其邊的權(quán)值和，即

我們需要找到G的一個生成樹，使其權(quán)值在G的所有生成樹中最小，稱為最小生成樹。在連通賦權(quán)圖中尋找最小生成樹的問題稱為最小生成樹問題。許多的實際問題都可歸結(jié)為如下的數(shù)學(xué)模型：在已知的加權(quán)連通圖上，求權(quán)最小的連通生成子圖，容易知道在權(quán)非負(fù)的情況下，生成樹的邊最小，則權(quán)最小者肯定是生成樹。最小生成樹問題的重要性在于它在計算機(jī)網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、運輸網(wǎng)絡(luò)設(shè)計方面的應(yīng)用。該問題最初是由OtakarBorùvka在1926年明確提出的，問題的提出源于他

在輸電線網(wǎng)絡(luò)的最節(jié)約設(shè)計方面的興趣。Borùvka還給

出了這個問題的第一種解法，在他之前的人類學(xué)家JanCzekanowski在研究分類方案時所產(chǎn)生的想法很接近于最小生成樹問題。

Kruskal算法的基本思路：一個連通賦權(quán)圖G，對于G的生成樹T的第一條邊e1，選擇G的任意權(quán)值最小的邊；對于T的第二條邊e2，在G剩下的邊中選擇權(quán)值最小的邊；對于T的第三條邊e3，在G剩下的邊中選擇權(quán)值最小的邊，且不與前面所選的邊構(gòu)成圈。不斷重復(fù)以上步驟，直至產(chǎn)生一個生成樹。

Kruskal算法步驟：注：Kruskal算法時間復(fù)雜度以O(shè)(mlbm)為界，當(dāng)邊數(shù)較多或是一個完備圖時，m≈n(n－1)/2，則時間復(fù)雜度近似于O(n2lbn)；Prim算法的時間復(fù)雜度為O(n2)。若圖的連通度較高（最高為完備圖）時，則Prim算法較好；圖的連通度較低（m≈O(n)）時，則Kruskal算法更適合。圖6.16給出了如何應(yīng)用Kruskal算法構(gòu)造連通賦權(quán)圖的一個生成樹。圖6.17給出了如何應(yīng)用Prim算法構(gòu)造連通賦權(quán)圖的一個生成樹。圖6.16

Kruskal算法構(gòu)造生成樹圖6.17Prim算法構(gòu)造生成樹6.2.4最小生成樹問題的應(yīng)用及推廣

最小生成樹的理論可以在很多工程、技術(shù)領(lǐng)域中得到應(yīng)用，如在若干城市之間架設(shè)通信線路、供電線路、鋪設(shè)各種管道，要求總的線路長度最短或成本最低；在印制電路板上布線，不允許線路在非結(jié)點上相交，并使設(shè)計的線路最短。在實際應(yīng)用中又提出了最小生成樹問題的各種推廣，其中較典型的問題多是在可行解的結(jié)構(gòu)上增加一些約束條件，主要有以下5類典型問題：

（1）最大生成樹問題。在連通加權(quán)圖中求最大權(quán)的生成樹，僅需按照前面兩種方法由大到小選擇各邊權(quán)值，這樣求最小生成樹的算法即可改為求最大生成樹。（2）容量約束最小生成樹問題。

在信息處理網(wǎng)絡(luò)的設(shè)計過程中需要考慮到這樣的一個問題：已給一個無向圖G=(X，E)，每條邊(x，y)具有費用d(x，y)以及容量c(x，y)，一個頂點為信息接收站。尋求一個生成樹，使所有信息沿樹的邊送到接收站，滿足約束容量，即每邊上所傳的信息量不超過容量且費用最小，稱此樹為容量約束的最小生成樹。

(3)度數(shù)約束生成樹問題。

生成樹在計算機(jī)和通信網(wǎng)絡(luò)中有許多應(yīng)用，其中的大多數(shù)問題對于某些定點的度數(shù)有限制。如一個頂點可以表示一個中央計算設(shè)備，其他頂點表示連接在中央計算設(shè)備上面的各個終端，它們通過電纜與中央設(shè)備連接，如何設(shè)計才能使中央計算設(shè)備與終端連接起來，使用電纜盡可能少的問題，可以利用以上的兩種算法進(jìn)行解決（若只有一個頂點受約束，則容易得到時間多項式算法）。

(4)最佳通信生成樹。

已知一個n個頂點的圖和頂點間的需求r(x，y)，這些可代表電話呼叫。設(shè)計一個生成樹，使得在所有生成樹中通信費用最少。通信費用C(T)的定義為

其中d(x，y)為樹T中x與y之間的長度。

6.3最短路徑問題

在所有圖類問題的最優(yōu)化中，路徑問題是得到最廣泛研究且有了一定成果的問題之一，這類問題經(jīng)常在交通、通信、工程規(guī)劃和決策等方面中遇到，一般的最短路徑問題會在賦權(quán)圖中進(jìn)行討論，本節(jié)僅將傳統(tǒng)的典型算法及相關(guān)應(yīng)用作為這方面的基礎(chǔ),一一向大家說明。6.3.1解最短路徑問題的基本方法

在賦權(quán)圖G=(V，E)中指定的一對頂點vi、vj間眾多的路中尋找一條權(quán)和最小的路，這樣的路稱為從vi到vj的最短路。常見的最短路徑問題有以下幾個類型：①兩指定點間的最短路徑；②圖中各頂點間的最短路徑；③某指定點到其他所有頂點間的最短路徑；④兩個指定頂點之間通過某指定點的最短路徑；⑤第2條、第3條、…、第k條最短路徑等等問題。

1.固定起點的最短路徑問題

此問題的解決有一個較好的方法——1959年由Dijkstra提出的算法。該算法不僅可以求出v1到vn的最短路徑，實際也求出了v1到其余各頂點的最短路徑。

Dijkstra算法的基本思想是生長一棵以v1為根的最短樹，在這棵樹上每一頂點與根之間的路徑皆為最短路徑。最短路徑的生長過程中各頂點將按照距v0的遠(yuǎn)近以及頂點的相鄰關(guān)系，依次加入樹中，先近后遠(yuǎn)，直到所有的頂點均在樹中。

Dijkstra算法是一種標(biāo)號法：給賦權(quán)圖的每一個頂點記一個數(shù)，稱為頂點的標(biāo)號（臨時標(biāo)號，簡稱T標(biāo)號）或固定標(biāo)號（簡稱P標(biāo)號）。T標(biāo)號表示從始頂點到這個頂點的最短路長的上界；P標(biāo)號表示從始頂點到這個頂點的最短路長。圖6.19賦權(quán)圖G解（1）給頂點v1標(biāo)P標(biāo)號0，并用方框把0框起來，給與頂點v1相鄰的頂點v2、v3、v4分別標(biāo)上T標(biāo)號，d(v2)=

l12=2，d(v3)=l13=8，d（v4)=l14=1，其余頂點的T標(biāo)號均為∞，并用表示,如圖6.20(a)所示。圖6.20例6.11求解步驟圖為了便于理解固定標(biāo)號值的取值途徑，將vi到vj的最短路徑中與vj相鄰的前一個頂點，稱為vj的先驅(qū)點（也稱父點）。引入先驅(qū)點的主要用途是便于追蹤最短路徑，同時也給出了各頂點間的最短路徑，例6.11的標(biāo)號過程可以列表，如表6.1所示。

【例6.12】如圖6.21所示賦權(quán)圖，求任意兩頂點間的最短路長。圖6.21賦權(quán)圖圖6.22具有負(fù)權(quán)的有向圖6.3.3最短路徑問題的擴(kuò)展

前面討論的最短路徑的問題，主要集中在由某一點到其他點的路程或費用最小，其權(quán)僅限于各邊上的權(quán)，但在實際問題中會出現(xiàn)路徑的權(quán)是邊上的權(quán)的某個函數(shù)、權(quán)出現(xiàn)在頂點等等，對于這類問題，上面兩小節(jié)的算法不能直接使用，需要進(jìn)行一定的修改。下面討論常見的最可靠線路、最小爬高路徑和帶有頂點附加值的最短路徑問題。圖6.23城市交通系統(tǒng)中最短路徑圖解現(xiàn)將原網(wǎng)絡(luò)圖轉(zhuǎn)化為無頂點附加值的網(wǎng)絡(luò)，如圖6.23(b)所示構(gòu)造一個新網(wǎng)絡(luò)，以舊網(wǎng)絡(luò)的弧Li為頂點，并增加兩個虛擬點代表起點和終點，(Li，Lj)上的權(quán)為ω(Lj)加上轉(zhuǎn)彎附加值（若不轉(zhuǎn)彎，則不加）。L0與起點的所有關(guān)聯(lián)邊相連，其權(quán)為這些邊的權(quán)；L10與終點的所有關(guān)聯(lián)邊相連，其權(quán)為0。通過上述做法，可以將原圖中轉(zhuǎn)彎附加值的最短路徑問題轉(zhuǎn)化為求新圖的最短路徑問題，可用求最短路徑的Dijkstra算法求解，得到從L0到L10的最短路徑為L0←L1←

L2←L5←L8←L9←L10，其權(quán)ω(P)=1+3+（2）+3+（2）+2+3+（2）=13。與圖6.23(c)的P對應(yīng)的原圖6.23(b)的路徑

P*為1→2→3→6→8→7，其權(quán)值為ω(P)=1+（2）+3+（2）

+3+2+（2）+3=13，P與P的權(quán)值相等，P：1→2→3→

6→8→7即原圖帶轉(zhuǎn)彎附加數(shù)的最短路徑。6.3.4最短路徑的應(yīng)用——選址問題及中國郵遞員問題

1.選址問題

選址問題即在服務(wù)項目中為了在某個區(qū)域內(nèi)選定位置，使某一指標(biāo)達(dá)到最優(yōu)值。這類問題在實際生活中很容易碰到，選址問題的數(shù)學(xué)模型依賴于設(shè)施的可能區(qū)域和評判為優(yōu)劣的標(biāo)準(zhǔn)，有許多不同種類的選址問題，此處僅介紹設(shè)施和對象均位于圖的頂點上的單服務(wù)設(shè)施問題。

1)中心問題

公共服務(wù)設(shè)施的選址需要距網(wǎng)絡(luò)中最遠(yuǎn)的被服務(wù)點距離盡可能小，如應(yīng)急服務(wù)設(shè)施、消防中心等。

【例6.15】某城市要建一個急救中心，為城市所屬的7個區(qū)