Maximum Flow Assumptions

Download 1 Mb.
Size1 Mb.
1   2   3   4   5   6
Flow across s - t cut

Property 6.1 The value of any flow is less than or equal to the capacity of any s - t cut

Property 6.1 implies that if we find a flow x that equals the capacity of some cut [S, ] then x is a maximum flow and [S, ] is a minimum cut.
We will reference this in the max-flow min cut theorem.

We can also state property 6.1 in terms of the residual capacity.

Suppose x has a flow value of v

x has a flow value of v + v v  0
Then 6.5 minus 6.3

Recall that 6.3 says:



Thus we get

Download 1 Mb.

Share with your friends:
1   2   3   4   5   6

The database is protected by copyright © 2023
send message

    Main page