Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:donohuem:chapter7 [2018/04/03 02:24] – donohuem | courses:cs211:winter2018:journals:donohuem:chapter7 [2018/04/03 03:13] (current) – [7.7 More on Maximum-Flow] donohuem | ||
|---|---|---|---|
| Line 2: | Line 2: | ||
| - | ===== 7.1 Maximum-Flow ===== | + | ===== 7.1 Ford-Fulkerson Algorithm |
| For our purposes, we define a flow network as a graph G with a source node s and a sink node t with each edge e having a non-negative capacity ce. There are also two important conditions: the capacity condition and the conservation condition. The capacity condition restricts a flow of an edge to be less than or equal to its capacity. The conservation condition assures that, with the exception of the source and sink nodes, the flow into a node v equals the flow out of v. Thus, our problem is to maximize the flow within a flow network. The algorithm that achieves this does so using a residual graph, a clone of the original graph G with augmented edges indicating flow. Thus, the overall algorithm, the Ford-Fulkerson algorithm, combines an two different functions. One for augmenting an edge, and another for computing overall flow: | For our purposes, we define a flow network as a graph G with a source node s and a sink node t with each edge e having a non-negative capacity ce. There are also two important conditions: the capacity condition and the conservation condition. The capacity condition restricts a flow of an edge to be less than or equal to its capacity. The conservation condition assures that, with the exception of the source and sink nodes, the flow into a node v equals the flow out of v. Thus, our problem is to maximize the flow within a flow network. The algorithm that achieves this does so using a residual graph, a clone of the original graph G with augmented edges indicating flow. Thus, the overall algorithm, the Ford-Fulkerson algorithm, combines an two different functions. One for augmenting an edge, and another for computing overall flow: | ||
| Line 15: | Line 15: | ||
| The overall algorithm is O(m). The overall readability of the section was 6/10. | The overall algorithm is O(m). The overall readability of the section was 6/10. | ||
| + | |||
| + | |||
| + | |||
| + | ===== 7.2 Minimum Cuts ===== | ||
| + | This section is entirely concerned with analysis of the Ford-Fulkerson algorithm. There are several important principles applied within the algorithm. For starters, we know that the flow returned by the FF algorithm is the maximum flow. We know this by a very complex proof that utilizes cuts, or partitions of the nodes within a graph. More specifically, | ||
| + | |||
| + | |||
| + | |||
| + | ===== 7.5 Bipartite Matching ===== | ||
| + | In this section, we revisit the Bipartite Matching Problem where we wish to find the largest bipartite matching in a graph G. The algorithm that achieves this builds off of the concept of flow networks. The algorithm takes an undirected bipartite graph and constructs a directed flow network from it. Interestingly enough, the size of the maximum matching in G is equal to the maximum flow in the corresponding flow network graph of G. The algorithm is more expensive, however, running in O(mn) time. Overall the readability of this section is 7/10. | ||
| + | |||
| + | |||
| + | |||
| + | ===== 7.7 More on Maximum-Flow ===== | ||
| + | The Maximum-Flow problem can be extended | ||
| + | |||
| | | ||
