Next we'll look at a proof that the Ford-Fulkerson algorithm is valid, known

as the max-flow min-cut theorem. It also proves that the two problems are

equivalent. We need a couple more definitions to, to

show, first we want to show the relationship between a flow and a cut.

So in this case we've got a cut where T is on one side and all the other vertices are

on the same side as S. And what we talk about is the flow across

the cut. And that, what that is, is the sum of the

flow on it's edges that go from S to T, minus the amount that goes the other way.

That's the flow across the cut. So this, what's called the flow value

lemma is that, if you have a flow then for any cut.

The net flow across the cut is the value of the flow.

That's called the flow value lemma. Doesn't matter what the cut is, this, this

is a max flow, a flow with value 25 and every cut is going to have 25 flowing

across it. So, this cut, this is a more complicated

cut where S and these three vertices are colored.

So the flow of a, across that cut has to take the all the edges that go from a gray

vertex to a white one. So, there's ten plus ten, plus from a gray

vertex to a white one, five plus ten + 00. Then, we have to subtract off the edges

that go from a white to a gray one. So we add up all the ones that go from

gray to white. Ten + ten + five + ten + zero + zero and

subtract off the two that go from a white to a gray and, still, the net value across

the flow is the same, the value of the flow.

That's the flow value lemma that gives a particular relationship between flows and

cuts. And that's not too difficult to prove by

induction on the size of one of the sets. For example, if we do an induction on the

size of the set containing T, it's certainly true when that set consists of

just T, because the value of the flow is exactly equal to the edges coming into T.

And then to prove by induction, you can move any vertex from A to B in local

elibriums, local equilibrium's going to make sure that the flow value limma is

true. And so that's, that's how it's proved.

And a corollary of that is that, that outflow from S is equal to the inflow to

T, which is equal to the val, all equal to the value of the flow.

And that's also easy to see in all of our examples.

So to get started let's, let's look at what's called weak duality.

If, F is any flow at all, in network. If AB is any cut.

The value of the flow is going to be less than or equal to the capacity of the cut.

So in this case value of flow is 27 and the capacity of the cut is 30.

Value of the flow is always less than or equal to the capacity of the cut.

And well the net flow across a cut has got to be less than less than or equal to it's

capacity 'coz it's at least that and then if there's any edges going the other way,

they get subtracted to compute the lugnut flow.

So a weak duality, is that, that's an easy thing to prove.

So what we want to prove are these two theorems.

The max-flow min-cut theorem is really two theorems combined called the augmenting

path theorem that says the flow's at max-flow if and only if there's no

augmenting paths, and that the value of the max-flow equals the capacity of the

min-cut. In any network.

And the way we prove that is to prove that the following three conditions are

equivalent. Again this is a proof that's a little

intricate logically. It's worthwhile for me to go through it,

but to really understand it you're going to need to read it carefully and convince

yourself that these three conditions work. So here's the three conditions that we're

going to prove our equipment. First one is, there is a cut, there's some

cut whose capacity equals the value of the flow.

The second one is that f is a max flow. So if there's a cut whose capacity equals

the flow then f is a max flow. And if f is a max flow there's such a cut.

And then the third one is that there's no augmenting path.

So we're going to prove those three conditions are equivalent.

And we'll do it with a little logic trickery.

So first we could prove that one implies two.

If there exist a cut capacities equals the value flow, then f is the max flow.

Alright, so suppose that we have such a cut, capacity is equal the value of the

flow then any other flow by weak duality, flow is going to be less than or equal to

the capacity of that cut, . In fact that cuts equal to the value of

the flow, so therefore, that's the maximum, max flow.

The value of any flow, if less or equal in value of f, so it's the max flow.

So that proves that one implies two. Okay.

Now we're going to prove two implies three.

One implies two, and also two implies three.

That also means one implies three. So in order to prove that we're going to

prove the counter-positive. So we'll prove that not three implies not

two. That is, if there is an augmenting path

then F is not a max flow. Well, that's pretty straightforward, then,

'cuz that's what we do in the algorithm. We could improve the flow by sending flow

along the path. So it can't be a max flow.

So that's, pretty easy. If that was a max flow, there's no

augmenting path cuz if there is an augmenting path, that's not a max flow.

So that's the, second, part of the proof. And now the third part of the proof, will

prove that three implies one. So, that'll give you, the circular logic

condition that proves that they're all equivalent.

So we want to prove that if there is no augmenting path, then there is a cut in

this capacity that equals the value of the flow.

So if there's no augmenting path. Then what we're going to have is a cut

where A is the set of vertices. That are, connected to S by an undirected

path with no full forward or empty backward edges.

And so there has to be such a cut if there's no odd many path.

S has got to be in A and T has got to be in B otherwise there will be a path from A

to B with no four, four front and empty backward with edges and the capacity of

that cut equals the net flow across the cut but all the four edges are fallen, all

the backward edges are empty so that's exactly equal to the value of the flow.

So if there's no augmenting path then we can demonstrate a cut whose capacity

equals the value of the flow and that is completes the proof of the max flow and

the cut theorem. Sorry.

Alright. So the one last step is if we have

computed a max-flow, then what we can do is compute the min-cut by computing the

set of vertices. And we can do that just by a graph search.

We start at S and if there's a path that has no, has a, a forward edge that's not

full then we follow that path and if we have a backward edge that's not empty, we

follow the path. And we just do a, a graph search to get to

all the vertices that we can reach with forward edges that aren't full, and

backward edges that aren't empty. And then we treat the full forward edges

and the back empty edges as not being there.

Otherwise, we do just a regular graph search.

And that's, going to give us, the, the, then the set of edges that define by that

cut are going to be the min-cut. So, not difficult to compute a min-cut

from a max-flow. So that's a proof of the augmenting path

there min, max-flow min-cut there.

Maxflow–Mincut Theorem

Algorithms, Part II

Rencontrer les enseignants