有关有向网络容量扩充问题.pdfVIP

高校应用数学学报A 辑 A pp l. M ath. J. Ch inese U n iv. Ser. A 2001, 16 (4) : 471～ 480 　 关于有向网络容量扩充问题 王洪国, 马绍汉 ( 山东大学 计算机系, 山东济南 250100) ( ) 摘　要: 提出了有向网络最大容量的两种计算方法, 将杨超等人 1998 的无向 网络容量扩充问题, 扩展到约束条件含固定费用的有向网络的扩充, 并给出了强多 项式算法. 关键词: 有向网络; 容量扩充; 约束条件; 强多项式算法 中图分类号: T P 3932, O 22 文献标识码: A 　　文章编号:(2001) §1　引　言 在实际应用中, 往往存在已有的网络不能满足工作和生活的需要, 需要进一步提高网络 的能力. 网络能力的提高通常有两种方法: 一是增加新的线路; 二是对已有的线路进行容量 扩充. 这两种方法上实际都是对两点间的容量进行扩充. 容量的扩充又涉及两个方面的内 容: 一是要使网络的容量达到某个需求值, 如何扩充才能使所需投资最小; 二是对给定的投 资 , 如何扩充才能使扩充后网络的容量最大. D [1 ] 中讨论了无向网络中带约束的容量扩充问题. 本文对[1 ]进行了两个方面的推广: 一 是把无向网络的容量扩充推广到有向网络; 二是考虑了包含固定费用的约束条件. §2主要 讨论如何计算有向网络的最大容量; §3主要讨论给定容量求最小投资的有向网络的容量扩 充问题; §4主要讨论给定投资求最大容量的有向网络的容量扩充问题. §2　有向网络的最大容量算法 1　基本概念 设有向网络N = (V ,A , W ) , 其中 V 为结点 v 1, v 2 , …, v n 的集合,A 为结点之间的弧的 收稿日期: ( ) ( ) 基金项目: 国家自然科学基金 ; 国家863306主题项目 863306 060104 ZT © 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 472 高 校 应 用 数 学 学 报A 辑 第16卷第4期 集合, W 是A 上的非负实函数, W 的分量w i, j 表示弧(v i , vj ) 的权或容量. 为简便起见, 以后 以w ij 表示弧(v i , vj ) 的权或容量. 令 是 中的一个特殊结点, 称之为发射点或网络中心, 其它点称为接受点或信息终 s V 端. 设在有向网络 中存在由 到其它每个结点的有向路径, 则由 到终点 的有向路径 N s s vj 的容量 ( ) 定义为