Maximizing Flow Through a Network With Node and Arc Capacities

In many actual network flow situations, nodes as well as arcs have limited capacities. This paper presents, for such a network, an algorithm for maximizing flow from a source node to a sink node. The algorithm allows us to treat these situations without introducing artificial arcs and nodes, as has been done in the past. Eliminating the artificial arcs and nodes simplifies network analysis since it always results in half as many nodes, as well as less than half as many arcs if the original arcs are undirected. In addition, the following generalization of Ford and Fulkerson’s max-flow, min-cut theorem is presented and proven. Consider two subsets of the nodes, X and Y , whose union is the set of all network nodes and such that the source node is a member of X , and the sink node is a member of Y . Then, forming a cut set separating the source and sink are the nodes in the intersection of X and Y , and the set of all arcs ( i , j ), such that i is a member of X - Y , and j is a member of Y - X . Letting a cut set's value be the sum of the capacities of all its arcs and nodes, it follows that the maximum flow is equal to the minimum value of all cut sets separating the source and sink.