关于网络构建的最大通过能力问题
杨健 （贵州民族大学 理学院，贵州 贵阳 550025）
【摘 要】摘 要：给定一个有向网络D以及关于弧上的容量函数和构建费用函数，要在网络D中寻找一个子网络D'，使得D'的总构建费用不超过费用预算，且要求网络D'中从始发点到目的点的通过能力达到最大.这就是最大通过能力问题，本论文讨论了该问题的两种特殊情形，即最大通过能力的路问题和容量相等的最大通过能力问题，分别给出多项式算法，并分析算法的时间复杂度. 【期刊名称】赤峰学院学报（自然科学版） 【年(卷),期】2015(000)013 【总页数】2
【关键词】最大通过能力问题；多项式算法；时间复杂度 【文献来源】
https://www.zhangqiaokeyan.com/academic-journal-cn_journal-chifeng-university-
natural-science-edition_thesis/0201248848204.html
1 问题的现实背景及其模型
最大通过能力问题在社会生产生活中有着非常广泛的应用，特别是在工程建设中，比如在铺设石油管道，架设输电网络，构建通讯线路等情况时，常常会遇到这样的问题，由于实际的需要，我们要计划构建从地点s到地点t的连通网络，有许多构建方案是可行的，但由于受到预算资金的制约，要求我们必须要在现有的预算下构建一个性能最好的连通网络，这里所谓的性能是指网络中从地点s到地点t所能承载的最大输送规模，这些类似的问题可以抽象为如下最大通过能力问题：
定义1给定一个双赋权网络D=（V，A;c，w;B;s，t)，V和A分别是网络D的
顶点集合和弧集合，c和w分别是关于弧的容量函数和构建费用函数，B是给定的构建预算，s是给定的始发点，t是目的点.要求在网络D中寻找一个子网络D'，使得D'的总构建费用，而从始发点s到目的点t的最大通过能力，即网络D'中从始发点s到目的点t的最大流量，达到最大.
最大通过能力问题是强NP-完备的，它不存在拟多项式算法，下面仅讨论该问题的两种特殊情形，它们仍然有非常好的现实意义，针对这两个问题，分别给出多项式算法.
2 最大通过能力的路问题
定义2最大通过能力的路问题是指，给定网络D=（V，A;c，w;B;s，t)，其中V和A分别是网络D的顶点集合和弧集合，c是弧上的容量函数，w是弧上的构建费用函数，B是给定的构建预算，s和t分别是始发点和目的点.要求在网络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).
证明 设算法在循环到第k次循环时得到输出解pk，当前网络为Dk，而在第k+1次循环时算法终止，这时路pk的构建费用w（pk)≤B.若pk不是问题的最优解，且设p为最优解，则w（pk)≤B，且有c（pk)＜c（p).由于算法在第k次循环的Step4中删除了Dk中容量小于或等于c（pk)的弧，得到一个新的网络Dk+1，而路p上的弧容量都不小于c（p)，故路p上的所有弧必存在新的网络Dk+1中，因w（p)≤B，所以算法在k+1步不会终止，这与假设矛盾，故算法1所求得的解是最优解.下面来分析算法的时间复杂度，由于在算法的每次循环中，都会在当前的网络中删除一些弧，得到一个新的网络进入下次循环，如果每次都只删除一条弧，最后网络中不含弧，算法终止，那么算法最多循环m+1次，而每次循环要调用Dijkstra算法，由于Dijkstra算法的时间复杂度是O（n2)，所以最短路迭代算法的时间复杂度是O（mn2)，证毕.
3容量相等的最大通过能力问题
对于最大通过能力问题，甚至当所有弧的构建费用全为1时，它仍然是强NP-完备的.在这里我们考虑所有弧的容量都相等时的情形，这个问题在现实中仍然具有广泛的应用性，例如，我们在架设电网时，常常利用的是同一种规格的电缆；我们在铺设管道时，用的也可能是同种管道.因此，解决这个问题对我们的
实际应用还是很有帮助的.下面我们来讨论这种情形.
设D*是关于网络D的最大通过能力问题的一个最优解，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的弧，就得到一些弧不交的路，并且因为是最大整数流，所以这些弧不交的路是在的限制下的最大条数.下面我们给出的算法是在限制性最大流问题的连续最短路算法[5]基础上设计的多项式算法. 算法2修正的连续最短路算法 输入：网络D=（V，A;c，w;B;s，t). 输出：通过能力最大的子网络. Begin
Step1.令网络D中所有弧的容量为1，令每条弧上单位流量的费用等于该条弧上的构建费用，流的总费用限制为B，构造一个新网络D'=（V，A;1，w;B;s，t).
Step2.利用连续最短路算法求解新网络D'中从s到t的限制性整数最大流f： （1）初始时，令流f=0，π=0是一个关于顶点的函数（称为点势），k表示所选s-t路的条数（初始时为0），构造网络D'关于初始流f的剩余网络D'（f)，计算剩余网络中关于弧的减小费用函数wπ；
（2）当B＞-π（t)时，执行以下循环：在剩余网络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修正的连续最短路算法能找到弧容量相等的最大通过能力问题的最优解，并且时间复杂度为O（mn2).
证明 由定理2可知，算法能够找出弧容量相等的最大通过能力问题的最优解.下面分析算法的时间复杂度，从算法中看到，时间复杂度主要由Step2决定，这一步调用了一次连续最短路算法，在每次连续最短路算法的循环过程中，都增广一个单位的流，可见Step2最多进行了m步循环，每步循环都调用了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. 【文献来源】
https://www.zhangqiaokeyan.com/academic-journal-cn_journal-chifeng-university-
natural-science-edition_thesis/0201248848204.html
关于网络构建的最大通过能力问题
