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 15:31] – [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 66: | 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 98: | Line 98: | ||
| =======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 139: | Line 140: | ||
| =======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 150: | 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: | ||
