Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2012:journals:garrett:entries:week_10 [2012/04/04 05:38] – 7.2 garrettheath4 | courses:cs211:winter2012:journals:garrett:entries:week_10 [2012/04/04 05:55] (current) – 7.7 garrettheath4 |
|---|
| A **flow network** is a specific kind of graph that has a node that is the source of some sort of traffic, directed edges indicating the maximum amount of allowed traffic between two nodes, and a node that is the destination of all of the traffic. The amount of traffic flow coming from the source node must equal the amount of traffic flow leaving the graph through the destination node. Additionally, the amount of flow into and out of any node must be conserved such that the amount of flow into a node is equal to the flow out of a node. | A **flow network** is a specific kind of graph that has a node that is the source of some sort of traffic, directed edges indicating the maximum amount of allowed traffic between two nodes, and a node that is the destination of all of the traffic. The amount of traffic flow coming from the source node must equal the amount of traffic flow leaving the graph through the destination node. Additionally, the amount of flow into and out of any node must be conserved such that the amount of flow into a node is equal to the flow out of a node. |
| |
| Given a problem that can be modeled with a network flow, we typically want to find the maximum flow of the graph. We use the **Ford-Fulkerson algorithm** to find the maximum flow of a network flow graph. It uses a residual graph and a growing set of examined nodes to progress toward the optimal solution of the network flow graph. | Given a problem that can be modeled with a flow network, we typically want to find the maximum flow of the graph. We use the **Ford-Fulkerson algorithm** to find the maximum flow of a network flow graph. It uses a residual graph and a growing set of examined nodes to progress toward the optimal solution of the network flow graph. |
| |
| |
| |
| === 7.5: The Bipartite Matching Problem === | === 7.5: The Bipartite Matching Problem === |
| FIXME | A **bipartite graph** is a graph in which there are two sets of nodes, or "sides" of the graph, that are not connected to each other but are connected to the other set. A node in one side of the graph can be connected to more than one node on the other side of the graph. |
| | |
| | The bipartite **matching problem** is a problem of finding the largest set of edges with distinct endpoints in a bipartite graph. This problem can be solved by adding a source node for the left side of the graph, link it to all of the nodes in the left side of the graph, add a destination node for the right side of the graph, link it to all of the nodes on the right side of the graph, and set all of the edges to be directed edges (pointing to the right, towards the destination node) to have a capacity of 1. Once you have this, you can run the Ford-Fulkerson algorithm on the network graph to find the largest set of edges with distinct endpoints. |
| |
| |
| === 7.7: Extensions to the Maximum-Flow Problem === | === 7.7: Extensions to the Maximum-Flow Problem === |
| FIXME | There are a lot of interesting problems that are based on the maximum-flow problem. One such problem is a network flow in which each node also has its own supply and demand. A node with a supply is a node that brings a certain amount flow traffic into the graph. A node with a demand is a node that acts as a destination node for a certain amount of flow traffic out of the graph. |
| |
| | Another problem is a network flow in which each edge has a lower bound in addition to its usual upper bound (capacity). In this kind of problem, simply add the lower bound of an edge to the demand of both of its endpoint nodes. |
| |
| |
| ~~DISCUSSION~~ | |
| |
| |
| | ~~DISCUSSION~~ |
| |
