Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| courses:cs211:winter2018:journals:holmesr:section_7.2 [2018/04/02 15:28] – created holmesr | courses:cs211:winter2018:journals:holmesr:section_7.2 [2018/04/04 01:07] (current) – holmesr | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Section 7.2 Maximum Flows and Minimum Cuts in a Network ====== | ====== Section 7.2 Maximum Flows and Minimum Cuts in a Network ====== | ||
| + | The next objective is to prove that the FF algorithm returns the best possible flow in G. One of the important concepts that will help us towards this goal is considering a cut and how it can place upper-bounds on the maximum-value flow. We can start off by noticing that the amount of flow leaving the cut minus the flow that comes back into the cut is the total volume of flow from the cut. In the case that the cut contains s, then this will be the same number as the amount of flow coming out of s. We can also say that the value of every flow is upper-bounded by the value of every cut in G. | ||
| + | |||
| + | There is a lot of discussion of minimum capacity cuts and I just don't understand what a minimum capacity cut is. This algorithm honestly doesn' | ||
