混合图网络上的 s-t-流(运筹学与控制论)

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

s-t-Flow on The Network with Hybrid Graph

Under the framework of hybrid graph,the present work firstly defines the road,path,path system,s-t-flows,path s-t-flows and positive path s-t-flows,etc.on the network,and shows the maximum flow on a path system without cycles to be a positive path s-t-flow.Then this paper designs a polynomial time algorithm to decompose an s-t-flow into a path s-t-flow,as well as prove its feasibility and complexity.Propose and prove a theorem that explains the relation between s-t-flow and the s-t-path flow with the decomposition.Propose and prove the s-t-flow conservation rule between the source and the sink.Finally,it further discusses the transformation between the two kinds of flows,and a few of related problems;in particular,it establishes the formulae for their translating and proves that their value does not change when they translate each other.These works improve and extend the previous corresponding works of Ford and Fulkerson(1962),Korte and Vygen(2000) as well as others.