Maximum Flow Assumptions



Download 1 Mb.
Page2/6
Date02.05.2018
Size1 Mb.
#47333
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
(6.5)
Then 6.5 minus 6.3

Recall that 6.3 says:

Gives


or



Thus we get


Download 1 Mb.

Share with your friends:
1   2   3   4   5   6




The database is protected by copyright ©ininet.org 2024
send message

    Main page