黃蘭　魯珍珍　尹倩華　張莉茜

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

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

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

1 引 言

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

相關(guān)概念：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Prim算法的基本思想：

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

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

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

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

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

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

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

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

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

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

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

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

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

2。6 其他算法

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

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

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

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

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

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

2。6。3 求解TSP問(wèn)題的Christofides近似算法

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

3 小 結(jié)

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

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