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.

The Bipartite Matching Problem