圖論及其算法在數學建模中的應用

黃蘭　魯珍珍　尹倩華　張莉茜

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

[關鍵詞]圖論；數學建模；算法

[基金項目]湖南省大學生研究性學習與創新型實驗計劃項目：圖論及其算法在數學建模中的應用。

1 引 言

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

相關概念：

圖：三元有序組G（V（G），E（G），φ（G）），其中V（G）是非空的頂點集，E（G）是不與V（G）相交的邊集，φ（G）是關聯函數，它使G的每條邊對應于G的頂點對。

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

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

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

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

2 常用算法及其應用

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Prim算法的基本思想：

從連通網絡G={V，E}中的某一頂點u0出發，選擇與它關聯的具有最小權值的邊（u0v），將其頂點加入到生成樹的頂點集合U中。

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

2。4 求網絡最大流的FordFulkerson標號算法

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

1956年，Ford和Fulkson給出求最大流的2F算法。

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

2。5 求解圖的色數的禁忌搜索算法

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

很多實際問題可轉化為地圖著色問題，如：

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

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

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

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

2。6 其他算法

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

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

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

2。6。2 求最優郵路的EdmondsJohnson算法

中國郵遞員問題：一個郵遞員每次投遞郵件都要走遍他所負責的投遞區域內的內條街道，完成投遞后回到郵局。他應怎樣選擇路線使他所走的總路程最短？

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

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

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

3 小 結

圖論提供了一個自然的結構，由此而產生的數學模型幾乎適合于所有科學領域，只要這個領域研究的主題是“對象”和“對象”之間的關系。而圖論中的相關算法成了模型求解的重要工具，此處提到的算法并未涵蓋圖論中的所有算法，望讀者通過本文進一步認識圖論，并能運用圖論中的算法和算法思想解決更多的問題。

[參考文獻]

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

[2]徐俊明。圖論及其應用（第三版）[M]。北京：中國科學技術大學出版社，2010。

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