16220093
| Question | Answer |
| What is the capacity of an edge? | The maximum flow of that can pass along an edge |
| What is a source? | Where all edges are directed away from a vertex |
| What is a sink? | Where all edges are directed towards from a vertex |
| The sum which flows into a vertex = .... | The sum that flows out of a vertex |
| Which special kind of vertices are allowed an unbalanced flow? | Sources and sinks |
| What is a cut? | A continuous line which separates vertices, but must not pass directly through vertices |
| Why would we use a cut? | To see if a flow is the maximum possible flow |
| What does the maximum flow - minimum cut theorem state? | Minimum cut = maximum flow |
| 15+3+4+11 = 33 (ignore 6 as going away from sink) | |
| Remember to only include the values of a cut going in..... | 1 direction from one side to the other |
| What could we do to ensure we select the correct values when using a cut? | Colour both sides in different colours, and select the values going from the left colour into the right colour |
| When finding a cut, what should you look out for? | Saturated edges |
| When we make a cut, we should only add up the edges'... | Capacities |
| What is a super-source? | A single source which flows into the original sources |
| What is a super sink? | A single sink which has all original sinks directed into it |
| The flows in/out of super sources/super sinks should be..... | Equal to all the original sources/sinks |
| How would we deal with a restricted flow edge? E.g. 9>--A-->8 (A has capacity of 5) | Replace A with 2 new vertices and put an edge between them with the stated capacity: 9>--A1-->5>--A2-->8 |
Want to create your own Flashcards for free with GoConqr? Learn more.