Discrete Mathematics - Network Flow Flashcards
1
Q
What is a cut
A
Its a set of arcs whose removal disconnects a network into a Source Set (S) and a Sink Set (T)
2
Q
What is the capacity of the cut equal to
A
The sum of the weights of the arc that have been cut
3
Q
What is the main Network Flow Theorem
A
The Maximum Flow = Minimum Cut
4
Q
What is the Conservative Condition
A
Total Inflow = Total Outflow
5
Q
What is the Feasibility Condition
A
The flow into an arc cannot be greater than its capacity
6
Q
A
