Chapter 7

We are given a directed graph with various nodes with edges along with their maximum capacity of flow each of these edges can hold. There is a single source node and a single sink node. Flow from the source should end up in the sink. Also, the flow into a node should equal to the flow out of the node. The problem we need to solve is to find the flow of the maximum possible value.

First, we make a residual graph. The initial residual graph is the same as the original graph, so we just copy it.

We start with the total flow in the graph being 0. Then, we find a path from the source node to the sink node and put in the flow. The amount of flow we put in should be the maximum possible flow in this particular path. Thus, the flow we put in would be the bottleneck of the path, or the flow that the least capacity edge would be able to hold. Once we put flow in the graph, we update the residual graph. For each edge in the path, we draw a residual edge, pointing the opposite from the flow. This edge would have the amount of flow between the nodes. We also modify the actual edge by subtracting the flow from its capacity. Thus, this new number is it's new capacity.

Now, we continue this algorithm until there is no more augmenting path left in the graph.

Algorithm in page 342 - 344.

“At every intermediate stage of the Ford-Fulkerson Algorithm, the flow values and the residual capacities in Gf are integers.” (Proof on page 344)

“Let f be a flow in G, and let P be a simple s-t path in Gf. Then v(f') = v(f) + bottleneck(P, f); and since bottleneck(P, f) > 0, we have v(f') > v(f).” (Proof on page 345)

“Suppose, as above, that all capacities in the flow network G are integers, then the Ford-Fulkerson Algorithm terminates in at most C iterations of the While loop, where C is the sum of the values of the flow out of s when all the outflows are saturated.” (Proof on page 345)

“Suppose as above, that all capacities in the flow network G are integers, then the Ford-Fulkerson Algorithm can be implemented to run in O(mC) time” (Proof on page 345, 346)

“Let f be any s-t flow, and (A, B) be any s-t cut. Then v(f) = fout(A) - fin(A).” (Proof on page 347)

“Let f be any s-t flow, and (A, B) be any s-t cut. Then v(F0 = fin(B) - fout(B).” (Proof on page 347)

“Let f be any s-t flow, and (A, B) be any s-t cut. Then v(f) ⇐ c(A, B).” (Proof on page 348)

“If f is an s-t flow such that there is no s-t path in the residual graph Gf, then there is an s-t cut (A*, B*) in G for which v(f) = c(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.” (Proof on page 349)

“The flow f' returned by the Ford-Fulkerson Algorithm is a maximum flow.”

“Given a flow f of maximum value, we can compute an s-t cut of minimum capacity in O(m) time.” (Proof on page 350)

“In every flow network, there is a flow f and a cut (A, B) so that v(f) = c(A, B).”

“In every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut.”

“If all capacities in the flow network are integers, then there is a maximum flow f for which every flow value f(e) is an integer.”

Now, if we had real numbers as capacities, rather than integers, we might run into an infinite loop while running the algorithm, or at least the algorithm would run for a gigantic number of iterations. This is because our iteration will keep going on until we saturate an edge with a real number capacity, which will take a very very long time.

The Bipartite Matching Problem is to find matchings of the largest possible size in a given graph of two sets of nodes, where the nodes from one set are undirectedly connected to the nodes in the other set.

The given graph is not a network flow graph. We need to make it a network flow graph. To do this, we make all the edges from a set of nodes to the other set of nodes directed. We also add in a source node that has directed edges to the set of nodes from which the edges are pointed out to the other set of nodes. We also add in a sink node that has directed nodes coming into it from the nodes that the edges are directed to. Also, in all the edges, we add in a capacity of 1. Now, we have a network flow graph.

“M' contains k edges”, where k is the value of flow in the graph. (Proof in page 369)

“Each node in X is the tail of at most one edge in M'”, where X is a set of nodes from which the edges are coming out. (Proof on page 369)

“Each node in Y is the head of at most one edge in M'” (Same as the one above)

“The size of the maximum matching in G is equal to the vale 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'.”

To create a network flow graph and to solve run the Ford-Fulkerson Algorithm, the bipartite graph can be solved in O(mn) time, where m is the number of edges in the graph and n is the number of nodes in each of the sets X and Y.

Now, we have a graph where some of the nodes may send out more flow than it takes in, whereas the some other nodes may take in more flow than they send out. The ones that give out more flow are the supply nodes and the ones that eat up the flow are the demand nodes. Note that the demand nodes have a negative number on them, showing how much flow they eat up for themselves, whereas the supply nodes have a positive number on them, showing how much flow they add up.

For this type of problem, we simply connect all the supply nodes to a SOURCE NODE and all the demand nodes to a SINK NODE. Now, we have a network flow problem.

“There is a feasible circulation with demands in G if and only if the maximum s*-t* flow in G' has a value D. If all capacities and demands in G are integers, and there is a feasible circulation, then there is a feasible circulation that is integer-valued.” (Proof on page 381-382)

Now, we have the above Circulation problem modified. We have a condition on some of the edges, that these edges MUST have a certain flow on them.

We need to reduce the given problem to a one with no lower bounds. To do this, we just update the whole graph by satisfying any of the lower bound edges as required and changing the direction of the edges, the capacity of the edges and the demand and supply of the nodes, just like what we would do on a residual graph while adding in flow. Thus, now we have a problem that is similar to the one above: The Circulation with Demands problem, with no lower bounds.

“There is a feasible circulation in G if and only if there is a feasible circulation in G'. If all demands, capacities, and lower bounds in G are integers, and there is a feasible circulation, then there is a feasible circulation that is integer-valued.” (Proof on page 384)

No questions on the chapter. Class discussions explains everything. In addition, the chapter was comparatively easier than the previous chapters to read and to understand. It was easily readable, and understandable.

It was very interesting how we took different kinds of problems, namely, Bipartite Graph Problem, Demand Circulation Problem, Demand Circulation with Lower Bounds Problem, Survey Design Problem and Flight Schedules Problem, and turned them into a Network Flow Problem and easily solved them. I wonder what other problems can be solved using this.