Flashcards
Network flow basics
Cards in this deck (17)
- 1What is the capacity of an edge?The maximum flow of that can pass along an edge
- 2What is a source?Where all edges are directed away from a vertex
- 3What is a sink?Where all edges are directed towards from a vertex
- 4The sum which flows into a vertex = ....The sum that flows out of a vertex
- 5Which special kind of vertices are allowed an unbalanced flow?Sources and sinks
- 6What is a cut?A continuous line which separates vertices, but must not pass directly through vertices
- 7Why would we use a cut?To see if a flow is the maximum possible flow
- 8What does the maximum flow - minimum cut theorem state?Minimum cut = maximum flow
- 9—15+3+4+11 = 33
(ignore 6 as going away from sink) - 10Remember to only include the values of a cut going in.....1 direction from one side to the other
- 11What 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
- 12When finding a cut, what should you look out for?Saturated edges
- 13When we make a cut, we should only add up the edges'...Capacities
- 14What is a super-source?A single source which flows into the original sources
- 15What is a super sink?A single sink which has all original sinks directed into it
- 16The flows in/out of super sources/super sinks should be.....Equal to all the original sources/sinks
- 17How 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