On the relation of max-flow to min-cut for generalized networks

A generalized network is characterized by arc multipliers that are positive and not all equal to one. The flow transmitted across an arc is modified by a gain/loss factor before it reaches the end node. Several maximum flow algorithms have been constructed for generalized networks without fully exploiting the underlying network structure. This paper is aimed at closing the gap. Ford and Fulkerson’s max-flow min-cut theorem is extended to cover generalized networks. Existence of a minimal cut, the optimal flow routing in the subnetworks separated by the cut and the effect of the theorem on future research are discussed.