圖論及其算法在數(shù)學(xué)建模中的應(yīng)用

黃蘭　魯珍珍　尹倩華　張莉茜

[摘要]圖論從誕生至今已近300年，但很多問題一直沒有很好地解決。隨著計算機(jī)科學(xué)的發(fā)展，圖論又重新成為了人們研究討論的熱點，這里通過提出實際問題、將問題轉(zhuǎn)化并建立模型的方式簡單介紹圖論及其算法在數(shù)學(xué)建模中的一些應(yīng)用。主要有求最短路徑的Dijkstra算法、Floyd算法，求最佳匹配的匈牙利算法、KM（KuhnMunkres）算法，求最小生成樹的Kruskal算法、Prim算法，求網(wǎng)絡(luò)最大流的FordFulkerson標(biāo)號算法，求解圖的色數(shù)的禁忌搜索算法，求平圖的DMP平面性算法，求最優(yōu)郵路的EdmondsJohnson算法，求解TSP問題的Christofides近似算法等。

[關(guān)鍵詞]圖論；數(shù)學(xué)建模；算法

[基金項目]湖南省大學(xué)生研究性學(xué)習(xí)與創(chuàng)新型實驗計劃項目：圖論及其算法在數(shù)學(xué)建模中的應(yīng)用。

1 引 言

《圖論》起源于在1736年瑞士數(shù)學(xué)家Euler提出的哥尼斯堡七橋問題，它是組合數(shù)學(xué)的一個重要分支。由于圖論研究的是個體及其關(guān)系的學(xué)科，其應(yīng)用領(lǐng)域十分廣闊，不僅局限于數(shù)學(xué)和計算機(jī)科學(xué)，還涵蓋了社會學(xué)、交通管理、電信領(lǐng)域等等。因此圖論在數(shù)學(xué)建模中的應(yīng)用也就非常廣泛，而其算法在求解模型時非常有效。各大數(shù)學(xué)建模競賽賽題有很多與圖論及其算法有重要聯(lián)系，例如歷屆全國數(shù)學(xué)建模競賽：93B：足球隊排名；94A：逢山開路；94B：鎖具裝箱；95B：天車與冶煉爐的作業(yè)調(diào)度；97B：截斷切割的最優(yōu)排列；98B：災(zāi)情巡視的最佳路線；99B：鉆井布局；07B：乘公交，看奧運；2011B：交巡警服務(wù)平臺的設(shè)置與調(diào)度等。此處我們就只著重于闡述圖論在數(shù)學(xué)建模中常見的幾種算法及其算法思想，介紹其具體應(yīng)用，使大家初步領(lǐng)略到圖論的魅力。

相關(guān)概念：

圖：三元有序組G（V（G），E（G），φ（G）），其中V（G）是非空的頂點集，E（G）是不與V（G）相交的邊集，φ（G）是關(guān)聯(lián)函數(shù)，它使G的每條邊對應(yīng)于G的頂點對。

賦權(quán)圖：對G的每條邊e，可以賦一個實數(shù)ω（e），成為e的權(quán)，G連同它邊上的權(quán)成為賦權(quán)圖。

匹配：給定一個二部圖G，M為G邊集的一個子集，如果M滿足當(dāng)中的任意兩條邊都不依附于同一個頂點，則稱M是G的一個匹配。

最佳匹配：如果G為加權(quán)二部圖，則權(quán)值和最大的完備匹配稱為最佳匹配。

最小生成樹：如果加權(quán)連通圖G的子圖T包含G的所有頂點，則稱T是G的生成子圖；若T是樹，則稱T為G的生成樹，并稱其權(quán)值和最小的生成為G的最小生成樹。

2 常用算法及其應(yīng)用

2。1 求最短路徑的Dijkstra算法、Floyd算法

最短路徑問題：設(shè)有一個鐵路系統(tǒng)連接著若干個城市，x0是該系統(tǒng)中的一個固定城市。在該系統(tǒng)中試求從x0到其他各城市的最短路線。

這是圖論中的重要問題，也是數(shù)學(xué)建模中的常見問題，例如1998年全國大學(xué)生數(shù)學(xué)建模競賽B題：災(zāi)情巡視路線中就涉及此類問題。構(gòu)造一個加權(quán)圖G，其頂點xi表示各城市，其邊表示連接各城市的鐵路，邊上的權(quán)表示各鐵路的造價，問題可轉(zhuǎn)化為求圖G中某一點到其他各點最短路（單源性問題），一般用Dijkstra標(biāo)號算法；求非負(fù)賦權(quán)圖上任意兩點間的最短路（多源性問題），一般用Floyd算法。這兩種算法均適用于有向非負(fù)賦權(quán)圖。這兩種算法的主要理論依據(jù)是：若v0，v1，…，vm是圖G中從v0到vm的最短路，則1≤k≤m，v0，v1，…，vk必為G中從v0到vk的最短路。即最短路是一條路，且最短路的任一段也是最短路。

對于單源性問題：假設(shè)在u0到v0的最短路中只取一條，則從u0到其余頂點的最短路將構(gòu)成一棵以u0為根的樹。因此，可采用樹生長的過程來求指定頂點到其余頂點的最短路。這就是Dijkstra標(biāo)號算法的基本思路。

對于多源性問題：直接在圖的帶權(quán)鄰接矩陣中用插入頂點的方法依次構(gòu)造出v個矩陣D1，D2，…，Dv，使最后得到的矩陣Dv成為圖的距離矩陣，距離矩陣中的元素dij表示vi到vj的距離，同時也求出插入點矩陣以便得到兩點間的最短路徑。

2。2 求最佳匹配的匈牙利算法、KM（KuhnMunkres）算法

工作分配問題（一）：給n個工作人員x1，x2，…，xn安排n項工作y1，y2，…，yn。n個工作人員中每個人能勝任一項或幾項工作，但并不是所有工作人員都能從事任何一項工作。 對所有的工作人員能不能都分配一件他所能勝任的工作？

這可轉(zhuǎn)化為求二部圖的完美匹配，一般用匈牙利算法，它的主要理論依據(jù)是下述定理1：

定理1 M是圖G的最大匹配，則G中無M的可增廣路。

工作分配問題（二）：給n個工作人員x1，x2，…，xn安排n項工作y1，y2，…，yn。如果每個工作人員工作效率不同，要求工作分配的同時考慮總效率最高。

我們構(gòu)造一個二部賦權(quán)圖G=（X，Y，E，F(xiàn)），這里X={x1，x2，…，xn}，Y={y1，y2，…，yn}，F(xiàn)（xi，yj）為工作人員xi勝任工作yj時的工作效率。則問題轉(zhuǎn)化為：求二部賦權(quán)圖G的最佳匹配。 如1994年B題：鎖具裝箱[3]?？刹捎肒uhnMunkras算法求解。

在求G的最佳匹配時，總可以假設(shè)G為完備二部賦權(quán)圖。若xi與yj不相鄰，可令F（xi，yj）=0。 同樣地，還可虛設(shè)點x或y，使|X|=|Y|。如此就將G轉(zhuǎn)化為完備二部賦權(quán)圖，而且不會影響結(jié)果。

KuhnMunkras算法流程：（1）初始化可行頂標(biāo)的值；（2）用匈牙利算法尋找完備匹配；（3）若未找到完備匹配則修改可行頂標(biāo)的值；（4）重復(fù)（2）（3）直到找到相等子圖的完備匹配為止。

2。3 求最小生成樹的Kruskal算法、Prim算法

筑路選線問題：欲修筑連接n個城市的鐵路，已知i城與j城之間的鐵路造價為Cij，設(shè)計一個線路圖，使總造價最低。

這類問題很多，如某城市內(nèi)供氣、供水、供電以及通訊等系統(tǒng)的設(shè)計。我們把這類問題稱為最小連接問題，問題轉(zhuǎn)化為在一個連通加權(quán)圖上求權(quán)最小的連通生成子圖，顯然，即求權(quán)最小的生成樹，稱最小生成樹。一般采用Kruskal算法或Prim算法求解。

為使生成樹上邊的權(quán)值之和最小，顯然，其中每一條邊的權(quán)值應(yīng)該盡可能地小。Kruskal算法的做法就是：先構(gòu)造一個只含n個頂點的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止。

Prim算法的基本思想：

從連通網(wǎng)絡(luò)G={V，E}中的某一頂點u0出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊（u0v），將其頂點加入到生成樹的頂點集合U中。

以后每一步從一個頂點在U中，而另一個頂點不在U中的各條邊中選擇權(quán)值最小的邊（u0v），把它的頂點加入到集合U中。如此繼續(xù)下去，直到網(wǎng)絡(luò)中的所有頂點都加入到生成樹頂點集合U中為止。

2。4 求網(wǎng)絡(luò)最大流的FordFulkerson標(biāo)號算法

運輸方案設(shè)計：把商品由產(chǎn)地運往銷地，交通網(wǎng)上每個路段運輸容量給定的條件下，設(shè)計一個運輸方案，使得運輸量最大。這可轉(zhuǎn)化為圖論中的最大流問題。

1956年，F(xiàn)ord和Fulkson給出求最大流的2F算法。

基本思想：從任何一個可行流開始，沿增廣路對流進(jìn)行增廣，直到網(wǎng)絡(luò)中不存在增廣路為止。 問題的關(guān)鍵在于如何有效地找到增廣路，并保證算法在有限次增廣后一定終止。

2。5 求解圖的色數(shù)的禁忌搜索算法

地圖著色問題：把無環(huán)圖G的頂點皆染上顏色，使相鄰頂點顏色不同，且使用的顏色數(shù)最少，則稱這個顏色數(shù)為G的色數(shù)，記為χ（G）。

很多實際問題可轉(zhuǎn)化為地圖著色問題，如：

（1）考試日程問題： 選修課考試安排時，要避免任何一名學(xué)生所選不同課程在同一天考，問最少幾天才能完成？

（2）存儲安全問題： 某公司生產(chǎn)若干種化學(xué)制品，其中有些制品如果放在一起可能發(fā)生化學(xué)反應(yīng)，引起危險。因此公司必須把倉庫分成相互隔離的若干區(qū)。問至少要劃分多少小區(qū)，才可安全存放？

（3）頻率分配問題： 地面上有若干無線電發(fā)射臺，對每臺分配一個頻率供其使用，頻率用自然數(shù)從1起編號，稱為信道號碼，為排除同信道的干擾，要求使用同信道的發(fā)射臺相距必須大于指定的正數(shù)d，問至少要幾個信道？

一般采用禁忌搜索法求解。它是對局部領(lǐng)域搜索的擴(kuò)展。傳統(tǒng)局部領(lǐng)域搜索是基于貪婪思想在當(dāng)前解的領(lǐng)域中進(jìn)行搜索，搜索性能完全依賴于領(lǐng)域結(jié)構(gòu)和初始解的選取，搜索結(jié)果容易陷入局部極小而無法保證全局最優(yōu)。而禁忌搜索從一個初始可行解s開始，通過變換得解的領(lǐng)域函數(shù)V（s），按照某種選擇策略從中選取一個解s*，從s移動到s*，把s*作為一個新解，重新疊代搜索，直到滿足退出機(jī)制。為避免循環(huán)和陷入局部最優(yōu)，禁忌搜索使用禁忌表記錄已經(jīng)到達(dá)的局部最優(yōu)點，也即最近進(jìn)行的移動狀態(tài)。在下一步的搜索中利用規(guī)定的禁忌規(guī)則，在一定搜索次數(shù)內(nèi)不允許選擇這些已被禁的搜索點，從而可以跳出局部最優(yōu)的限制。

2。6 其他算法

2。6。1 求平圖的DMP平面性算法

印刷電路板的設(shè)計問題：當(dāng)設(shè)計和制造印刷電路板時，首先遇到的問題是判定一個給定的電路圖是否能被印刷在同一層板上而使導(dǎo)線不發(fā)生短路？若能，怎樣給出具體的布線方案？

上述問題轉(zhuǎn)化為判定印刷線路版對應(yīng)的圖是否是平面圖？若是，給出它的一個平面表示。DMP平面性算法可判定簡單圖的平面性并給出其平面表示。

2。6。2 求最優(yōu)郵路的EdmondsJohnson算法

中國郵遞員問題：一個郵遞員每次投遞郵件都要走遍他所負(fù)責(zé)的投遞區(qū)域內(nèi)的內(nèi)條街道，完成投遞后回到郵局。他應(yīng)怎樣選擇路線使他所走的總路程最短？

問題轉(zhuǎn)化為在加權(quán)圖中求一條回，經(jīng)過每條邊且權(quán)和最小。EdmondsJohnson算法是在求Euler圖的Euler圈的Fluery算法的基礎(chǔ)上改進(jìn)，先求圖中各奇度點間的最短路徑將圖中奇度點進(jìn)行配對，并加邊使之變成Euler圖，再利用Fluery算法求得其Euler圈，即為所求的最優(yōu)解。

2。6。3 求解TSP問題的Christofides近似算法

旅行售貨商（TSP）：設(shè)v1，v2，…，vn為n個城市，城市之間的路程已知，售貨商從v1出發(fā)，走遍所有城市一次且僅一次回到v1，并使總旅程最短。對于這類問題沒有最優(yōu)解法，只有近似解法：Christofides近似算法。事實上，目前還沒有發(fā)現(xiàn)比Christofides近似算法更接近于最優(yōu)解的有效近似算法。

3 小 結(jié)

圖論提供了一個自然的結(jié)構(gòu)，由此而產(chǎn)生的數(shù)學(xué)模型幾乎適合于所有科學(xué)領(lǐng)域，只要這個領(lǐng)域研究的主題是“對象”和“對象”之間的關(guān)系。而圖論中的相關(guān)算法成了模型求解的重要工具，此處提到的算法并未涵蓋圖論中的所有算法，望讀者通過本文進(jìn)一步認(rèn)識圖論，并能運用圖論中的算法和算法思想解決更多的問題。

[參考文獻(xiàn)]

[1]J。A。Bondy M。S。R。Murty。Graph Theory with Applications[M]。London：Am。Elsvier，New York，1976。

[2]徐俊明。圖論及其應(yīng)用（第三版）[M]。北京：中國科學(xué)技術(shù)大學(xué)出版社，2010。

[3]姜啟源，謝金星，葉俊。數(shù)學(xué)模型（第三版）[M]。北京：高等教育出版社，2003。