| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2018:journals:melkersonr:chapter7 [2018/04/03 03:04] – [Section 7.5] melkersonr | courses:cs211:winter2018:journals:melkersonr:chapter7 [2018/04/03 03:42] (current) – [Section 7.7] melkersonr |
|---|
| ===== Section 7.2 ===== | ===== Section 7.2 ===== |
| |
| * **Summary:** Section 7.2 is Maximum Flows and Minimum Cuts in a Network. This subsection is concerned with further analyzing the Ford-Fulkerson algorithm. Recall that in section 7.1 we upper-bounded the maximum s-t flow as the sum of all edges out of s. We expand that idea and define an s-t cut to be "a partition (A,B) of the vertex set V, so that s in A and t in B. The capacity of a cut (A,B), which we will denote c(A,B), is simply the sum of the capacities of all edges out of A" (p 346). In the cut we originally mentioned, A consists of only s and B consists of the rest of the nodes in V. Armed with this definition, we know that we could have also defined the value of a flow as the sum of all edges going into the sink. Further, we conclude that the value of the flow is less than or equal to the capacity of an A,B cut of G. This means that "the value of every flow is upper-bounded by the capacity of every cut" (p 348). We take these notions a step further and say that the maximum flow corresponds to a minimum cut. This observation implies that we can extend the Ford-Fulkerson algorithm to give the minimum s-t cut (A*, B*), and we can do so in O(m) time. | * **Summary:** Section 7.2 is Maximum Flows and Minimum Cuts in a Network. This subsection is concerned with further analyzing the Ford-Fulkerson algorithm. Recall that in section 7.1 we upper-bounded the maximum s-t flow as the sum of all edges out of s. We expand that idea and define an s-t cut to be "a partition (A,B) of the vertex set V, so that s is in A and t is in B. The capacity of a cut (A,B), which we will denote c(A,B), is simply the sum of the capacities of all edges out of A" (p 346). In the cut we originally mentioned, A consists of only s and B consists of the rest of the nodes in V. Armed with this definition, we know that we could have also defined the value of a flow as the sum of all edges going into the sink. Further, we conclude that the value of the flow is less than or equal to the capacity of an A,B cut of G. This means that "the value of every flow is upper-bounded by the capacity of every cut" (p 348). We take these notions a step further and say that the maximum flow corresponds to a minimum cut. This observation implies that we can extend the Ford-Fulkerson algorithm to give the minimum s-t cut (A*, B*), and we can do so in O(m) time. |
| * **My Questions:** The page about integer vs real numbers was difficult to read. Are we ok with non-integer values, or not? | * **My Questions:** The page about integer vs real numbers was difficult to read. Are we ok with non-integer values, or not? |
| * **Second Time Around:** The idea of a minimum cut makes more sense after reading. | * **Second Time Around:** The idea of a minimum cut makes more sense after reading. |
| ===== Section 7.5 ===== | ===== Section 7.5 ===== |
| |
| * **Summary & Motivations:** Section 7.5 is A First Application: The Bipartite Matching Problem. This subsection begins the discussion on application fo maximum flows and minimum cuts in graphs. The application for this subsection is the Bipartite Matching Problem. Recall that "a matching M in G is a subset of the edges M subset E such that each node appears in at most one edge in M" (p 368). This problem involves finding a matching in G that is as large as possible. We want an algorithm to get the value of the maximum matching and to recover that matching. | * **Summary & Motivations:** Section 7.5 is A First Application: The Bipartite Matching Problem. This subsection begins the discussion on applications of maximum flows and minimum cuts in graphs. The application for this subsection is the Bipartite Matching Problem. Recall that "a matching M in G is a subset of the edges M subset E such that each node appears in at most one edge in M" (p 368). This problem involves finding a matching in G that is as large as possible. We want an algorithm to get the value of the maximum matching and to recover that matching. |
| * **About the Algorithms:** All we must do to get what we want is add to the Ford-Fulkerson algorithm. We start with the graph G in an instance of the Bipartite Matching Problem, add the source, add edges from the source to all nodes in X, add the sink, add edges to the sink from all edges in Y. After some proofs, we conclude that "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' " (p 369). The runtime for this algorithm is O(mn), where n is the number of nodes in X/Y. The subsection closes with a discussion on graphs that have no perfect matching. | * **About the Algorithms:** All we must do to get what we want is add to the Ford-Fulkerson algorithm. We start with the graph G in an instance of the Bipartite Matching Problem, add the source, add edges from the source to all nodes in X, add the sink, and add edges to the sink from all edges in Y. After some proofs, we conclude that "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' " (p 369). The runtime for this algorithm is O(mn), where n is the number of nodes in X (and in Y). The subsection closes with a discussion on graphs that have no perfect matching. |
| * **My Questions:** What again is Gamma(A)? | * **My Questions:** What again is Gamma(A)? |
| * **Second Time Around:** Technically, this was the "first time around," so I cannot say that anything made sense the second time I saw it. | * **Second Time Around:** Technically, this //was// the “first time around,” since we did not have class 4/2, so I cannot say that anything made more sense the second time I saw it. |
| * **Note to Self:** This is another example of an old problem seeing new light (Bipartite Matching). | * **Note to Self:** This is another example of an old problem seeing new light (Bipartite Matching). |
| * **Readability:** 6 - Because the extension part was really hard to follow. | * **Readability:** 6 - Because the extension part was really hard to follow. |
| ===== Section 7.7 ===== | ===== Section 7.7 ===== |
| |
| * **Summary & Motivations:** Section 7.7 is Extensions to the Maximum-Flow Problem. | * **Summary & Motivations:** Section 7.7 is Extensions to the Maximum-Flow Problem. This subsection deals with extensions to the Max-Flow problem, as the title suggests. This sentence sums up the power of the Max-Flow problem pretty well: "The power of the Maximum-Flow Problem...lies in the fact that many problems with a nontrivial combinatorial search component can be solved in polynomial time because they can be reduced to the problem of finding a maximum flow or a minimum cut in a directed graph" (p 379). We explore two related problems here: Circulations with Demands, first without and then with Lower Bounds. Here we allow more than one source and more than one sink. Now instead of deciding which source or sink to use, we'll image that sources have supplies and sinks have demands, of flow. We have the same capacity condition as before for this problem, but there is no conservation condition anymore. It is more or less replaced by the demand condition: for each node in V, the flow into v minus the flow out of v is equal to v's demand. Further, this problem is no longer about maximization. Rather, it's about feasibility. We want to know if it's possible to satisfy all demands. The only difference between no lower bounds and having lower bounds is that when there are lower bounds on the edges it means that the minimum flow for that edge is its lower bound, not zero. |
| * **About the Algorithms:** | * **About the Algorithms:** We solve the problem that has no lower bound by adding a "super source" that supplies everything in S and a "super sink" that siphons from everything in T. Then the problem reduces to the Max-Flow algorithm, and the runtime is O(Cm). We solve the problem //with// lower bounds by reducing it to a problem with no lower bounds. We simply push flow down edges at a value equal to their lower bound and adjust the upper bound on that edge and the demands at its two ends accordingly. |
| * **My Questions:** | * **My Questions:** What examples are there for when lower bounds would occur? The book didn't give any. |
| * **Second Time Around:** | * **Second Time Around:** Technically, this //was// the “first time around,” since we did not have class 4/2, so I cannot say that anything made more sense the second time I saw it. |
| * **Note to Self:** | * **Note to Self:** Figure 7.14 reminds me of things we did in CSCI 313. |
| * **Readability:** | * **Readability:** 8 - pretty straightforward. |
| |
