Chapter 7: Network Flow

Graphs are used to model transportation networks, which are networks whose edges carry traffic and whose nodes act as “switches” to pass the traffic. Each edge has a capacity, a specified amount that they can carry, and there are source and sink nodes which direct the flow of traffic. A flow network is a graph with non-negative edges, that has a single source node s and a single sink node t. Furthermore, we assume that there are no edges entering the source and no edges leaving the sink, each node has an edge and all capacities are integers. Flow through the graph is conserved. That is, if a flow of 10 goes into a node, then 10 leaves the node. The problem generally associated with these graphs are finding the maximum flow across the graph and the minimum cut of the graph. In order to find the maximum flow, we first find the residual graph, which is the graph found be traversing the augmenting paths from s-t, and determining the maximum flow through each path. We can find the “leftover” flow after each of these traversals. This algorithm is outlined on pages 342 and 344 of the text. The section then details how we are able to determine that the Ford-Fulkerson algorithm runs in O(mC) time with m being the number of edges in the graph and C denoting the sum of the flow. This section is a little confusing. It was tough running through the examples in class and the section is a little long-winded. I think writing out another example would probably help me a lot. I would give this section a 8/10 because event though it is a little hard to understand i is an important type of problem and one with interesting uses.

This section continues to look at the Ford-Fulkerson algorithm and focuses on the idea of cuts. The section strives to prove that F-F returns the maximum possible flow. A cut separates the graph into two sections and limits the flow that can come in and out of a section. Then, we know that after making these minimum cuts, we can tell that the value of every flow is less than or equal to the capacity of every cut. The section goes on to prove the existence of a cut that produces the cut that results in a maximum flow and several other results that come from cuts. The importance of using integers as the capacities for the edges. If we were to use real numbers as opposed to integers, the Ford-Fulkerson algorithm would run forever as we assume in the algorithm everything increases by increments of 1. Using integers allows us to better control how many times the algorithm will run.

This section was very proof heavy and therefore a little confusing. I would give it a 6/10.

The Bipartite Matching Problem is a problem we discussed earlier in the semester, where we want to split a graph into two colors of nodes. We can create a flow network from a bipartite graph that will have a maximum matching that is equal to the maximum flow of the graph. We try and find the best matching for the graph (a matching is the two sets in which one can entirely be colored blue and the other red and there are edges between them). We then bound the run time of this algorithm O(mn) where m is the number of edges in the graph. There is discussion of further refining this run time but it is not necessary. We also want to be able to determine whether a graph has a perfect matching and output this information to the user.

This section was super confusing to me. I'm not really sure what the motivation is behind this problem is. Since I was confused I would give this section a 5/10. It was confusing and I hope we discuss this problem in class.

The Maximum-Flow problem is able to do a lot more than determine how much traffic can flow across a graph. Some of the other problems that exist in tandem with the Maximum-Flow are circulations with demands and circulation with bounds. The circulation with demands is when we have multiple sources and multiples sinks and a fixed supply and demand that we must ship across the graph. We want to know that there is a circulation that delivers the necessary demand without exceeding the capacity of the graph. In order to determine what this circulation is, we can find a maximum s-t flow is a graph that is made by attaching a super source and a super sink to each end of the graph. The process by which we are able to glean a maximum graph using this is on page 381 of the text. Then we know that there is a feasible circulation if the maximum flow of the graph is D. Another problem is the circulations with demands and lower bounds. This problem enables us to force the flow to pass through certain edges by placing lower bounds on some edges. The strategy behind the algorithm is to reduce this to finding a circulation with demands but no lower bounds. (Discussed on 383 of the text).

I would give this section a 6/10. It was little confusing and I'm not entirely sure how these problems would be applied in real life. I am sure that we will go over this in class and it will help me see things a little more clearly.