Now we have the statement of the theorem, so what else can we do? We should provide the proof. So here are the proof. And to provide the proof we start with understand our theorem in some special case. It's generally a good idea to give a theorem before proving it you should look at what the theorem really states and understand this better you should consider this case, this case, that case and so on. But in our it's not only an example but also a tool for the general case. So it's often also happens to you after you prove some special case you can reduce the general cases as a special one. Anyway what is a special case? It's a case where there is no flow, it is not possible to send any oil from source to destination, no positive flow. And the theorem for maximum flow is zero then and the theorem says that the minimal cut should be zero so there should be cut when there is no outgoing edges of positive capacity. So if there is no flow, there should be a cut, which make the flow impossible. Can you say why it happens? It's actually not difficult. If you think, you will guess this. Here is the statement again. And now we need to explain this. To explain this we introduce the node as a notion of reachable node. So by definition, the source node A is reachable, and every node which can be reached from a reachable node by an edge of positive capacity is reachable. So, we just somehow look where the oil can connect the pit arrive. Just the independent of quantity. Just when there is a chance to send some oil. And technically, you can say that we have considered directed graph made of edges of positive capacity and you look what vertices are reachable from A in this graph. And by assumption, our B is not reachable. There is no path from A to B, which goes through edges of positive capacity. And y, then there is a cut. So if B's reachable, let me say it in another position. If B's reachable, then there is no zero flow. Let's look at this path from A to B with edges of positive capacity. Technically, it can happen that this path is not simple path. It goes twice to some vertex or even through some edge. But of course, you can delete all the cycles and so you get a path without when you never come to the same vertex. And then you can send if the capacity is a positive integer you can send at least one unit of oil along this path. So if the vertex B is reachable then there exists a non-zero flow and an integer case is one unit flow is possible at least. But what if B is unreachable? The other case. Then there is the zero cut. And it's easy, what is this cut? Do you see it? Of course it is just made of unreachable vertices. By definition, there is no edge going of positive capacity going from reachable vertex to a non-reachable. So just make a section, we know that this capacity zero and A's inside and B's outside, so this is just the cut we look for. So our special case is now completely proven. So the cut, let me repeat the cut, is the set of reachable nodes from A and reachable means reachable on the graph of positive capacities. So the special case is considered, now we want to go to the general case. And the proof idea is very simple, in one sentence we increase the flow until we will find a bump into an obstacle and this obstacle is minimal cut. But while we should of course explain what we do. So our special case is a good start, either we bump into this zero cut immediately or we can increase the flow and as we have discussed there is one flow of size one. So it's a good start, but maybe it's not optimal of course, and we should increase it further. So this is our special case. What special case says, and then we repeat this procedure somehow and each time we increase the flow by 1 until we bump into some matching cut. Of course, as we don't know why we will bump into some matching cut. And we need to explain what happened. And this explanations in just the reduction to our special case and the tool of this reduction is what called residual network. A network of reserves, per se. And let me explain, I prepared some picture for that. What is the reserve? So imagine we have an edge somewhere in the graph is just a small edge in a big graph. And imagine that its capacity and this is flow. So you see that this edge is not fully used. We can still send some oil here, and maximal oil we can send is two. We can send more flow. But also, so to say, we can decrease the flow by ten here. Why ten? Because we have now plus four and we can have six, we can stop this four and use this six in other direction. Now we assume that this edge is symmetric. It's plus minus six. It's not clear from this picture so the edge is symmetric. It's six in any direction, now we can use it in four in one direction and then we can switch direction and make six the difference between plus four and minus six is ten. So this is this residual network. It has capacity two in this direction and capacity ten in the other direction. Actually, it's not so unreal. There are long stories when there is some guest sending from A to B, and then somebody want to send the guest from B to A, the other company. And the simplest thing is to just decrease the flow and use the guest where it's not sending it. But there are a lot of legal difficulties with that. But in our mathematical model, there are no legal problems. And so we have a reserve residual edges of 2 and 10. And for the general case I prepared the slide. This exact situation we had. We had the flow 8, and so here was 4 goes here and 4 goes here and capacities are 6, 4, 4, 6, 1. And we just compute the residual network, we can send two more or we can send them here or in this here we can send anything, but in the back direction we can send even 8, and also here things are symmetric. And here it's not used so we can send one in any direction we want. And now, what is the meaning of this residual network? And there are three things, two things sorry. So, the first, what is the flow in the residual network? A flow is just increased compared to the current flow. So we have an original network and there is the sum current flow and we look how much this current flow can increase or decrease. What are the changes in the current flow? And the bounds for these changes are shown in the residual network. So if there is a path in the residual network from A to B this means that we can increase the flow in our original network by the capacity of this part. This is about flows and another thing is about cuts. So if we have some zero cut. Here we don't have a zero cut but in our second example we would. If we have a zero cut in the residual network, it means that all the edges that go across this cut in the right direction are fully used, because they have zero capacities in the residual network, which means that they are fully used in the original network. So this is a full cut, and so now we see that we consider the residual network. There are two cases, either there is a zero cut and then we have a cut. We bump into some cut in the original problem. Or there is a part in the residual network and we can increase our flow along this part by one. So we increase our flow by one, and that's what we want. So let me repeat the story, the pieces together. So that's kind of algorithm, so we start with a zero flow and then we repeat the following procedure. First, given a current flow we compute the residual network. First time it will be the third residual network. And then we apply our result about specialties. Either we find a path which can improve flow, which is called the augmenting path, or we find a zero residual cut. And in this case, the cut means that in the original network our flow bumped into a minimal cut and maximum flow are the same. And then we stop. And after that we have maximal flow into minimal cut that met each other. So this is the algorithm. You should think about this. It's so simple that there is not clear where is the trick. But really there is nothing counter intuitive. We do whatever we should do and we are done. It's very easy if you know how to prove it. Only thing we should say that's also obvious for integer capacities, the termination. So if capacities are integer then each time we increase the flow at least by one. We know that in this residual network we have a path and we can assume that it doesn't come back to the same vertex, so we can just send at least one unit of oil along this part. So we increase the flow at least by one, and so we cannot do it infinitely long, we will finally stop. And also, as this algorithm shows, that for integer capacity network our maximal flow is also integer, which is important for some application.
