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.

The next goal of this problem is to show that the value of the flow returned by the Ford-Fulkerson Algorithm is the max possible flow for the graph. We will use the idea of a cut to develop a way to place an upper bound on the maximum-flow value. We consider dividing the nodes in the graph into two sets A and B, where the source is in the set A and the sink is in the set B. We say that an s-t cut is a partition (A, B) of the nodes in the graph, with the source in A and the sink in B. The capacity of a cut (A, B) is the sum of the capacities of all edges out of A into B. 'Let f be any s-t flow, and (A, B) any s-t cut. Then v(f) = fout(A)-fin(A). 'Let f be any s-t flow, and (A, B) any s-t cut Then v(f) = fin(B)-fout(B). Let f be any s-t flow, and (A, B) be any s-t cut. Then v(f) is less than or equal to the capacity of (A, B).' Thus the value of every flow is upper-bounded by the capacity of every cut. Thus, we can find any s-t cut, and know that the s-t flow can't be greater than the capacity of that cut. Conversely, if we find a flow value, we know there can't be an s-t cut of a capacity less than that flow value. 'If f is an s-t flow such that there is no s-t path in the residual graph G, then there is an s-t cut in G for which v(f) = capacity (A, B). Consequently, f has the maximum value of any flow in G, and (A, B) has the minimum capacity of any s-t cut in G.' Thus we know that the flow returned by the Ford-Fulkerson Algorithm is a maximum flow, and given the max flow value, we can compute an s-t cut of minimum capacity in O(m) time. For every flow network , the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut. Additionally, if all capacities in the flow network are integers, then there is a max flow f for which every flow value f(e) is an integer. This section was a bit harder to read and understand, and I still didn't understand how to find a minimum cut, and had to do some outside reading. Overall I would give this section a 5/10.

Having found an algorithm that solves the Maximum-Flow problem, we know look towards finding situations were we can apply the algorithm. One very basic algorithm of maximum flows and minimum cuts is the Bipartite Matching Problem. A bipartite graph is an undirected graph whose node set can be partitioned into two smaller sets, with the property that every edge of the graph must have one end in each of the two subsets. A matching M in G is a subset of the edges such that each node appears in at most one edge in M. The bipartite matching problem is finding a matching in F of the largest possible size. While the flow networks are directed graphs, and we are working with undirected graphs, it is not difficult to use the algorithm we developed to solve this problem. Beginning with a bipartite graph g, we can construct a flow network, directing all edges in G from X to Y, and adding a source node s and an edge from s to all nodes in X, and a sink node t and an edge to t from all nodes in Y. Consider a flow f' in G' of value k edges. All edges in the path have a value of 1, and all other edges have a value of 0. Thus the set M' of edges of the form (x, y) on which the flow value is 1. M' contains k edges, since every edge value is 1 and the total value is k. Each node in X is the tail of at most one edge in M'. Each node in Y is the head of at most one edge in M'. The size of the maximum matching in G is equal to the value of the maximum flow in G'; and the edges in such a matching in G are the edges that carry flow from X to Y in G'. THe Ford-Fulkerson Algorithm can be used to find a maximum matching in a bipartite graph in O(mn) time. However, not all bipartite graphs have perfect matchings. To determine if a bipartite graph has a perfect matching, we can use the algorithm to find the maximum matching, and check if it is a perfect matching, but there is a better way. We can look for the minimum capacity s-t cut, and if it is less than n, then we know that the max flow value must be less than n, and thus, there is not a perfect matching. If a bipartite graph G with two sides X and Y has a perfect matching, then for all nodes in X we must have a distinct match in Y, and thus the size of Y must be at least as large as X. 'Assume that the bipartite graph G has two sides X and Y and that they are the same size. Then the graph G either has a perfect matching or there is a subset such that the corresponding subset is smaller. A perfect matching can be found in O(mn) time. This section was more difficult to follow, but hopefully will make more sense after studying it in class. I would give this section a 3/10.