Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:nasona:chapter7 [2018/04/01 14:22] – [7.1 Max Flows and Ford-Fulkerson] nasona | courses:cs211:winter2018:journals:nasona:chapter7 [2018/04/01 16:57] (current) – [7.7 Extensions to Max Flow Problem] nasona | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| =======7.1 Max Flows and Ford-Fulkerson======= | =======7.1 Max Flows and Ford-Fulkerson======= | ||
| ==Summary== | ==Summary== | ||
| + | A flow network is a directed graph G=(V, E) that has a capacity associated with each edge, a single source node, and a single sink node. Our goal is to create an algorithm that computes the maximum flow of the flow network while also satisfying capacity and conservation conditions. Our algorithm will push flow forward on edges with leftover capacity and push flow backward on edges that are already carrying flow, to divert it in a different direction. We do this using a residual graph Gf. This algorithm is called the Ford-Fulkerson Algorithm. The algorithm runs in O(mC) time. | ||
| ==The Problem== | ==The Problem== | ||
| * Flow network: directed graph G = (V, E) with the following features | * Flow network: directed graph G = (V, E) with the following features | ||
| Line 65: | Line 66: | ||
| =======7.2 Max Flows and Min Cuts in a Network======= | =======7.2 Max Flows and Min Cuts in a Network======= | ||
| ==Summary== | ==Summary== | ||
| + | We can measure the flow value by accounting for the amount of flow f sent across a cut (A, B); it is the total amount that leaves A minus the amount coming into A. The value of every flow is upper bound by the capacity of the cut. Flow f has the maximum value of any flow and that (A*, B*) has the minimum capacity of any s-t cut. In every flow network, the maximum value of an s-t slow is equal to the minimum capacity of an s-t cut. The Ford-Fulkerson algorithm works for rational and real numbers as capacities beyond integers values. | ||
| ==Analyzing the Algorithm: Flows and Cuts== | ==Analyzing the Algorithm: Flows and Cuts== | ||
| * Use the notion of a cut to develop a much more general means of placing upper bounds on the maximum-flow value | * Use the notion of a cut to develop a much more general means of placing upper bounds on the maximum-flow value | ||
| * S-t cut is a partition (A, B) of the vertex set V so that s is in A and t is in B | * S-t cut is a partition (A, B) of the vertex set V so that s is in A and t is in B | ||
| * Capacity of a cut (A, B), which is denoted as c(A, B), is simply the sume of the capacities of all edges out of A | * Capacity of a cut (A, B), which is denoted as c(A, B), is simply the sume of the capacities of all edges out of A | ||
| - | * Let f be any s-t flow and (A, B) any s-t cut. Then, v(f) = f:out(A) – fin(A). | + | * Let f be any s-t flow and (A, B) any s-t cut. Then, v(f) = f:out(A) – f:in(A). |
| * By watching the amount of flow f sends across a cut, we can exactly measure the flow value: it is the total amount that leaves A minus the amount that swirls back into A | * By watching the amount of flow f sends across a cut, we can exactly measure the flow value: it is the total amount that leaves A minus the amount that swirls back into A | ||
| * Let f be any s-t flow, and (A, B) any s-t cut. Then v(f) = f: | * Let f be any s-t flow, and (A, B) any s-t cut. Then v(f) = f: | ||
| Line 92: | Line 93: | ||
| ==Additional Information== | ==Additional Information== | ||
| + | The relevancy of min cuts to max flows was very confusing to me at first in class. However, after reading the explanation in the book, it is clearer. The max-flow min-cut theorem tells us that in every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut. | ||
| The readability of this section was a 7 out of 10. The hard part of this section was remembering exactly what a cut was, but once I did that, it was easy going from there. The authors did a really good job of using clear language to explain the max-flow min-cut theorem and the relationship between flows and cuts. | The readability of this section was a 7 out of 10. The hard part of this section was remembering exactly what a cut was, but once I did that, it was easy going from there. The authors did a really good job of using clear language to explain the max-flow min-cut theorem and the relationship between flows and cuts. | ||
| =======7.5 Bipartite Matching Problem======= | =======7.5 Bipartite Matching Problem======= | ||
| ==Summary== | ==Summary== | ||
| + | We can use an algorithm for the Maximum-Flow Problem to find a maximum matching for bipartite graphs. We will direct all edges in G from X to Y, we will then add a node s in X and a node t in Y, and give each edge in G' a capacity of 1. We now can compute the max flow and matching using the Ford-Fulkerson Algorithm. 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 in such a matching in G are the edges that carry flow from X to Y in G’. The runtime is O(mn) for a bipartite graph. We can decide if the graph has a perfect matching by checking if the maximum flow in a related graph G’ has value at least n. | ||
| ==The Problem== | ==The Problem== | ||
| Line 132: | Line 135: | ||
| ==Additional Information== | ==Additional Information== | ||
| + | At first, I was confused as to how this problem applies to our maximum flow algorithm. But, with the way you set up the problem before the algorithm, it makes sense. First, we direct all edges in G from X to Y, we add a node s in X and a node t in Y, and we give each edge in G’ a capacity of 1. Then, we are able to use the algorithm we know to compute the max flow of the graph, and we know the output value of the max flow is the same as the max matching. | ||
| + | |||
| The readability of this section on a scale of one to ten was a 8. This is because it was just an explanation of how to apply an algorithm that we already knew how to do. | The readability of this section on a scale of one to ten was a 8. This is because it was just an explanation of how to apply an algorithm that we already knew how to do. | ||
| =======7.7 Extensions to Max Flow Problem======= | =======7.7 Extensions to Max Flow Problem======= | ||
| ==Summary== | ==Summary== | ||
| + | The problem of circulations with demands has the problem of is it feasible for the circulation capacity and demand conditions to exist. Total supply must equal the total demand for a circulation to be feasible. There is a feasible circulation with demands {dv} in G if and only if the max s*-t* flow in G’ has value D (the capacity). We can add lower bounds to ensure flow to certain edges. In order to do this, we need to reduce this to the problem of finding a circulation with demands but no lower bounds. | ||
| ==The Problem: Circulations with Demands== | ==The Problem: Circulations with Demands== | ||
| Line 146: | Line 152: | ||
| * dv < 0: supply of –dv | * dv < 0: supply of –dv | ||
| * dv=0; neither a source nor a sink | * dv=0; neither a source nor a sink | ||
| - | * circulation with demands {dv} is a function that assigns a nonnegative real number to each edge and satisfies the following two conditions: capacity conditions and command | + | * circulation with demands {dv} is a function that assigns a nonnegative real number to each edge and satisfies the following two conditions: capacity conditions and demand |
| * feasibility problem: whether there exists a circulation that meets the above conditions | * feasibility problem: whether there exists a circulation that meets the above conditions | ||
| * in order for feasible circulation: | * in order for feasible circulation: | ||
| Line 186: | Line 192: | ||
| ==Additional Information== | ==Additional Information== | ||
| + | The added layer of the demand value added some confusion to my comprehension of this problem. If dv > 0 the node is a sink, if dv < 0 the node is a supply, and if dv=0 the node is an interior node. Basically, as a result, our problem transitions from the problem of max flow to a problem of feasibility. Does there exist a circulation with demands {dv}, which is a function, that assigns a nonnegative real number to each edge and satisfies capacity conditions and command conditions? | ||
| The readability of this section was a 7 on a scale of 1 to 10. This is because I was kind of confused for both of these applications of the algorithm. However, after reading it a second time, it definitely makes more sense. I think that the confusion stems from the fact that there are a lot of moving parts with these two problems. The added demand value definitely added an extra layer to understand, which was difficult at first. | The readability of this section was a 7 on a scale of 1 to 10. This is because I was kind of confused for both of these applications of the algorithm. However, after reading it a second time, it definitely makes more sense. I think that the confusion stems from the fact that there are a lot of moving parts with these two problems. The added demand value definitely added an extra layer to understand, which was difficult at first. | ||
