15. Network Flow Problems

• Suppose a directed graph \(G=(V,E)\).

• Each edge has a capacity of \(c_{v,w}\).

• We could consider that the capacity is the amount of water that could flow through a pipe.

Definition

• In a network flow problem, the graph contains two nodes:

  • \(s\) called the source.

  • \(t\) called the sink.

• \(c_{v,w}\) is the maximum unit of “flow” that can pass.

• At any vertex \(v\) (not being \(s\) or \(t\)) the total incoming flow must be equal to the total flow exiting the node.

• The maximum flow problem is to determine the maximum flow amount that can pass from \(s\) to \(t\).

• The following graph has a maximum flow of 5:

Activity

• Do you have any real application of this problem?

• Can you increase the flow in this graph?

• Can you prove it?

• If we cut the graph in two parts:

  • A part containing \(s\) and few nodes.

  • A part containing \(t\) and few nodes.

• The capacity leaving the first part is the maximum flow:

15.1. A simple Maximum-Flow algorithm

• We start with our graph \(G\) and construct a flow graph \(G_f\).

• \(G_f\) is the flow that has been attained at any stage.

• Initially all edges in \(G_f\) has no flow.

• At the end \(G_f\) should contain the maximum flow.

• We also construct \(G_r\), the residual graph.

• \(G_r\) contains for each edge how much flow can be added.

How does it work?

• At each stage, we find a path in \(G_r\) from \(s\) to \(t\).

• The minimum edge on the path is the amount of flow that is added to every edge on the path in \(G_f\).

• We recalculate \(G_r\) and we add an opposite edge with the same capacity.

• When we find no path from \(s\) to \(t\) in \(G_r\) we stop.

Example

• If we apply it to the previous graph.

• Now we find a path:

• And we continue:

• You can see that we changed a previous flow.