Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2012:journals:virginia:chapter7 [2012/04/04 01:52] – lovellv | courses:cs211:winter2012:journals:virginia:chapter7 [2012/04/04 02:59] (current) – lovellv |
|---|
| |
| We can implement this algorithm in O(mC) time, where m is the number of edges and C is the maximum flow we could send out of the source node s. | We can implement this algorithm in O(mC) time, where m is the number of edges and C is the maximum flow we could send out of the source node s. |
| | |
| | Readability: 8 |
| |
| ===== Section 2: Maximum Flow and Minimum Cuts in a Network ===== | ===== Section 2: Maximum Flow and Minimum Cuts in a Network ===== |
| |
| Note that if we did not have integer capacities the FF algorithm would not necessarily terminate, but the max flow - min cut theorem still holds. | Note that if we did not have integer capacities the FF algorithm would not necessarily terminate, but the max flow - min cut theorem still holds. |
| | |
| | Readability: 8 |
| |
| ===== Section 5: The Bipartite Matching Problem ===== | ===== Section 5: The Bipartite Matching Problem ===== |
| |
| In this section, we see how to solve the bipartite matching problem using our new algorithm. First we need to create a flow network from our original graph. This network will have directed edges from nodes in X to nodes in Y, in place of any undirected edge between a node in X and a node in Y. Then we add a source node with an edge from it to each node in X, and a sink node with an edge to it from each node in Y. Each edge has capacity 1. Finally we run the FF algorithm. This gives us the size of the maximum matching (since the capacities are 1, each node can appear at most once). We can then use the flow to find the matching. We can find this matching in O(mn) time. | In this section, we see how to solve the bipartite matching problem using our new algorithm. First we need to create a flow network from our original graph. This network will have directed edges from nodes in X to nodes in Y, in place of any undirected edge between a node in X and a node in Y. Then we add a source node with an edge from it to each node in X, and a sink node with an edge to it from each node in Y. Each edge has capacity 1. Finally we run the FF algorithm. This gives us the size of the maximum matching (since the capacities are 1, each node can appear at most once). We can then use the flow to find the matching. We can find this matching in O(mn) time. |
| | |
| | Readability: 8 |
| |
| ===== Section 7: Extensions to the Maximum Flow Problem ===== | ===== Section 7: Extensions to the Maximum Flow Problem ===== |
| |
| We can also use our algorithm in other more complex problems. Suppose we want to solve a circulation problem. In this problem, we have supplier nodes and demand nodes. We want to satisfy the demand by moving the flow from suppliers to demand nodes. We can also have flow move through these nodes, but suppliers ultimately want to supply and demand nodes want to receive. | We can also use our algorithm in other more complex problems. Suppose we want to solve a circulation problem. In this problem, we have supplier nodes and demand nodes. We want to satisfy the demand by moving the flow from suppliers to demand nodes. We can also have flow move through these nodes, but suppliers ultimately want to supply and demand nodes want to receive. We can apply our algorithm to solve this problem by slightly modifying the existing graph. We attach a single source node that points to all the suppliers and a single sink that all the demand nodes point to and then run the FF algorithm. This will return the maximum flow. If this maximum flow is the same as the total supply, then we can remove the source and sink and be left with a circulation. Otherwise, a circulation does not exist. |
| | |
| | Networks can also have lower bounds for edges that require a certain flow. Suppose we have a circulation problem with lower bounds. Then we can just reduce the maximum capacity of each edge by the lower bound and reduce the demand of each node by L = lower bound of edge in - lower bound of edge out. Now we have a network without lower bounds and the idea above can be applied. |
| | |
| | Readability: 8 |
| | |
