[MUSIC] [SOUND] Hello everybody. I was looking forward very much to today because today's lecture and the next is my favorite in the whole course. You remember in the very first lecture I showed you an example about network flows. About these transportation networks, where you have a start and a target and you want to transport some goods from left to right. So these goods could be data on a computer network. It could be trains or whatever trains transport in the rail network. It could be oil in a network of pipelines, where you want to transport as much as you can from an oil well to the oil refinery. It really doesn't matter from the viewpoint of discrete math. It's simply a graph with two vertices, the start and the target. So here, for example, we route one unit of flow, flow is whatever commodity we are talking about, along this red path. And we have the blue path, we have the green path, and note that the green and the red path intersect. But this is fine because what restricts the capacity of the network are not the nodes but the links, so the edges are restricted in capacity. This is what you define to be the capacity of a network. It is the maximum number of independent paths from S to T. So now if you want to sabotage the network, you can place these little bombs on these four edges, and if you destroy these edges you have successfully disconnected it. So now you cannot go from start to target anymore. This is what we define to be the vulnerabilities. The minimum number of edges you have to remove in order to disconnect the network. And it's pretty obvious that the capacity is, at most, the vulnerability. In this specific network, you can change the green path, we can change it, you can make space, if we get another path. And now you see here, in this network, the capacity and the vulnerability are actually the same number, in this case, four. And this turns out to hold in general, that's known as the max-flow min-cut theorem. And today I want you to introduce network flows and cuts in general. And then in the next session we are going to prove this very nice theorem. Okay, in general, the setup is a little bit more complex. But what we have seen now, in graphs, it's actually not very difficult. So the first thing is, we actually have directed edges. So it could be that you can transfer something from A to B but not back, okay, like one way roads. The other thing is not all links have the same capacity. It could be that some links have capacity 4, some have capacity 1 and so on. So in general, a flow network is a directed graph together with a source vertex and a sink vertex t and edge capacities. These are the black numbers next to every edge. Now, if we have these edge capacities, we can actually generalize and say, c is actually a function from V times V into R, Where we just defined c(u, v) to be 0. Whenever (u, v) is not an edge. Conversely, if you give me a function from V to V into R, a capacity function, I can just say, well, E is the support of it. So E is the set of all (u, v), That have positive capacity. It is sometimes easier to think of c as a function from V times V and not as a function on edges. Okay, so here is an example of a flow. There is a path and, okay, here is a path, here is another path, and a quick route, one unit of flow through the blue path and 0.5 units of flow through the red path. So this is possible, right? Again, of course, also choose this, I can split the blue flow into 0.1 and 0.9. And then you see, along these edges, you have a 0.6 flow. So actually, we can forget about colours and we can just say, well whatever entrance this vertex has to leave it, but we don't really care which part of the oil goes here and which goes here. It's just the inflow has to be the outflow. Okay, so we can forget about these colors. At this point, I think we should formally define what a flow is. So now, I think the content of a flow deserves a proper mathematical definition. So, if you have a flow network (G, s, t, c), a flow is a function from peers of vertices into rear numbers that satisfies the following constraint. First of all, it should never exceed the capacity, obviously. This is called a capacity constraint. Second, whatever flows into vertex V, has to flow out of vertex B. There is no flow that is lost at V and nothing is generated at V, right? Okay, so this inequality has to hold for all vertices except the source and the sink. However, it turns out for a mathematical treatment, it pays off to reformulate this constraint as follows. So first of all, we introduce something that's called skewed symmetry. We say the flow from u to v is the negative value of the flow from v to u. So whenever we have a flow from u to v, let's say we have 4 units of flow, then we define the flow from v to u as -4, okay? This might strike you as odd, but it's actually a convention that is also used when people study electricity networks, like how current flows between certain points. And it just makes the treatment much easier. So, now for example, we can reformulate flow conservation as follows. The total outflow at v should sum up to 0. Right, that's the definition of a flow. And the value of a flow, which is what we want to maximize is the outflow at s. Actually, here is a typo, my god, it's the flow s to v. Okay, that's the value of a flow. Okay, so let me give you some examples of a flow. Here is one. There are weird things happening. So here, for example there is something running in circles, or here you see there is something flowing back into the sink. Again you might think this is weird, but if you look at our definition, this is perfectly allowed. What I show here is a flow. Also, you might have something like this, so here stuff is also flowing out of the sink, back into the network. Again, this is a flow, because it satisfies all our conditions in our definition. So here, in this flow, let's see, what is the network, what is the value of this flow? Well, you see here, there is 1 unit flowing out here, and 0.5 flowing out here. So, 1.5 is flowing out of the sink. And here, it's 0.9 and 0.6, so 1.5 units are flowing into t. So these are the same values, which is almost obvious, right? Whatever flows out of the source has to flow into the sink. Because nothing can get lost in the middle of the network and nothing can be generated. So, we have the following lemma. It's almost obvious but let's try to prove it formally. Proof goes as follows. Let us sum up the flow of all peers of vertices. On the one side, I can say, well, this is minus v, u. Now we can actually exchange the order of summation and we see that this here, Is actually the same as this. So you can have a number that equals its negative part, therefore, it must be 0. On the other hand, we can split the sum by saying, well u, the vertex u could be s, it could be t, or it could be something else. And then we get this. So here we sum of all remaining vertices, in v without s and t. But now you see this term here, this sum is the total outflow at vertex u, and by flow conservation, it's 0. So only the two first sums survive and I can rewrite the second sum by skewed symmetry. And I get the following. So now you see, this here, is the outflow at the source. This is the inflow at the sink. And their difference is 0. This finishes the proof. Cool, again, here we have a flow. It's not the best flow. Let's ask our question, how can we prove upper bounds? That's a whole large would make our flow. So, note that all the flow must go through one of these edges. And therefore, it seems obvious that the flow can not be larger than this, which is 10. Alternatively, I could choose this, Large set. And now you see, all the flow has to pass through one of these edges. And therefore, it cannot be larger than 2 + 1 + this. Which is 7. So, this method gives us, this is a tool how to prove upper bounds on the value of a flow. And again, this is very important, so let's come up with a mathematical definition. This is called a cut. So a cut, or more specifically, an s-t cut is a set of vertices that contains s but not t. And the capacity is defined to be the total capacity of edges crossing this cut. So we have a set S here, we have V\S here. t is over here, s is over here. And if you sum up all the capacities, you get this. And if you sum up all the flow, You get this. You must be careful with flow because if something is flowing back, let's say if 4 units of flow are flowing back, then actually this counts s -4 units of flow, flowing forward. So you have to take this into account as well. All right, so this is the capacity of s and f of s. So here is a lemma, it says the value of a flow is at most the capacity of S. And this is basically also what we have seen in the beginning, it says that the capacity of a network is, at most, a vulnerability. So the capacity of S here, is a generalization of our concept of vulnerability. How do you prove this lemma? First of all, the value of f is everything that flows out of s. And this equals everything that flows out of capital S. And I don't prove this, that's an exercise for you. The proof is very similar to the summation we had a couple of slides ago. But if you have this, we see the sum can be at most the sum of the capacities by capacity constraint. And there you have it. The value of the flow is, at most, the capacity of the cut. Okay? And here is a surprising theorem. It says, there is a flow and a cut such that these values match. Then this must be a flow of maximum value, that's called a max flow. And this must be a cut of minimum capacity, it's called a min cut. So the theorem tells you that a max flow equals the min cut. These two numbers coincide, they are the same. So this is the famous max-flow min-cut theorem. And in the next session, we're going to prove that. For today, we are done. Thanks. [MUSIC]
