Network flows Flashcards
What is a source of a network flow?
a source is where the flow enters the network
What is a sink of a network flow?
a sink is where the flow leaves the network
What is a feasible flow?
a possible flow that considers circled values
What is a saturated network flow?
a flow at maximum capacity
What is an unsaturated network flow?
a flow that is not at capacity
What is a cut?
a way of describing bottlenecks:
a cut is a line across the network which splits the network into two parts: one containing the source and one containing the sink
What are cuts cross arcs?
they do not pass through nodes
the capacity of a cut is the sum of all the edges crossed by the cut which are directed from the source to the sink
What is the max flow- min cut theorem?
the value of the maximal flow is equal to the capacity of the min cut.
What are supersources and supersinks
when there is more than one source and more than one sink
