maximum flow minimum cut Flashcards
1
Q
what are the steps to finding the maximum flow?
A
- identify the source (S) and the sink (T)
- find paths from S to T
- identify the sturated arcs
- find the excess capacities
- find alternate routes from S to T that do not include saturated arcs
- continue until no more paths
- the maximum flow is the total volume leaving the source (also the total volume coming into the sink)
2
Q
Find the maximum flow
A
3
Q
What is a cut ?
A
A set of edges that separates the networks into two parts, one with the source and the other with the sink
4
Q
How can this example cut be defined in vertices
A
5
Q
What is the capacity of the cut?
A
The sum of all the capacities of edges that are directed from the part containing the source S, to the part containing the sink, T
6
Q
What is the capacity of this cut?
A
21
7
Q
What is the maximum flow minimum cut Therom?
A
The value of the maximum flow = the value of the minimum cut
8
Q
what is a super source super sink?
A
- super source is where all sources spout out from
- super sink is where all sinks lead to
9
Q
A
10
Q
A
The minimum cut has as many arcs that are saturated. A cut must separate the sink from the source entirely
11
Q
A
12
Q
A
13
Q
A
14
Q
A
15
Q
A
