Chapter 7

Many problems can evolve from the Bipartite Matching problem, such as the perfect matching problem, the assigning-job-to-machine problem, and what we focus on this chapter-network flow problem.

The section first introduces the maximum-flow problem. A flow network is a graph such that each edge is assigned with a positive number called capacity, a single source node s and sink node t. A flow through a network is a function f:E-R+ (from edges to a positive number, that is the amount of flow), such that f satisfy two properties: capacity condition and conservation condition, to ensure the flow function to physically make sense. The value of a flow is defined as the amount of flow generated at the source. The maximum-flow problem is to find a way to maximum the value of the flow of a given flow network. We first want to try to apply greedy algorithm. But it is not hard to find a counter example of just pushing the flow to the network with greedy algorithm. In fact, we need a more generalized “push”. We not only shall push the flow forwards, but also push the flow backward on edges that are already carrying flow. Because in this way, our network becomes more “flexible”-we can divert the flow to more directions. Using this idea, we define a new and useful term: residual graph, which satisfies the following requirements: the nodes are the same as the original graph; the original edges will have f(e)<ce capacities; the backward edges will have f(e) capacities. Then we define a function, called augment(f,P) to add a new flow to the residual graph and update the residual graph. Provided that the path P can be effectively determined, we now can write down the Ford-Fulkerson Algorithm. One limit of the algorithm is that the capacities as well as the value of flow has to be positive integer. Only in this way, we can assure the termination of the F-F algorithm, which is going to be within C iteration, where C is the total possible flow out of the source. The F-F Algorithm thus has a running time O(mC). I have two comments as to the F-F algorithm, 1, in real life, the reverse flow may not be possible at most of the times; 2, in real life, very possibly, the capacity is not all in integer. But the idea is still very neat. Readability is 7.