We continue our graph theory part and in this part we speak about networks which are graphs with capacities, you'll see what it is. To explain what we mean, we'll start with a simple example and the example is just about oil pipes. So there is a network of oil pipes, and here in the A, the edges, these edges are pipes. The numbers, these numbers are their capacities. So capacities how much oil can be transferred along this pipe in some unit time like barrels per hour or whatever. So this is our capacities. And we decide that oil is initially in A. That is the source of oil. And the destination, the place where the oil is needed, is B. And the goal is to move oil from A to B as fast as possible. So we want to find the maximal flow. It's more or less intuitively clear what you want and also clear that this problem is really important. Of course not only for oil, but for any commodity. I don't know, water or just the people who want to fled some, they want to go outside some area for, I don't know, for weekend or just the bytes in Internet cables and so and so. There are many cases when the setting looks reasonable, of course, they are more complicated but we consider the simple one with some clear physical meaning where both oil. So what are the maximum flow? So for example, this 10. Can you put 10 units of oil, proper unit of time, in this keep? So there are 6 and 4. So if you are careless, you just send 6 here and 4 here, but then, you find that the 6 come here. There is no way to send them in anywhere. So this is not a good idea. So you cannot do like this. But you can do the next slideshows that 8 is possible. So you see a very simple solution. Forget about the 6, and you will just send 4 in this path and 4 in this path. In total you get eight. And here, so there is a flow 4, 4, 4 and 0. Sort of this edge is not used at all. And here, capacities, they are maximum things. So you see that actual flow should not exceed the capacity. And you see that no oil is lost because all the 4 which come here go there, everything is okay. And the flow, the total flow is 8, 4 and 4 along this path and 4 along this path. So the question is can we do something better? What do you think? Look at this picture, can we do something better? And probably you see that we can, look, here there is some reserve, we use only four out of six so we can put a bit more oil here. But then we cannot put it here but we can put it down, and then here is the reserve, so something can be really improved. And if you think about this, you see the Flow 9. So flow from A to B is 9, because 5 goes here and then it's split into 4 and 1. And 4 come from here and this 4 and 1 are combined into 5 so the total flow is 9. The question is maximum or not? What do you think? So we see that it's possible and we know that of course it can be more then ten because six plus four is ten and you can not just send more from eight. But It can improve nine or nine is a maximal? What do you think? And nine is a maximal, and here is the explanation why, and this explanation is in terms of a cut. So imagine that A and B are in different states, and there is a boundary between the states, and there are three pipes, which are export pipes, we're going to say, which curves the boundary, and they have capacity for 1 and 4. So definitely if there are only three export pipes of this capacities, you cannot export oil faster. So nobody cares now what are the capacities here. If there are only 3 edges which cross the border, and they are capacities 4, 1, and 4, then, you cannot get anything more than the sum. So this dashed line here is a cut. And we compute the capacity of the pipes that cloth this cut and we see that there are the total capacities 9 and so no flow you cannot send more than the 9 units. And as an example, we fold 9 and this argument shows that this example really makes sense example. So now we are very well set with our case. We have a flow and we have a proof using a cut. We have a proof that this flow is optimal. Now, our goal is to do the same in a general case so we defined the notion of network which is graph plus capacities plus source and destination vertices. And we want to find the maximal flow. And to solve this problem we should provide an example of maximum flow and the proof of maximality. And the proof of maximality, we know a tool for that, it would be using cuts. So this is what you want to do. And this what was done by, rather long ago, by Ford and Fulkerson. And I will explain the theorem of these two guys. These are simplified keys. The simplification is that all numbers will be interjoined our setting, this theorem is true for any capacities and don't need to be integer. But the prove becomes more complicated so we are consider as simple case when the capacity are integers then the maximum flow will be also integer on this.
