Feasible flows and possible connections
A. M. Duguid · Pacific Journal of Mathematics · 1961
Introduction.A number of results in the theory of graphs, including Menger's Theorem [2] and Whitney's Theorem ([1], Chapter 20, [3]), have been shown to follow from the max flow-min cut theorem, which was discovered in the course of study of the flow of goods in a transportation network [4].Gale [6] has used the max flow-min cut theorem to prove a generalization of a well known combinatorial lemma of Philip Hall [7], and has used his "feasibility theorem" to obtain interesting combinatorial results 1 .The object of this note is to give a slightly more general form of Gale's theorem, and to use this to prove a theorem about directed graphs, which is of interest in connection with communication networks.Let the network [N, c,c*] be a set N of nodes with a non-negative capacity c(x, y) restricting flow along the directed edge xy, for any x,y e N, and a positive capacity c*(x) restricting the total flows into, or out of, any node x e N. Let S and S r be complementary subsets of N. The upper bound on flow from S to S r imposed by the capacities c and c* will be denoted by k(S, S f ) (and is more precisely defined below).Following Gale, we define a demand d on the network to be a realvalued function on the nodes, and \d(x)\ is to be thought of as the demand for or the supply of some good at x, according as d(x) is positive or negative.The demands d(x) are said to be feasible if there exists a flow in the network, satisfying the capacity restrictions, such that the net flow into (out of) each note is at least (at most) equal to the demand (supply) at that node.Gale's theorem states that a necessary and sufficient condition for the demands d(x) to be feasible is:For every collection S of nodes, the sum of the demands at the nodes of S' must not exceed the capacity k(S, S f ).Gale proves this for the case when there are no capacity restrictions on the nodes, and k(S,S') is thus the sum of the capacities of edges leading from S into S'.We show how Gale's argument may be modified to cover the case when there are capacities on the nodes as well as on the edges.Let A and B be disjoint subsets of the nodes of the directed graph G, containing n and m elements respectively.In § 3 we establish a necessary and sufficient condition that from any r nodes of A there are r disjoint paths to any r nodes of B, for all r S min {n, m}.