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.