The Maximum-Flow Problem and the Ford-Fulkerson Algorithm

In this chapter we are working on modeling transportation networks through graphs. These network models require capacities, source, and sink nodes. Capacities represent how much the edges can carry. Source nodes generate traffic and sink nodes absorb traffic (destination nodes). We also have to represent that traffic that is transmitted across edges.

Flow Networks Traffic across the graph is referred to as flow (generated at sources, transmitted across edges, absorbed at sinks). What is a flow network?

• a connected graph
• each edge has a capacity c_e
• single source node s and single sink node t
• internal nodes are nodes that aren't the source and sink nodes
• no edge leaves the source, no edge leaves the sink
• there is at least one edge incident to each node
• all capacities are integers

What is flow

• our network carrying traffic
• s-t flow is a function, f, that maps each edge to a nonnegative real number
• the value of f(e) is the amount of flow carried by edge e.
• a flow must:
  • Capacity Conditions: for each edge the flow at that edge has to be greater than zero and less than the capacity of that edge
  • Conservation Conditions: the sum of flow values over all edges entering node v has to equal the sum of flow values over all edges leaving node v
  • for every node other than source and sink, the amount of flow entering must equal the amount of flow leaving
• the value of flow v(f) is the amount of flow generated at the source (sum of the flow of each edge out of s)
• we define fⁱⁿ(v) and f<sub>out</sup>(v) as the flow out of the source and the flow into the sink * fⁱⁿ(v) and f<sub>out</sup>(v) must be equal to each other! So what is the problem?? We want to find the flow of maximum possible value. We want to use the available capacity as efficiently as possible. By using cuts (dividing the nodes into two sets) we can put a bound of the maximum possible flow value. The maximum flow value equals the minimum cut. The Algorithm It doesn't work to just find the path with max capacity so we can maximize the flow. We want to push flow forward on edges with leftover capacity and backward on edges already carrying flow to divert it. This is defined as the residual graph that gives us a way to search for forward and backward operations. * the nodes in the residual graph are the same on G * for each edge of G where f(e)<c_e we add the edge to the residual graph with capacity c_e - f(e) (leftover capacity) so we can push the flow forward. These are forward edges
• for each edge where f(e) > 0 we can undo f(e) units of flow by pushing the flow backward so e in the augmented graph has the same capacity as it does in G but its direction is reversed. These are backward edges

The residual graph can has twice as many edges as the graph G because if 0<f(e)<c_e there are both a forward and backward edge. We pass a simple s-t path P to the function augment(f,P) to yield a new flow. It finds the bottleneck residual capacity of any edge in the path. Any s-t path in the residual graph is an augmenting path.

There is a very long proof that describes why f' is a flow in G….I don't really understand it.

So to find the s-t flow in G we use the augment algorithm to compute the augmented graph. This is the Ford-Fulkerson algorithm.

Analysis

Proof by induction that the algorithm maintains certain properties. We denote C to be the sum of the capacities of edges out of s. So the while loop must iterate at most C times. The Ford-Fulkerson algorithm runs at O(m+n) or O(mC) time.

This section was so confusing. I feel like I needed more diagrams or better pictures of how the algorithm works and how the forwards and backwards flows are established. I thought it was so hard to read and didn't like it. Readability: 5.

Maximum Flows and Minimum Cuts in a Network

We show that the flow returned by Ford-Fulkerson algorithm has the max possible value of any flow in G. We use a cut to place an upper bound of the max-flow value. We partition the nodes so that s is in one set and t is in a different set. All of the flow must cross from one set to the other (since the source and sink are in two different sets). The capacity of the cut, we represent as c(A,B), is the sum of the capacities of all edges out of A. This allows us the measure the flow value by watching the amount of flow f sends across a cut. So its the total amount that leaves A minus the total amount that comes back into A. value of any s-t flow is less than or equal to the capacity of any cut A,B (statement 7.8 p 347). This means the value of every flow is upper-bounded by the capacity of every cut. We can compute the s-t cut of minimum capacity in O(m) time. In every flow network the max value of an s-t flow is equal to the minimum capacity of an s-t cut.

We can further analyze this algorithm so that if all capacities in the flow network are integers, then there is a maximum flow f for which every flow value f(e) is an integer (p.351).

This section again was really hard to read. A lot of proofs and really difficult to follow. Felt like it moved really fast and could use more visuals. Readability: 5

The Bipartite Matching Problem