楊?。ㄙF州民族大學　理學院，貴州　貴陽　550025）

關于網絡構建的最大通過能力問題

楊健
（貴州民族大學理學院，貴州貴陽550025）

摘要：給定一個有向網絡D以及關于弧上的容量函數和構建費用函數，要在網絡D中尋找一個子網絡D'，使得D'的總構建費用不超過費用預算，且要求網絡D'中從始發(fā)點到目的點的通過能力達到最大.這就是最大通過能力問題，本論文討論了該問題的兩種特殊情形，即最大通過能力的路問題和容量相等的最大通過能力問題，分別給出多項式算法，并分析算法的時間復雜度.

關鍵詞：最大通過能力問題；多項式算法；時間復雜度

1　問題的現實背景及其模型

最大通過能力問題在社會生產生活中有著非常廣泛的應用，特別是在工程建設中，比如在鋪設石油管道，架設輸電網絡，構建通訊線路等情況時，常常會遇到這樣的問題，由于實際的需要，我們要計劃構建從地點s到地點t的連通網絡，有許多構建方案是可行的，但由于受到預算資金的制約，要求我們必須要在現有的預算下構建一個性能最好的連通網絡，這里所謂的性能是指網絡中從地點s到地點t所能承載的最大輸送規(guī)模，這些類似的問題可以抽象為如下最大通過能力問題：

定義1給定一個雙賦權網絡D=（V，A;c，w;B;s，t)，V和A分別是網絡D的頂點集合和弧集合，c和w分別是關于弧的容量函數和構建費用函數，B是給定的構建預算，s是給定的始發(fā)點，t是目的點.要求在網絡D中尋找一個子網絡D'，使得D'的總構建費用，而從始發(fā)點s到目的點t的最大通過能力，即網絡D'中從始發(fā)點s到目的點t的最大流量，達到最大.

最大通過能力問題是強NP-完備的，它不存在擬多項式算法，下面僅討論該問題的兩種特殊情形，它們仍然有非常好的現實意義，針對這兩個問題，分別給出多項式算法.

2　最大通過能力的路問題

定義2最大通過能力的路問題是指，給定網絡D=（V，A;c，w;B;s，t)，其中V和A分別是網絡D的頂點集合和弧集合，c是弧上的容量函數，w是弧上的構建費用函數，B是給定的構建預算，s和t分別是始發(fā)點和目的點.要求在網絡D中尋找一條s-t路p，使得p的總構建費用B，且路p的通過能力達到最大.

顯然，一條路的通過能力是由路上弧的最小容量來決定的，對此，這里設計一個最短路迭代算法加以解決，并證明這是一個有效算法.

算法1最短路迭代算法

輸入：網絡D=（V，A;c，w;B;s，t).

輸出：一條通過能力最大的路P. Begin

Step1.初始時，令P=?；

Step2.利用Dijkstra算法在網絡D中尋找關于構建費用的s-t最短路，記其為p，其路長為，通過能力為；

Step3.若w（p)＞B或當前網絡中不存在s-t最短路時，則算法終止，輸出當前路P；否則，轉Step4；

Step4.清空P，并將路p存入P中，同時令D?D/{e|c（e) ≤c（p)}，轉Step2.

End

定理1最短路迭代算法是最大通過能力路問題的有效算法，并且它的時間復雜度為O（mn2).

證明設算法在循環(huán)到第k次循環(huán)時得到輸出解pk，當前網絡為Dk，而在第k+1次循環(huán)時算法終止，這時路pk的構建費用w（pk)≤B.若pk不是問題的最優(yōu)解，且設p為最優(yōu)解，則w（pk)≤B，且有c（pk)＜c（p).由于算法在第k次循環(huán)的Step4中刪除了Dk中容量小于或等于c（pk)的弧，得到一個新的網絡Dk+1，而路p上的弧容量都不小于c（p)，故路p上的所有弧必存在新的網絡Dk+1中，因w（p)≤B，所以算法在k+1步不會終止，這與假設矛盾，故算法1所求得的解是最優(yōu)解.下面來分析算法的時間復雜度，由于在算法的每次循環(huán)中，都會在當前的網絡中刪除一些弧，得到一個新的網絡進入下次循環(huán)，如果每次都只刪除一條弧，最后網絡中不含弧，算法終止，那么算法最多循環(huán)m+1次，而每次循環(huán)要調用Dijkstra算法，由于Dijkstra算法的時間復雜度是O（n2)，所以最短路迭代算法的時間復雜度是O（mn2)，證畢.

3容量相等的最大通過能力問題

對于最大通過能力問題，甚至當所有弧的構建費用全為1時，它仍然是強NP-完備的.在這里我們考慮所有弧的容量都相等時的情形，這個問題在現實中仍然具有廣泛的應用性，例如，我們在架設電網時，常常利用的是同一種規(guī)格的電纜；我們在鋪設管道時，用的也可能是同種管道.因此，解決這個問題對我們的實際應用還是很有幫助的.下面我們來討論這種情形.

設D*是關于網絡D的最大通過能力問題的一個最優(yōu)解，k是網絡D中在總構建費用不超過B的情況下，弧不交的s-t路的最大條數，c是網絡D中弧的容量.那么我們有以下定理.

定理2在構建預算B的限制下，網絡D中從s到t的最大通過能力等于k?c.

證明設D*是網絡D在預算限制為B時，通過能力達到最大的子網絡，由于網絡D中所有弧的容量相等，所以D*的通過能力，即其最大流量等于D*中弧不交的s-t路的最大條數k*與弧容量c的乘積.設k是網絡D中在總構建費用不超過B的情況下，弧不交的s-t路的最大條數，顯然有k*≤k，又它們的通過能力為kc，而k*c≥kc，即k*≥k，故k*=k，定理得證.

從上述定理可知，要求在預算限制B下，通過能力最大的子網絡，實際可以轉化為在預算限制B下，求弧不交的s-t路的最大條數，而利用限制性最大流問題的相關算法，后者是容易求出來的.實際上，我們可以令網絡中所有弧的容量為1，其余參數不變，從而得到一個新的網絡，這樣就將后者轉化為求解在費用限制B下新網絡的限制性最大流問題，我們要求得到的最大流是整數流，然后取這個整數流中所有流量為1的弧，就得到一些弧不交的路，并且因為是最大整數流，所以這些弧不交的路是在的限制下的最大條數.下面我們給出的算法是在限制性最大流問題的連續(xù)最短路算法[5]基礎上設計的多項式算法.

算法2修正的連續(xù)最短路算法

輸入：網絡D=（V，A;c，w;B;s，t).

輸出：通過能力最大的子網絡.

Begin

Step1.令網絡D中所有弧的容量為1，令每條弧上單位流量的費用等于該條弧上的構建費用，流的總費用限制為B，構造一個新網絡D'=（V，A;1，w;B;s，t).

Step2.利用連續(xù)最短路算法求解新網絡D'中從s到t的限制性整數最大流f：

（1）初始時，令流f=0，π=0是一個關于頂點的函數（稱為點勢），k表示所選s-t路的條數（初始時為0），構造網絡D'關于初始流f的剩余網絡D'（f)，計算剩余網絡中關于弧的減小費用函數wπ；

（2）當B＞-π（t)時，執(zhí)行以下循環(huán)：在剩余網絡D'（f)中計算從s到所有點關于wπ的最短路長，記為關于頂點的函數d，此時尋找一條最短的s-t路p，在路p上增廣1個單位流，更新原始網絡中的流f，并重新構造剩余網絡，π?π-d，更新減小費用函數wπ，B?B+π（t)，k?k+1；

Step3.在所求得的網絡D'的限制性整數最大流f中，選取流值為1的弧，并輸出.

End

定理3修正的連續(xù)最短路算法能找到弧容量相等的最大通過能力問題的最優(yōu)解，并且時間復雜度為O（mn2).

證明由定理2可知，算法能夠找出弧容量相等的最大通過能力問題的最優(yōu)解.下面分析算法的時間復雜度，從算法中看到，時間復雜度主要由Step2決定，這一步調用了一次連續(xù)最短路算法，在每次連續(xù)最短路算法的循環(huán)過程中，都增廣一個單位的流，可見Step2最多進行了m步循環(huán)，每步循環(huán)都調用了Dijkstra算法，而Dijkstra算法的時間復雜度為O（n2)，因此算法的時間復雜度為O（mn2)，證畢.

4　結論

最大通過能力問題具有很好的現實意義，但該問題是強NP-完備的.本文討論了該問題的兩種同樣具有現實意義的特殊情形，并給出了多項式時間算法，而對該問題的一般情形，有待進一步研究探討，從而設計相關的近似算法.

參考文獻：

〔1〕田豐，馬仲蕃.圖與網絡流理論[M].北京：科學出版社，1985.

〔2〕J.A.Bondy，U.S.R.Murty.Graph Theory with Applications [M].American Elsever，New York，1976.

〔3〕C.H.Papadimitriou，K.Steiglitz.CombinatorialOptimization：Algorithms and Complexity[M].Printice Hall，1982.

〔4〕M.R.Garey，D.S.Johnson.Computer And Intractability，A Guide To The Theory Of NP-Completeness[M]. New York：W.H.Freeman，1979.

〔5〕R.K.Ahuja，J.B.Orlin.A Capacity Scaling Algorithm for the Constrained Maximum Flow Problem[J]. Cambridge，1995.

中圖分類號：O157.5

文獻標識碼：A

文章編號：1673-260X（2015）07-0005-02