Chapter 7: Network Flow

Graphs are often useful in modeling transportation networks, where the edges carry traffic and each node acts as a switch that passes traffic between different edges. This system can thought of as a highway system where the edges represent the highways themselves, and nodes represent the interchanges between the highways, or also as a fluid network where the edges are pipes that carry fluid and the nodes are junctures where pipes meet. Networks of this type have several main key characteristics: capacities for each edge, destination(sink) nodes for the graph, and the traffic itself that is transmitted along the edges. In this chapter we will consider flow networks, where the traffic is considered as flow - 'an abstract entity that is generated at source nodes, transmitted across edges, and absorbed at sink nodes'. A flow network is a directed graph where each edge has a non-negative capacity, and there is a single source node and sink node, with all other nodes called internal nodes. With our flow networks, we make three key assumptions: that no edges enter the source node s and no edges leave the sink node t, and that there is at least one edge incident to each node, and that all capacities are integers. 'We say that an s-t flow is a function f that maps each edge e to a nonnegative real number f:E → R+; the value f(e) represents the amount of flow carried by an edge e'. A flow f must satisfy two criteria: for each e in E, the flow is greater than or equal to zero and less than the edge capacity, and that the flow out of s must equal the flow into t. To summarize, the flow on an edge can't exceed the capacity of that edge, and the flow into a node must equal the flow out of the node, with exceptions at the source, and sink node that have no flow in, and no flow out respectively. The value of a flow f, v(f) is defined to be the amount of flow generated at the source. The Maximum-Flow Problem is defined as given a flow network, arrange the traffic so as to make as efficient use as possible of the available capacity. If we use a greedy algorithm to try to solve this problem, we will likely end up with a solution that does not maximize the flow. To avoid this, we will use an approach where we can push flow forward one edges that have leftover capacity, and push backwards on edges that are already carrying flow at max capacity in order to divert it in a different direction. We will use a residual graph for looking at the forward and backward flow. The residual graph will consist of a node set the same as the original graph, but for each edge we will maintain the leftover capacity to push flow forward, and the flow that is already being pushed along the edge as the backwards flow that we can undo. Thus we have twice as many edges as the original graph as we have a forwards and backwards edge for every edge in the original graph. When we look to push flow from s to t, we look for an s-t path that does not visit any node more than once, with a bottleneck value of the minimum residual capacity of any edge on the path. For every edge in the path, if it is a forwards edge we increase the flow by the bottleneck value, otherwise we decrease the flow by the bottleneck value. Any s-t path in the residual graph is known as an augmenting path. 'At every intermediate stage of the Ford-Fulkerson Algorithm, the flow values f(e) and the residual capacities are integers'. Thus, the Ford-Fulkerson Algorithm must terminate in at most C iterations of the While loop, and will run in O(mC) time. This section was somewhat easier to follow having talked about the algorithm in class. I would give this section an 8/10.