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