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:41] – [7.2 Max Flows and Min Cuts in a Network] nasona | courses:cs211:winter2018:journals:nasona:chapter7 [2018/04/01 16:57] (current) – [7.7 Extensions to Max Flow Problem] nasona | ||
|---|---|---|---|
| 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: | ||
