混合图网络上的s-t-流

• 作者: 程丛电
• 来源期刊: 重庆师范大学学报（自然科学版）
• 学科: 数学
• 关键词: 混合图 网络 s-t-流 分解 算法 最大流
• 年，卷（期）: 2012,（1）
• 所属期刊栏目: 运筹学与控制论
• 页码范围: 12-17
• 分类号: O221|O157
• 字数: 5636字
• 语种: 中文
• DOI: 50-1165/N.20120115.1809.003

摘要

在混合图的框架下,给出网络上路段、路径、路径系统、路段s-t-流、路径s-t-流及正向路径s-t-流等定义,并表明无圈路径系统上的最大流一定是正向路径s-t-流.设计一个分解路段s-t-流为路径s-t-流的多项式时间的分解算法,并做算法分析证明其可行性与复杂性.给出并证明一个表现分解前后的路段流与路径流之间关系的分解定理.给出并证明关于路段s-t-流的收发点的流量守恒公式.进一步讨论两种流的互相转化及其有关性质,特别地,给出了它们互相转化的方式,并证明了当它们互相转化时流值不变.此项工作改进与推广了Ford和Fulkerson,Korte和Vygen及其它学者关于s-t-流的基础理论工作.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	程丛电	沈阳师范大学数学与系统科学学院	32	61	5.0	7.0