First, we should define things more mathematically, we speak about oil and pipes and so on. But we want to be more formal, so let's fix the framework for that. So what is network and what are the capacities? So the network is a graph. Just you can even forget about graphs. The vertices of the networks are just numbers one, two and up to n, so we have n vertices. And one of this vertices is declared as a source, and some other is declared as a destination, should be a different vertex. And for every two vertices i and j, we have some number capacity. So somehow this is how much oil can be sent from i to j. So you just form and adjust a non-negative number, which we assume to be an integer. And for simplicity, we don't consider the graph. We'll just say that if there is no pipe, then in the area, we have a zero element. So no pipe, and pipe of capacity is zero, is the same thing. Okay. And what is important, that we allow non-symmetric things. So if we have i and j, we allow that situation when we can send more, i is not here. We can send more from i to j, then 10 and only two in other direction. And why such a strange thing? Because it's useful for intermediate steps. So as usual we need to generalize this statement to prove it. You will see how it works. This is needed for the analysis. So imagine in real life, you can have two pipes with the same source and destination. In our table, it doesn't make sense. We do not allow several pipes but of course we can just add up the capacities of all the pipes and say there's one bigger pipe of a combined capacity. So it's not allowed, but it doesn't matter. It can be easily and it's used to this in case of one pipe. And the last thing also in the table, that is a diagonal element, pipe from i to i makes no sense, so we decide that this elements are zero. So this is what is a network. We fix the number n, we see what is the source, what is the destination and to specify the area of capacities, just an area, and there are some restrictions. So this is a network and then we should explain what is the flow and what is a cut. To next slide, I prepared for that. What is the flow? Flow is just another area which says how much oil is sent actually, not what can be sent, but what is really sent now. And so it's also number, for every two vertices i and j, we see how much oil is now moving from i to j and it should not exceed the capacity of the pipe. This is why the capacity are needed. And there is some rule which is taken from electricity rules. So if there is a flow from i to j, we say that this is of one unit, we say that this is the same as the flow of minus one unit, from the j to i like positive electricity to negative electricity. So we assume that this f is symmetric with changing the sign and this is convenient for our purposes you will see why it's convenient. And first we can know that this implies that if i is equal to j here, we see that this should be as f[i,i] should be zero. And now we should return to our condition that no oil is lost. So what does it mean? So if we take some vertex i, and let's look at all the pipes that go out of i and each of them carries some amount of oil, but they should compensate each other and using our sign rule, we can see that the total sum of all flows for all the edges should be zero. So for every i, the sum over j should be zero, formally. Here is also j could be equal to i, but this is zero anyway. So this is the condition and of course this condition should be everywhere except for source and destination, because there are external consumers and producers there, and for destinations, the amount of oil which is sent is just for source and for destination, the amount of oil which comes is here. So, the law of conservation of matter says that if nothing gets lost in the middle, then all the oil should just come to be. So that is the same number. You can prove it formally but it's more or less obvious. So this is what is flow. And the last ingredient is cut. So what is cut? It's our technique how to prove that the flow is bounded. How to prove that, we can have a flow bigger than something, and we find the cut of boundless capacity. So what is the cut? Actually we cut between A and B. So there are two paths, but we will consider for simplicity of definition only one path, the path that contains A but not B. So there are internal vertices and external vertices in terms of the cut, and the total capacity of a cut, is just we look at all outgoing edges, edges which start if there's some C and end outsides. And the sum of this their capacities is just the total capacity of a cut. And the same conservation of matter means that whatever the amount of oil which leaves A, is the same amount which crosses C, and the same amount which arrives in to B. And so any total flow is bounded by the total capacity of any cut. And Fold and Fulkerson proved that this inequality, this never exceeds. Sometimes is an equality, so sometimes the flow is equal to cut, the maximal flow is equal to minimum cut. So let let me draw some picture which should explain this. So what is the obvious path of Fold and Fulkerson. So this is real line and there are some possible flows. It's kind of symbolic of course, picture, and there are some possible capacities of some cuts. And what we know that every flow is bounded by every cut. But what the theorem says is Fold and Fulkerson what they guarantee us, that there exist actually these two things should match. So there is some flow and some cuts which give the same number. And therefore, we know that this is optimal because we know that flow, no flow can exceed this cut and some flow achieves this. So this flow is maximal, and the cut is minimal for symmetric reasons. And this is the statement Fold and Fulkerson theorem of maximal flow equals minimal cut. This is if you want to say it in four words it's what you should say.
