Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:thetfordt:chapter7 [2018/04/01 22:28] – thetfordt | courses:cs211:winter2018:journals:thetfordt:chapter7 [2018/04/02 15:53] (current) – thetfordt | ||
|---|---|---|---|
| Line 15: | Line 15: | ||
| The section then walks through a variety of different proofs which back up the intuition behind the algorithm. At every stage of the algorithm, the flow values and the residual capacities are integers. Later in the section, we denote the value C as the summation of capacities of edges out of s. The section walks through the proof that the algorithm terminates in at most C iterations of this summation. And it concludes this part of the section by outlining the proof that the Ford-Fulkerson Algorithm can be implemented to run in O(mC) time. | The section then walks through a variety of different proofs which back up the intuition behind the algorithm. At every stage of the algorithm, the flow values and the residual capacities are integers. Later in the section, we denote the value C as the summation of capacities of edges out of s. The section walks through the proof that the algorithm terminates in at most C iterations of this summation. And it concludes this part of the section by outlining the proof that the Ford-Fulkerson Algorithm can be implemented to run in O(mC) time. | ||
| + | I would rate the readability of this section at 7/10. | ||
| + | |||
| + | ===== Section 7.2 - Maximum Flows and Minimum Cuts in a Network ===== | ||
| + | |||
| + | In this section, we continue to analyze the Ford Fulkerson algorithm. | ||
| + | |||
| + | The section begins by defining a cut, which is a division of the nodes such that s lies in one division, call it A, and B lies in the other division, call it B. The section walks through the proof that, for any s-t cut, the value of the flow if the flow out of A minus the flow into A. And from this, we can prove that if f is an s-t flow, and (A,B) is an s-t cut, then the value of f is less than or equal to the capacity of (A,B). This inequality is useful for us in proving the optimality of the Ford Fulkerson Algorithm. | ||
| + | |||
| + | The section then walks into the driving point of the section: That the Max-Flow Equals the Min-Cut. That is, if f is an s-t flow, and there is no path in the residual graph, then there is an s-t cut (A*,B*) in G for which the value of the flow equals the capacity of (A*,B*). Consequently, | ||
| + | |||
| + | This fact combined with the fact from earlier, that for any s-t cut, the flow out of A minus the flow into A equals the value of the flow of the graph, gives us the optimality of the Ford-Fulkerson Algorithm. And from here, the section walks through the proof that we can compute an s-t cut of minimum capacity in O(m), which helps further explain the overall runtime of the algorithm. | ||
| + | |||
| + | The section concludes by discussing some details of integer assumptions behind the algorithm. They note that for all practical applciations, | ||
| + | |||
| + | I would rate the readability of this section at 8/10. | ||
| + | |||
| + | ===== Section 7.5 - A First Application: | ||
| + | |||
| + | In this section, we address an old problem: The Bipartite Matching Problem, but we do it using the Ford Fulkerson Algorithm. We want to use the Ford Fulkerson Algorithm in order to find the largest Matching M in G, a subset of the edges such that each node appears in at most one edge in M. | ||
| + | |||
| + | Given the bipartite graph G, we direct all edges in G from X to Y (the two sets), add a node s, and edges (s,x) to all nodes in X, add a node t, and edges (y,t) for all nodes in Y. And after doing this, we just run the Ford Fulkerson Algorithm to obtain a maximum s-t flow in this new network we have created. And the assertion is that the value of this flow is equal to the size of the largest matching M in G. (Note all edges have capacity 1). | ||
| + | |||
| + | When considering the set of edges M' that connect x's to y's, the section walks through the assertions that M' contains k edges, each node in X is the tail of at most one edge in M', and each node in Y is the head of at most one edge in M'. With these facts, we can reason that the size of the maximum matching in G is equal to the value of the maximum flow of the network flow created from G, and the edges in that matching are edges that carry flow from X to Y in G'. | ||
| + | |||
| + | When analyzing the runtime of this algorithm, we note that the ' | ||
| + | |||
| + | The section uses the rest of the section to discuss bipartite graphs that do not have perfect matchings. If we have a perfect matching, for every subset A of X of nodes such that Gamma(A) equals the nodes which the nodes in A are mapped to, then Gamma(A) must be greater than or equal to the size of A. Again, this statement is also true vice versa. That is, if we have a bipartite graph with sides X and Y, the graph either has a perfect matching, OR, there is a subset A of X such that the size of Gamma(A) is less than the size of A. And since we are using the Ford Fulkerson Algorithm to accomplish this, this can be done in O(mn) time. | ||
| + | |||
| + | I would rate the readability of this section at 6/10. | ||
| + | |||
| + | ===== Section 7.7 - Extensions to the Maximum-Flow Problem ===== | ||
| + | |||
| + | The section begins by laying out the premise- that many different types of problems can be slightly altered to be solved in the same way we solve the maximum-flow problem. | ||
| + | |||
| + | The first problem outlined here is the problem surrounding circulations with demands. Suppose that incoming flow is demand, and outgoing flow is supply. And we are given a graph G with multiple source nodes and multiple sink nodes. We are seeking to satisfy all of the demand of the given graph. | ||
| + | |||
| + | In order to design an algorithm to see if there is a feasible circulation with demands in G, we slightly alter the original G and use the Ford Fulkerson Algorithm to figure this out. We alter it by creating a super-source s* and a super-sink t*, where the super source has edges to all other sources and each of the initial sinks have an edge to the super sink. It turns out that the circulation is feasible if and only if the maximum s*-t* flow is G' has value equal to the summations of each individual node's demand. | ||
| + | |||
| + | The problem is then slightly altered. Suppose that there are lower bounds on the edges in terms of the flow that passes through them. In order to do this, we just slightly modify the input. We let G' have the same nodes and edges, but the capacity of each edge is the original capacity minus that edge's lower bound. The section then walks through the proof that this modification plugged into the Ford Fulkerson Algorithm will produce the desired results. | ||
| + | |||
| + | I would rate the readability of this section at 6/10. I found 7.5 and 7.7 very difficult to grasp as we have not yet covered them in class. | ||
