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 network flow 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.