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”.