Week 10

A flow network is a specific kind of graph that has a node that is the source of some sort of traffic, directed edges indicating the maximum amount of allowed traffic between two nodes, and a node that is the destination of all of the traffic. The amount of traffic flow coming from the source node must equal the amount of traffic flow leaving the graph through the destination node. Additionally, the amount of flow into and out of any node must be conserved such that the amount of flow into a node is equal to the flow out of a node.

Given a problem that can be modeled with a network flow, we typically want to find the maximum flow of the graph. We use the Ford-Fulkerson algorithm to find the maximum flow of a network flow graph. It uses a residual graph and a growing set of examined nodes to progress toward the optimal solution of the network flow graph.

When finding the maximum flow of a network flow graph, it is useful to find the bottleneck of the graph to know the best-case of flow. This is done by considering the nodes in the graph to be separated into two major groups, called a cut, and summing up all of the edge capacities between the two groups. Since the flow has to go through these edges (having no other path to the destination node), we know that it is a best-case scenario that the flow of the graph be equal to the minimum possible capacity through any cut.