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:40] – [7.7 Extensions to Max Flow Problem] 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 97: | 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 138: | 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 149: | 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: | ||
