[MUSIC] Hello everybody. Today, as promised, we will proof the max-flow min-cut theorem. As a reminder, last time we defined what a flow network is and what a flow is. So a flow is a function satisfying certain constrains, the capacity constraints, skew symmetry and flow conservation. And we also define cuts, which are best pictorially drawn like this. The capacity of a cut is the total capacity of the edges crossing it. We have proved the Lemma that the value of a flow can never be larger than the value of any cut. And today we are going to prove that there is a flow and a cut such that these two values actually coincide. As a preparation, let's look at this very simple flow and network. We can find the path from s to t and route one unit of flow through it. After we've done it, let's pause for a moment and think, what is left of our capacities? So you can, for example, see here, this edge has capacity 2 and we used 1 unit. So, there should be 1 unit left. Here we used 1 unit so nothing should be left and so on. So, this depicts what remains. All right, so in this network we see there is no path left from s to t. But does that mean we have found the optimum? No, not really, because we can do something that is slightly weird, but actually we can do it. We can start from s, go through here, 1 unit of flow. But now instead of going here which we can't because this edge is already used, we can push back flow and use this edge, so to say, and continue around here. If this is confusing, don't despair, we'll make everything formal in a minute. Basically what it tells us, whenever we use, we route flow here, we can use the edge in the backwards direction in the next step. So actually, the remaining capacities should look like this. We don't only have the green edges, we also have this brown back edges. And in this network, let's stick to our convention that if something has zero capacity, then it's not an edge anymore. So, this net work should look like this. Okay, so now in this network we can find another path like this, In route one unit of flow. So let's try to combine this, we have 1 unit of flow here. And 1 unit of flow like here. And now let's see how this combines to a flow. And this gives us 1 unit, 1, 1, 1. And this gives us 1, 1, 1. Now we have to be careful, because actually we are sending flow in the other directions. So we should put a minus 1 here, 1, 1, and all together, you can see that this gives us a flow and the flow kind of looks like this. One unit here. One unit here. So this business of inserting the edges going back, might strike you as weird and unusual. So let's try to formally define it and see that it makes sense. Well, if you have a flow network and a flow, we define the residual capacities as follows. Cf is c- f. So, remember, what is c and f? C and f are functions from V x V into R, which means we can subtract and add them as functions, right? And if we take c- f as a function, we get a new function, which we call cf. And this is the residual capacity. And here is the core Lemma if you have a flow in G. And now we have a flow F prime in GF. Then you can combine them and get a flow in G. That's what we did on the slide before. And now we are going to prove that this works in general. So what we have to do is we have to check that this new function f +f' satisfies all constraints of a flow. It fit over definition of a flow. So first, We have to show the capacity constrain. We have to show that this is at most c. And indeed, f prime, Is a flow in gf. So it respects the capacity constrains and it is at most cf. By definition, cf is c minus f and it nicely cancels out and here you get it. All flow respect the capacity constrains. Second, we have to show skew symmetry. But this is really a simple exercise, so I'll let you do it. And third, we have to show flow conservation. So,if you take a vertex V and you sum up this value, You can actually tear this sum into two parts. In this part, And we see because f and f prime are both flows, this is 0+0. The flow conservation also holds for the combined flow, right? Okay, now you see the way we defined flow actually made it super simple to prove this Lemma. So, again here, let's practice this definition we have a network, we have a flow. Here is our residual network. Good, so now we are ready to prove the maximum in cut theorem. So, what we do, we choose a max flow f, we just suppose we have it. And actually, I should warn you, I'm cheating just a little bit because a gentlemanly assume that there is a maximum flow. But this is not completely obvious, right? I should prove to you the existence of a maximum flow. It could be that it goes on and on and on, you find larger flows but actually it doesn't reach this limit or something. So, I would, technically speaking, I'm cheating you here a little bit. However, for an important special case, we will see a proof of this at the end of today's lecture. For now, never mind, let's just assume f is the maximum flow. The second, Let's consider the residual network. I claim that this network has no path from s to t. And indeed if it did, We could take such a path, And remember our convention every edge has positive capacity, otherwise it's not an edge. So now we have this path and we can just route a small amount of additional flow and we would get a larger flow. So we could choose a flow fp along this path. And then f+fp, Would be larger than the value of f which is a contradiction because we assume that f is a max-flow. Okay, so there is a no path. So it looks like this, we can define s to be the set of vertices v such that there exists a path from s to v in Gf. And by point two, we know that t is not in s. But, obviously, s is in S. So, what does this tell us? It tells us that s is a cut. Also, If u is in s and v is in v minus s, then we know that the residual capacity of uv is 0. Why? Well, because there is a path from s to u. If we had the edge from u to v, then there would be a path from s to v too, right? So by definition of s, there is no residual capacity crossing this cut. And now, the prove basically finishes itself. The value of f, as we have seen as we have proved in an exercise, is this sum. But now you see, Because cf = c-f, we have that c(u,v)- f(u,v) = 0, for all such vertices. So the capacity equals the flow. For all this edges crossing the cut, and therefore we get the following equality. And this is essentially the capacity of the cap(S). And there you have it, we have a flow, There it is. All right, we have a flow f and we have a cap(S) and the value of the flow matches the capacity of S. So the crucial observation is that for all these edges here, the residual capacity is 0, and this means, the original capacity must actually equal the orig flow f, right? So here you have it. And this finishes the proof, but it does a little bit more, it also suggests an algorithm, how to find the maximum flow. For example, what you could do as long as you find a path, you take a path and you route as much flow as you can through this path. And then we take the residual in network, we, again, find a path and so on and so on. And if this ends, then there is no path left you can define a set S as we just did before and then f is a max flow and S is a min-cut, all right? So this algorithm, if it terminates, it returns max flow in min-cut. Now if we can prove that this algorithm terminates, we have also proved that there is a maximum flow. I should say, this algorithm is called the Ford–Fulkerson method. And if we assume the following, if c(u,v) is an integer for every edge, then whenever we find a path, we can route at least one unit of flow. So the belly of the flow increases by one in every iteration which means it must at some point terminate, because it cannot go to infinity because everything is finite. So for integer capacities, everything is fine. The algorithm terminates. It proves that there is a max flow and it returns a max flow in the min-cut. However, If, Our capacities are real numbers, It's not that simple. Actually there are examples where this algorithm does not terminate. So, we have to fix it. And the fix is quite simple. We choose this path here wisely. Choose p to be a shortest s-p path. And this fix, it's known as the Edmonds-Karp algorithm. And you can show, That it has utmost n times m iterations. So here, n is the number of vertices and m is the number of edges. And every iteration requires that we find a shortest path which we can do in linear times, for example, by. So this gives us an n times m squared algorithm. But proving the theorem actually is slightly nasty, so we are not going to do it in this course. And actually, if this was an algorithms course, we could continue for the next three weeks just talking about algorithms for maximum flow, making it more and more efficient, but we're not an algorithms course, we are a discrete math course. So we are not going to do that, instead, we are going to talked about applications of this beautiful theory. So here's an application that becomes clear if you see this algorithm. If all your capacities are integral, then this algorithm will return a max flow. But even more, the max flow will have integer values on all pairs, right? Because every time you find a path, you add at least one unit, you add an integer amount of flow. So in the end, the flow will only contain integer values. And this is a very important observation that we are going to use next time. All right, I'm done for today. I hope you enjoyed it and I'll see you next time. Thanks. [MUSIC]