Chapter 7

Often times, graphs are used to model transportation networks where the edges represent connections between objects or places. In real life, these routes typically have some amount of maximum capacity. Additionally, some nodes will generate this traffic, which are called sources, and others will be the destination of traffic, AKA sinks. The traffic in a graph of this nature is called flow, and the graph itself is called a flow network. We define a flow network to have edges with a capacity c, possibly different for each edge, one source node, and one sink node. Other nodes are called infernal nodes. We use a function that maps an edge to the amount of flow currently running through it. The maximum-flow problem is one that aims to efficiently distribute flow so that edges carry as close to their capacity as possible. In solving this problem, there are no known greedy or dynamic programming algorithms that are optimal. One step in trying to solve the problem is defining the residuals graph. This graph has the same nodes and edges as the original graph, but for the edges capacity it lists ce - f(e) to denote how much is wasted in a sense. These edges are forward edges. For any e with f(e) > 0, we include another edge with f(e) as the capacity that denotes how much can be undone. These are backwards edges. The next step is producing an algorithm that alters the flow of the graph and creates a new flow by increasing and decreasing the flow values of edges. Ultimately, we can use this to build a function to find the max flow iterates over paths in the residual graphs and uses it to run the flow augmentation algorithm. While it requires significant proof to show the algorithm works. Ultimately, the book shows it to terminate. It is shown to run in O(mC) where C is the maximum capacity.

This section went into the proof-heavy description I find tedious to read. It is a cool algorithm on the other hand. I will ultimately give it a 5/10 as a result.

This section looks further into the algorithm from 7.1 in an attempt to show it really does generate the best possible result. The previous section used a general way to discuss the upper-bound on the flow of a graph, but this section uses the idea of a cut. A cut of a graph would be an s-t cut where we divide the elements into two sets, A and B, where s is in A and t is in B. The book goes to prove in a lengthy proof that one can actually measure flow by looking at the flow across a cut. The next portion of the section involves numerous proofs to ultimately validate the initial claim of the section. It is really difficult to summarize it though other than that it took the process one step at a time by proving statements that can ultimately be pieced together in addition to a number of corollaries. The last section goes into what follows when all of the capacities of the original graph are integers. It says that in this case, there is an integer maximum flow. It then discusses when there are non-integer values. By carefully picking real valued capacities, the original algorithm can actually infinitely loop.

This section was a lot to intake and a lot of it, while necessary, simply grinded through proofs. I really did not enjoy it. I give it a 2/10.

The problem for this section is about solving the Bipartite Matching Problem. A matching in G is a subset of the edges such that each node appears in at most one of the edges of the subset. The Bipartite Matching Problem is finding the matching of largest possible size. It goes to state that bipartite graphs are undirected where as flow graphs are directed, but we can still use the flow algs to solve this problem. We use the bipartite graph to create an analogous flow graph and we then find the maximum flow of that graph. The section proves that this mapping from one graph to another is performable in a transparent fashion. Once we have this mapping, we can use the Ford-Fulkerson algorithm to find the matching in O(nm) time. It would make sense to take this matching and check if it is perfect, but not all bipartite graphs have a perfect matching, so it goes on to discuss what these look like. We hope to be able to find a certificate for a graph without a perfect matching to verify this. Hall's theorem provides one such certificate that can be generated in polynomial time. Specifically, we can go to show it can be done in O(mn).

Again, this is not quite the type of section that interests me, so I once again give it a 2/10. I understand why thorough proofs are necessary, obviously, but I feel like they could be somewhere other than the main text.

The section begins by saying that the power of the Maximum-Flow problem lays not in looking at traffic flows, but at the ability to reduce other problems to the Maximum-Flow problem in polynomial time. Bipartite Matching served as the first example of this. One first generalization that is made is removing the stipulation that you can only have 1 source and 1 sink. We assign a supply and demand values to sources and sinks. The goal in this setting is to satisfy all demand given what supply we have. We then assign a demand to each node and negative demand indicates a source and positive demand indicates a sink. A circulation on a set of demands is a function that assigns nonnegative real number to each edge and satisfies capacity and demand conditions. In regards to this problem, we care simply about if a circulation exists that meets the conditions. One simple thing that determines this is if total supply equals total demand. The next step in this is to convert it to a maximum-flow problem and find an optimal s-t flow. The next generalization we make on this problem is to add the stipulation that certain edges be used by placing lower bounds. To solve this, we convert it to a circulation problem like before by doing it in a manner that removes the lower bounds.

This ends our review of the chapter, luckily. I really, really did not like this chapter. I will, however, acknowledge that the idea of turning problems into a different type of problem we can solve is a concept covered heavily in CS 313, which is cool. So this section gets once again, a 2/10.

This concludes the use of this Wiki. All in all, I may not have enjoyed all of the sections, but it is certainly true that I learned a lot from using this textbook.