# 13. Incremental Improvement: Max Flow, Min Cut

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=VYZGlgzr_As
**Transcript page:** https://www.withtranscript.ai/video/VYZGlgzr_As

## Chapters

- 0:00 — Chapter 1 (0:00)
- 3:39 — Chapter 2 (3:39)
- 6:56 — Chapter 3 (6:56)
- 10:19 — Chapter 4 (10:19)
- 12:49 — Chapter 5 (12:49)
- 19:31 — Chapter 6 (19:31)
- 23:20 — Chapter 7 (23:20)
- 27:59 — Chapter 8 (27:59)
- 29:06 — Chapter 9 (29:06)
- 31:20 — Chapter 10 (31:20)
- 34:30 — Chapter 11 (34:30)
- 38:01 — Chapter 12 (38:01)
- 47:28 — Chapter 13 (47:28)
- 48:47 — Chapter 14 (48:47)
- 49:30 — Chapter 15 (49:30)
- 52:26 — Chapter 16 (52:26)
- 55:30 — Chapter 17 (55:30)
- 1:01:24 — Chapter 18 (61:24)
- 1:04:01 — Chapter 19 (64:01)
- 1:08:49 — Chapter 20 (68:49)
- 1:13:05 — Chapter 21 (73:05)
- 1:15:41 — Chapter 22 (75:41)
- 1:17:16 — Chapter 23 (77:16)

## Transcript

**[0:00]:** The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseware continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseware at ocw.mit.edu.

**[0:21]:** All right, good morning, everyone. Welcome back from spring break. Hope you had a nice time off and couldn't wait to get back to 6.046. So, exciting second half. Uh going to do uh flow networks uh today on Thursday. Uh next week it's uh linear programming uh on to complexity, distributed algorithms, cryptography. Uh topics going to come fast and furious. Hopefully, they'll all be interesting. So, uh there's a lot of setup associated with uh network flow, max flow. Uh it's an optimization problem. And so, I'm going to spend like the the first hour here and hopefully it won't be too too boring uh setting up uh flow networks, describing the max flow problem. As you can see, this outline is uh fairly involved uh talking about cuts in a network, uh residual networks, and uh we'll uh uh more or less uh uh end the lecture with uh uh the statement, uh though

**[1:20]:** not the proof, we'll save that for next time, of the max flow min cut theorem, which is really an iconic theorem uh in the literature and certainly uh the crucial theorem for uh flow networks. And uh we'll take the max flow min cut theorem uh and use that to uh get to uh the first ever uh max flow algorithm, which was due to Ford and Fulkerson. And uh that should be uh pretty much at the end of this uh end of today's lecture. And uh next time I will talk about uh uh the proof of max flow min cut, talk about some of the issues with Ford-Fulkerson, and then use max flow uh as uh uh as a hammer to solve uh interesting problems in bipartite matching, uh baseball playoff elimination, and things like that. So, just like shortest paths uh can be used not just to compute uh uh the uh shortest distance from point A to point B, you can imagine that uh other problems, for example, scheduling problems, time problems, could be

**[2:28]:** solved using Dijkstra. And you've probably seen examples of that. Uh max flow is another uh algorithmic hammer that's been used to solve a wide variety of problems. We won't really touch upon that aspect today, but we'll spend a bunch of time on Thursday uh talking about that. So, let's get started. Uh We're going to start with defining what a flow network is. And at some level, it's really simple. I mean, it's a it's a graph. Uh a graph is going to have vertices and edges. Uh we're going to uh only look at directed graphs. And we're going to have a a couple of constraints associated with these directed graphs that are going to make the algorithms and the proofs and the notation a lot simpler. I'll get to that in a few minutes. And uh the key thing with the flow networks, I mean, just like uh you have a source and a destination for shortest paths, in a flow network as well, you're going to have a source and you're going to

**[3:27]:** have a sink. Right? So, we're going to have distinguished vertices, two distinguished vertices.

**[3:39]:** We're going to call them um the source S and a sink T. And so, the basic idea here, and just to sort of set things up right up front, is that there's going to be some flow coming out of S and it's going to have to obey some constraints associated with capacities of the edges in order to make its way to T. And along the way, um this is flow. This is water. You can think of it as water or cars or what have you. It's a rate. Uh you're you're not going to allow accumulation in the intermediate nodes. So, you're going to have uh a a um law of conservation associated with this commodity that's flowing, you know, be it water or cars or people, and uh that essentially comes down to um uh for any uh vertex other than S or T, everything entering the vertex has to leave the vertex.

**[4:34]:** Right? So, that's like Kirchhoff's current law, for example. So, there's a lot of analogies here uh with respect to uh real life or uh electricity in this case. And uh you'll see that, I think um uh over and over as we go along. So, let's uh uh take a look at our a flow network. I'm not going to draw it out here. I'm going to keep this one example all through the lecture, but just to go off and talk about uh edges and capacities before we actually draw an example. Um we're going to have edges, uh directed edges, U V. So, you can have an edge from U to V, and it's going to belong uh to uh to E, obviously. That's the reason um the edge is in the network. And this edge is is going to have a non-negative, each edge is going to have a non-negative capacity, um C UV.

**[5:33]:** Right? And uh if per chance there's no edge from, let's say, uh S1 to S2, these are different vertices from the source or uh or the sink, uh just as an example, uh you can say it's between A and B, then we're going to assume that the capacity is is zero. So, if UV does not belong to E, then assume that C UV is zero. So, there's no way of getting from U to V. This this rate, this water, uh cars, you know, there's no road that gets you from U to V. Okay? So, let's draw an example of a flow network. We'll talk a little bit about uh what the flow is and what the max flow is uh in in you know, sort of uh in example-driven uh algorithm design, if you will. So, I I got a source S and I got uh a sink T.

**[6:33]:** That's And then I got a bunch of nodes in the middle. Just draw them out.

**[6:41]:** I'm not going to bother naming those nodes. Well, that might be a mistake. You'll see.

**[6:56]:** So, it's not like it's an acyclic graph.

**[7:02]:** You're allowed cycles in this graph. But we will have a couple of constraints that are associated with this graph that I'll get to in just a minute. So, first, uh that's what all we got. You got GVE, directed graph, can have cycles in it. And I'm going to draw a a uh a couple of numbers here. The numbers I'm putting up here are the capacities

**[7:36]:** associated with each of these edges. Right? So, um those are just the capacities. Those are C UV. And uh I said that if you V does not belong to E, then you're going to assume that C UV is zero. So, uh there's no edge, for example, uh between uh this node and that node. So, there's no way that you can directly get from here to there. Uh you can go like this, like this, and like that uh and get from here to there, and you can obviously go like so and like this and like that uh to get uh that from the uh the one on the top left to the one on the bottom right. Okay? So, uh that's essentially uh the setup, uh except for the fact that we've just talked about capacities, and uh this is sort of the bandwidth, if you will.

**[8:30]:** This is the amount of traffic that can go through this road. And now we have to talk about the specific case where we're actually going to shove things through the network. Right? So, we're going to have another number. So, typically, we're going to have two numbers associated with each edge. Uh one of them is going to be the capacity, and the other one is going to be the flow that goes through the edge. And as you can imagine, we're going to have this uh constraint that says that the flow can never exceed the capacity, and that's a local constraint associated with each edge. Okay? That doesn't mean that um uh there aren't, you know, variations possible with respect to uh the overall flow of the network. Uh things I can change. You obey the edge capacities, and going into T, uh etc. And so, there was going to be an optimization here associated with the exact numbers that all obey these edge constraints, so these edge capacity constraints.

**[9:28]:** Okay? So, uh let's take a real simple

**[9:36]:** of uh a flow in this network. And uh ah, I have some colored chalk here. So, I can put down uh the flow over here, and so this is flow. Wow. That is an ugly color. But now we're stuck for the rest of this lecture. So, I got two two um one {colon} three. So, the first number is the flow and the second number is the capacity. Let me just write that out. This is

**[10:19]:** So, and and then this is one {colon} three. This is one {colon} one. So, that that meets the capacity. This is two {colon} three and then one three two {colon} three and one {colon} two. Right? So, that's uh my first example of a flow. And that we want to we want to make sure that this flow makes sense. Okay? And we're going to write this down a little more precisely in just a minute, but I've started giving you the intuition already. Right? I've talked about it's okay to have a flow from the source. It's It's It's It's the It's the mountain, you know, spewing water. Or or or that's the source of the river. And and this is the sea, for example, and the and and the river flows into it, but along the way you you really can't have accumulation. Okay? Not in because when you think about it as as a rate, and so this is sort of gallons per second, uh then uh maybe you'll have a little bit of accumulation allowed, but over huge period of time, you

**[11:31]:** know, you can't have infinite accumulation. So, so that's where the conservation law kicks in, which says anything that goes in to a node that is not marked S or T has to leave the node. So, you look at this and you go well, there's two things coming in here. There's one and one, which add up to adds up to two. And uh there's two leaving. So, we're good there. Okay? Uh and then uh pick another one. Uh this one, for example, uh you got two coming in and you got one and one leaving. We're good there. Right? For T, you got three coming in. Uh two plus one. And uh another uh check to do is well, you got two coming out of the source. Right? So, uh hopefully that all makes sense. And ask questions if you're confused. Um One other thing to look at, uh which is interesting, is that you could have um flows that uh are essentially cyclic.

**[12:33]:** You could have um commodities that are flowing in a little cycle. And can you see that? Can anyone see that over here? Yep. Go ahead.

**[12:49]:** Bottom right triangle, this thing over here? Like that? Good. Right. So, you see this one going up this way, this way, and that way. And so, there's nothing that's stopping us uh from um taking this and um I had one over here, so I'm going to make that zero. I I had two over here, I'm going to make that one. And I had two over here, I'm going to make that one.

**[13:15]:** Oh, what was it? It was one before? Oh, you're right. It was one before. So, I should make that zero then. Good. I wanted to subtract one from what I had before, right? And I and I screwed that one up. The simple thing. All right. Wow. Uh no wonder I didn't major in mathematics. Okay. Computer science is this forgiving field. Um so, you can go a zero uh uh well, this is zero, so So, now let's take a look at what we have here and uh I check that nothing went wrong, right? We want to check that nothing went wrong. I and so, two coming in, uh one going out, one going out, and nothing coming in here, so we're all good. And so on and so forth. Okay? So, um there's interesting things happening here with respect to uh uh the conservation laws and having to obey them.

**[14:15]:** Uh In general, you can imagine that what we're interested in is simply maximizing the flow from the source and getting as much flow out of the source as possible and pushing it into the sink. Okay? Now, the flow here into T, as you can see, is two plus one, which is three. Okay? Uh can anyone uh take this particular flow network and uh increase the flow? I mean, it's easy to decrease the flow. You can make everything zero and that'd be valid, right? But can you can you increase the flow? You think that this flow network uh allows for a larger flow than three, given that the capacities of those edges are fixed and I'm not going to change them?

**[15:10]:** Let's see. I think all of you have Frisbees, right? Yeah. Some Yeah, back there. I don't think you can because you're maximizing two edges, which like would have to be increased like the one coming out of the bottom one coming out of S would have to be increased or the one on the very top would also have to be increased. Uh people agree with that? Over there? Yeah. You can have a path going along the top with a flow of two, so then S to the one on the top of it has two, then from that to the right has another has two like it has now. From that node to T has two. And then along the bottom you have another path that has two from S to the one to the bottom of it. Okay. So, that made perfect sense. To me. It did.

**[16:00]:** Uh um So, I I the one of the crucial observations that were just made here, and let me just focus in on that, is uh and that's why I think the other gentleman uh said no, is that you can actually decrease the flow in particular edges, and that's going to help you increase the overall flow. Right? And that's why this problem is challenging. That's why we need so much of a setup. All right. So, one thing that I could do is um I could essentially say, you know, I'm going to take this and make this uh make this zero. Right? So, when I do that, um essentially what I have is I I get to uh I get to push more flow out from here. Right? Uh so, I get to push more flow. This two I can turn this into a two. And I can turn this into a two.

**[16:53]:** Right? Am I Am I done? Not quite. I mean, I got one little bug here, but I can fix that, right? Right? I got one little bug here which says I got two coming out here. I made this zero, so I have to push something more, but hey, I'm lucky. I got S here, which is giving me as much as I want. Correct? So, I can just make this a two. Right? And so, now we get a flow of of four. Right? Uh you both get Frisbees. Should we do blue and purple? Here you go. Can you stand up? Uh okay. Over there.

**[17:32]:** So, that actually kind of summarizes at some level uh our task ahead. Right? So, we have to find ways of increasing the flow, and sometimes we have to take a step backwards in the sense that we decrease the flow on a particular edge. Right? So, it's not this monotonic uh increase that Dijkstra would do or a greedy algorithm like MST that Eric talked about. There's There's going to be something a little more interesting here. Uh we uh eventually are going to end up doing things uh in in a monotonic way uh in terms of the overall flow. So, the max flow that we're trying to get at uh is going to start with the current flow and we're going to improve the current flow constantly, but that doesn't mean that the uh edges are going to look monotonic in terms of the flows on a particular edge in relation to the capacity.

**[18:30]:** You'll never exceed the capacity, but as you saw in this little example already, we increased from three to four by taking that edge that was vertical up there which says zero uh {colon} three, and that was one, and we we shrank the the flow on it. Right? So, how are we going to discover these paths, right? Especially if you have a 5,000 node network and I don't know, 10,000 edges. And so, that's essentially what uh we have to do for the rest of this lecture. Right? Any questions so far? Okay. So, uh we've done flow networks. I kind of defined what the max flow problem is. Um and let me just write that out I more more precisely.

**[19:15]:** Uh given a flow network

**[19:23]:** G find a flow

**[19:31]:** with maximum value

**[19:37]:** on G. And for that, the max flow

**[19:45]:** is four. Right? So, that's the other thing we haven't actually done, which is obviously important for us to do, which is we have to show that the four in this case is the max flow, right? So, and now of course I've given that away and so I'm not going to ask you can you push this over to five and but you might think that five is a possibility simply because the capacities of the edges that are coming out of the source are three plus two, which is five, right? So, it's certainly possible that that you could push at least if you only look at those two edges that you could push five units from the source. But in this case, in this example, um if you obey the laws of conservation, you cannot obey those laws and get five units from the source to the sink T, right?

**[20:36]:** But we have to prove that. I mean we have to have an algorithm that says this is the best that you can possibly do and the algorithm terminates when that happens, right? And that's our Ford-Fulkerson algorithm. Right? Good. So, that's uh what we have so far. I want to talk about a flow network assumptions and I can do that over here. And this is going to make our life easier. One of the things that's a little bit um confusing sometimes is the circular flow and the fact that we're going to potentially have uh flows that uh uh it correspond to edges coming in and edges going out. So, for example, if I had something like um S and U for example, and S could be the could be the source in this case or it could be another node. Uh suppose I had a little subnetwork that looks like this where I'm just giving you what the capacities are.

**[21:44]:** Um this is uh a a bit strange in the sense that uh you could have a situation where you uh essentially have zero flow really because you have one unit coming in here and one unit leaving. All right? And you can think of this let's just call this S1. I if if to to make it clear that it doesn't have to be the the source, right? And so, you could have the circularity that you saw over there and now you're talking about well, I mean I have I might have one colon one here and one colon two here, which is fine for this subnetwork, but if I have stuff going out uh what happens what happens with that? Well, that's got to be a zero. Um I could have a one and a two uh and uh if I have a if I have a two here uh then well, if I had a one and a two here, then that doesn't work uh because

**[22:38]:** maybe I'd need I'd need uh something else coming in. So, you can see that pretty quickly it gets kind of confusing if we end up having uh these uh cycles that are uh that that are uh such simple cycles especially the ones where you have SU and US, okay? And so, we're going to disallow uh cycles of two kinds, right? The first cycle we're going to disallow is the simple one where we say if I have uh A, then uh no self-loop edges allowed. Okay?

**[23:20]:** Right? So, uh that would involve accumulation at a particular node and it's going to make things really confusing and CLRS disallows that and most flow network algorithms assume that you're just going to discard these cycles. Um this particular transformation uh that I'm going to describe here um is something that is going to be uh forced on you and this for you for your benefit uh in in in over six in in lectures and sections, uh but it's not actually uh something that CLRS follows and uh it's going to make things simpler though. And what we're going to do is we're going to take uh any pair of vertices that has this characteristic where you have S1U and US1 and they have nonzero capacities, right? So, S1U has a capacity of one, uh US1 has a capacity of two. Both of these edges exist and if these edges exist, that means they have nonzero capacity, right?

**[24:25]:** Positive capacity. And we're going to transform that uh very simply uh into uh this this is not changing the the generality of the algorithm, but all I'm going to do is transform it call this S1 uh in into something that satisfies this restriction. So, I can have two here, one and one. Okay? So, all I've done is introduce U prime. Right? And I can always do this if this is trivial for any pair of vertices, I can introduce one other vertex. I it all works out linear expansion, constant factors, ignore them, life is wonderful. Right? So, I all I've done is taken away the situation where I have you can think of it as as two-way streets, right? Two-way streets are annoying. You don't quite know what the rate of traffic is from one end of the street to another because cars are going in both directions and you have to do subtraction, right?

**[25:30]:** Subtraction is painful. So, we we don't want that. Right? So, so we're just going to say we're just going to assume that there's this U prime and and now you're all set. Right? This we allow this. So, we have to allow for generality reasons as we saw in that very first example there. We are going to have cycles here, okay? But we just don't want cycles to be of length one or two. Okay? So, those that's essentially what we're going to disallow. All right? The good news is that uh if you do this, then we'll only have a single notion of flow whereas if you go read CLRS, you'll see that there's two notions of flow in CLRS. There's positive flow, which is different from net flow. And positive flow is different from net flow in graphs that have this particular structure or have nodes with these properties.

**[26:27]:** But if you disallow them, then you can just talk about flow and it doesn't matter. It's positive flow is the same as net flow. All right? So, for the purposes of uh 6046 for this semester uh we're going to simply think about flow and equate that to positive flow, equate that to net flow and it's all going to work out assuming your graphs satisfy these two properties of the cycle lengths. All right? Cool. Uh good. So, let's uh keep going here. So, we're up to finished up on max flow. Uh Let me just give you some sense of notation. I I've talked a lot uh or about constraints but we got to write some stuff out because we're going to be uh getting more precise and proving things in just a few minutes. So, what is a flow? Well, to be precise it is going to be a function that satisfies the following properties.

**[27:45]:** Satisfies the capacity constraint.

**[27:59]:** This is the obvious capacity constraint intuitive capacity constraint and then we got flow conservation.

**[28:16]:** And the important thing here is that I I don't have it for all V, but I do have it for all vertices V that are not the source or the sink and I'm going to require

**[28:38]:** f of UV equals zero. Right? And the last one which I haven't talked about but becomes easy to talk about given this constraint is skew symmetry.

**[29:06]:** Right? So, I you if you take there doesn't have to be an edge between you and V. Now I'm talking about the flow F between U and V. And so, you could be S, which is the source, V could be T, which is the sink. So, in general, I'm not talking about a flow. And there obviously has to be a a path uh from U to V in order for there to be a nonzero flow f of UV, right? If there's no path, there's no way of getting there. But having said that uh the definition of a flow here in our network is the straightforward definition uh would simply say if there's a a flow from U to V regardless of what U and V are, then the value of that flow is simply the negation of uh the value of the flow from a V to U.

**[30:03]:** Right? So, which makes perfect sense. Right? So, um and and this all works out uh under the definition of of net flow. And so, this is essentially what the definition of net flow is on in the textbook, but for our purposes here, we don't have to add that adjective. We just are going to be talking about flows. Positive or net, they're the same. All right. All right. Good. So,

**[30:38]:** one of the things you can do uh with this notation and we're going to um use what's called implicit summation notation on top of this is to um prove some interesting things interesting theorems that give you some intuition as to how algorithms on flow networks are going to work. And um in particular, uh we're going to

**[31:05]:** use this notation when we talk about the value of a flow. So, the value of a flow F is denoted

**[31:20]:** You can think of it as a cardinality of F. And F is V belonging to capital V F S V and that is F S {comma} V. Right? So, what I have written here? Well, um given a flow network, I want one particular quantity that I want to maximize. Right? And that particular quantity is going to be defined based on how much I can push from S. How much can I push outward from S? And that's the crucial quantity that I want to maximize. Um that quantity uh is you think about everything that is going out of S and you add it all up together. Right? So, you you look at um from S, you look at any other vertex uh every other vertex and you say, "What is F S {comma} V?" Right? And I'm not talking about just the edges that come out of S.

**[32:22]:** Uh this uh vertex uh V, small V, can be any vertex. Right? If I add up all of the flows that come out of come out of S, then that is the the the flow that is that corresponds to my flow network. That is everything that's getting pushed out of pushed out of S. Okay? Um now, it may be the case that remember what I'm talking about flow here. So, it it it may be the case that you have a you you have an edge uh from uh S coming in from V4. Okay? And there may be there may be a a flow uh associated with that. This may be something like one {colon} two. All right? So, uh what this means is that uh F S V4 is This is F, remember. So, this minus F V4 S and in this particular case, um it's this is is one.

**[33:30]:** So, this is minus one. Okay? So, so keep that in mind. I when I talk about the flow of the network, I'm going to be looking at the source and I'm going to be looking at all of the flows that are going outward and I have to keep in mind the skew symmetry relationship. I obviously have to obey capacity constraints and the conservation laws. All right. So, given that, uh let's use this uh implicit summation notation and uh show some simple properties of flow. Right? So, let's look at

**[34:30]:** One thing I want to emphasize is uh what I've done here is use this implicit summation notation

**[34:42]:** which simply says if I see a a capital letter here, that's a set and I'm going to have to um enumerate all of the members of that set and the it's implicit summation. So, as I enumerate those members, I'm going to add up all of these quantities. Right? So, that's really what this means. So, this sigma here gets embedded into this capital V. So, two things going on. The small V turned into capital V because I'm looking at the entire set and the sigma gets in there, too. And that's why it's implicit summation, not just implicit set notation. Uh so, some simple properties. I can say F X {comma} X is zero where X is an arbitrary set. Uh it All that says is let's say X has uh a single uh member in it uh which is A, then F of A A is is always zero uh because we don't allow self-loop edges.

**[35:45]:** And um uh that's pretty much all you need. Uh if you have a pair of vertices here, A and B, then what you're saying is F of A B plus F of uh B A uh is is zero. And that's true because of skew symmetry. Right? We just wrote that out. So, F of X X is zero. Um and in general, you can say even though X and Y are are sets of vertices, I'm going to be able to use skew symmetry to say that F of X {comma} Y is minus of F of Y {comma} X. All right? Uh similar argument. And then lastly, uh there's any number of these. Uh we just do three of them here. X of F of X union Y to Z is F of X Z plus F of Y Z. We're going to use these properties to prove our first theorem here on flow networks.

**[36:52]:** If X of X intersection Y is null. So, you don't want to double count. So, that's all this is. Uh make sure you're not double counting. You got uh F of X union Y and you want to look at that entire set, the union, and then look at the flow from any member in X union Y to any member in Z and you can do that by breaking it up provided you're careful about double counting and the fact that the the two sets X and Y do not have an intersection or they have a null intersection implies that you're okay with the right hand side. All right? So, you might be going, "Why are we doing this?" Right? Well, here's a good reason to like implicit set notation. Uh you can you can prove some interesting theorems in a in a very elegant way using this notation.

**[37:52]:** So, let's do one example of that. You'll probably see others in section.

**[38:01]:** So, one of the things that we'd like to do is prove a pretty important theorem which I think all of you probably kind of assume in your heads uh in given all of the properties of flow networks that we have. And it's a very simple theorem that simply says um I have the law of conservation that is applied on all of these intermediate vertices. And I got a bunch of uh commodities. I got I got a flow going out of S. Right? So, where can this flow go? Where does this flow end up? It ends up at at the sink. At T, right? So, so so So, the point is that if you have all of these properties that we have up here, uh you're going to be able to show, and you want to show this, uh you want to prove this, that um the value of a flow uh which is defined as what gets pushed out from the source is exactly what goes into the sink.

**[39:13]:** Right? If that's not the case, there's been a violation of some property. Uh perhaps a capacity constraint. Uh perhaps more likely a conservation constraint. Okay? So, so the theorem that we'd like to prove is simply that F is F of V {comma} T. Right? That's the theorem. And and there's a lot going on here, so it's worth spending 30 seconds looking at what exactly this means. What I have here is that if you just look at this and that I'm saying that F is what gets pushed out of of the source. Okay? And now what I'm saying here is that F, the value, is exactly what gets pushed in to the sink. Okay? So this is what I have to prove. Right? And I should be able to prove that by invoking my laws. Right? That's it. I mean that's my axiomatic system. I got those laws.

**[40:14]:** I got a I got a definition of a of a flow that may not necessarily be the max flow. It might be something much less than the max flow. It might be the max flow. Regardless, what gets out of the source has to get into the sink. Right? So how are we going to do that? And the implicit summation notation is going to give you essentially a three or four line proof, which is very intuitive. Right? So let's let's do that and maybe you can help me. So we're going to start with what we know. Right? So that's the proof. F equals F of S {comma} V. Right? So that's what we got. That's the definition of cardinality of F or value of F. Okay? Um what I'm going to do is I'll I'm going to say uh this is the same as I'll give you the first step and then let's see whether you can help me with the remaining is the same as

**[41:13]:** F of V minus S capital V. Right? So uh if you have if you're having trouble differentiating between my cap V's and small V's, uh holler. I'm trying to write them as big as possible. Yeah. Let put little hats on them. Yes, I will put little hats on them. I'll put little Frisbees on them if I could, but uh I like Frisbees much better than hats. All right, that's good. That's That's good to do. Um so uh so yeah, so so I think hopefully I'll keep doing this and it won't be confusing. Um so what I've done here is invoke I essentially this, except it's not exactly that in in this in the sense that it's written a little bit differently. But if you see what's going on here, uh what I've done is uh uh is look at uh this S and uh I've said, you know, think of this S as being um a cap V uh minus uh

**[42:21]:** cap V minus S. Right? So that gives you S and those are clearly disjoint. Right? The those are clearly disjoint sets. Uh that is this one and this one are disjoint sets. That's what That's what I mean to say. I mean these two aren't disjoint, but this and that are disjoint and that's what you need in order to invoke uh the little property that you have here. And so uh that all makes sense? You see why I did that? Okay? Um what can I say uh about uh either of these two quantities? Can I say something about either of these two quantities?

**[42:56]:** Yeah. F of V to V is zero. That's exactly right. F of V to V is zero. There you go. Yeah. So this is simply uh I'm going to invert that. I'm going to write this as F of V hat minus S. Okay? I've just flipped this. I had negative sign here, but I flipped that. And uh skew symmetry tells me I can do that. Right? Um All right. So So I'm up to this point here. Um now what I'm going to do is uh I'm going to do F of V T. And the reason I want to do this is because this is where I want to get at. Right? Eventually I want to show something that corresponds to F of cap V uh T. Right? So uh and and what I have here is VT, but now I can do plus F of V V minus cap minus S minus T.

**[44:08]:** Right? So what I've done here is taken V minus S and uh pulled out T from it. Remember T is part of uh cap V. Uh cap V contains all of the vertices. So I've pulled out T from it. Uh but that implies that I have to do V minus S minus T over here. And again they're disjoint. Right? So So it's all good. Uh what can I say about uh about this? Yeah. It's zero because of flow conservation. That's exactly right. Uh we didn't quite write it that way, but if you look at what the implicit summation notation would mean for that, uh you look at it and you say um maybe that and one more step would be let me think about this as being F of V T. It'll become more obvious if I write it this way. F of V I'm putting a minus in here.

**[45:11]:** V minus S minus T and cap V again. Right? So all I've done here is flip these two. Uh skew symmetry allows me to do that. And now look at what I have here. I'm talking about a flow that corresponds to some uh for any uh vertex I I pick and it's not an S vertex, it's not a T vertex. So it's an intermediate vertex. And if I look at an intermediate vertex and look at the the flow that goes out to all vertices, uh conservation says that has to be zero. Right? So that's exactly what this says. Uh for any U that is in this uh that's neither S nor T, but in V, uh the sum has to be zero. So this is zero and we're done. All right. Oh, you have Frisbee? Who is that? Ah, yeah. So that's uh the power of implicit summation notation.

**[46:15]:** Right? So we could invoke uh these different properties. It was fairly straightforward. Your first example of this, you'll probably see a few more. All right. Um any questions so far?

**[46:29]:** Okay. So as you can see, as I promised or threatened at the beginning, but followed through on my threat, we have a lot of notation, a lot of baggage here before we get to algorithms. Right? But we're slowly getting there. The next major concept is the concept of cuts. Right? So a cut, you think of a cut as being well, a cut through paper, you know, a cut through the air, whatever. It turns out the notion of a cut in a network is more general than that. Right? A cut is basically a partition. Um a cut is a partition of nodes and a partition means that you can't have a node in both sides. Right? So a cut is going to give you two disjoint uh components at at the end of it. But the cut doesn't have to be something contiguous. It doesn't have to be, you know, a line through the network and everything to the left of the line is in one half of the cut and everything on the right of the line is in a different half

**[47:28]:** of the cut. I I can just break up these nodes into two disjoint parts and the only constraint that I'm going to ask for is that is that S, which is the source, is on one side of the cut and T, which is the sink, is another side of the cut. Okay? That's it. And given that, I'm going to say interesting things, really interesting things, about the flow through a cut. Okay? And so let's do that. Let's define a cut

**[48:22]:** So a cut is ST

**[48:34]:** of a flow network G

**[48:41]:** is a partition

**[48:47]:** of V such that small S belongs to cap S and small T belongs to cap T. Right? I don't know. Do you want hats on the T, too?

**[49:05]:** I'll just write them large. If a flow on G if F is a flow on G

**[49:23]:** then the flow across the cut

**[49:30]:** is F S T. Okay? Um so again, implicit summation notation here the flow across the cut is as the sum of the flows corresponding to each pair of vertices such that the source vertex is part of capital S and the destination vertex is part of capital T. All right. That's it. I'm just going to add them all up and that's the flow across the cut. Um So what I can do now is just talk about let's just go up here back to this um and I'm going to look at exactly what I have here. Is that right? Not not exactly. I'm going to change this a little bit because I I I want to make sure I don't have to add up numbers and do that incorrectly. So I need a one. Yep. That's all I need to do. Change it. So I'm going to change our example here not the topology of the example but the actual numbers and you'll need to verify that what I have here satisfies our flow network properties and uh there's one more.

**[51:13]:** Okay. So I think I'm good. All right. So this is going to be an example of a cut. I haven't defined the cut yet.

**[51:27]:** Let's get rid of that. Holler if you think there's something wrong with this flow. I think I got it right. It satisfies capacity constraints. It satisfies flow conservation constraints. Right? The flow that is going into T is four. This happens to be a max flow. Doesn't really matter. Right? So what we're going to talk about with respect to cuts doesn't require the flow to be maximum. Keep that in mind. Um what do I mean by the flow across the cut via an example? I'm going to simply say that the shaded nodes two of them are part of capital S. Okay. So

**[52:26]:** So as you can see I just arbitrarily picked a couple of nodes and they're not necessarily something that can be easily partitioned using a actual cut line a physical cut line. I just picked that that one over there and the one over here with S. And so I can now look at this and I can compute numerically for this example and it's worth doing at least once what the flow across this particular cut is defined by the particular choice of cap S and cap T. Okay. And and that's what we're going to do. So F of cap S T is I'm going to have to look at pairs of nodes such that I got a shaded node on the left hand side and non-shaded node on the right hand side and I'm going to have to go through all of the the combinations. Right? So if I look at this I can I can first knock off this one and that one and that one.

**[53:42]:** Let me actually put it put in let's call this A B and C here and we can call that D. Right? So we have S and D as being part of the cut in terms of S capital S and the other ones are are in in cap T. Um and so what I have is I could I could do SA and SB. So I got 2 + 2. Right? And this would correspond to SA and SB. So those are going out. Right? So far so good. Um and then I'm going to write down a bunch of numbers here -2 +1 -1 +2. Okay. And the the -2 where did the -2 come from? Well in in AD for example is a is a -2. Right? Because D is part of it would be DA. So AD is has a flow of two. Correct? And so DA has a flow of -2.

**[54:46]:** Right? And DA is part of what I have here because D is part of capital S and A is part of capital T. You guys see that? So it's this is not trivial. So pay attention. Um So this would be for example the -2 would correspond to to A comma D comma A. That's what I need here and I could also have what do I have here? I have C something is going into D. So CD is one. So DC is -1. Right? Make sense? DC is -1. What about the +1? Where do I get a +1 from?

**[55:30]:** DB is going out. That's exactly right. DB. And +2 would be DT. Right? So

**[55:43]:** Um and so you have to do the enumeration. I this it's worthwhile doing once and then it gets kind of boring. We won't do it again. But you have to realize that you have to absolutely look at every pair of vertices and you have to use Q symmetry and ensure that even though there's actually no edge going out if there's an edge coming in you got to count that and you got that's going to get a negative. Whatever it's coming in you got to you got to subtract. Okay? So it's not that complicated. Yeah. Go ahead. I'm sorry. Um so when you don't have so the the the beauty of this is that when you don't have a particular edge from S to C you can use Q symmetry to argue that SC and CS cancel out each other. All right. So so that's the good part.

**[56:36]:** Right? And thanks for asking the question. Right? That's that's a good question. Right here you go.

**[56:43]:** So you can you can do that by just looking at the edges and you can you can add up the numbers. All right? And so I I don't think this is going to be absolutely crucial to understand the rest of the the lecture. Keep this in mind that there's a a process by which you define the the value of a cut and we're going to get back to this when we prove the max flow min cut theorem next time. But at this point I want to say something actually much more straightforward which is going to be important when we look at residual networks which is the last concept that we need to get at before we get to an algorithm and that is simply that the capacity of a cut and the relationship between the capacity of the cut and the the flow of a cut.

**[57:42]:** So the capacity of a cut is C of capital S capital T. Oops. I didn't draw that properly. Open brackets capital S capital T and we can do it exactly the same way except this is a lot simpler because you only look at edges that and you only have positive quantities. So in this case you'll simply say it's 3 + 2 corresponding to what I what did I have here? I had D comma A S comma A and S comma B. And then the capacity is you you you you you only need to look at edges that go from a node in S to a a node in capital T. And so those are one +3. Um and this simply would be the one would be D comma B and the three is D comma T. Right? So you don't care about the other flows.

**[58:49]:** This is not about flows. This is simply about capacity. Right? So this adds up to adds up to nine. Okay. Um and so I we have at this point I if at the we've defined the flow through a cut and we know the capacity of a cut. Okay? It's more or less obvious that you could suddenly prove a theorem which you know is going to take a couple of lines to say that the value of any flow um is bounded by the capacity

**[59:44]:** of any cut. And sorry, I lied. It's not a It's not a trivial proof. And there's actually something profound going on here. Uh and so I'll have to explain uh exactly what this means. And then we'll take a look at the how we could prove something like this. So, what's cool about this um is that uh you're saying that the it's the value of any flow is bounded by the capacity of of any cut. Okay? And so that's an upper bound on the maximum flow value. Right? So, I'm saying, you know, there's all these cuts that are possible in the network. And I'm making a statement about uh uh what the maximum flow can be based on the values corresponding to the capacities of of of any cut. Right? So, uh why is that the case? Well, we're not going to be able to prove that uh uh uh fully uh today.

**[1:00:50]:** We're going to That's the max-flow min-cut theorem, but you'll certainly You can certainly get a sense of it uh by looking at as a different characterization of the flow value. So, I'm going to give give you one half of the proof at least and intuition about the other half and we'll finish it next time. Um but here's another characterization

**[1:01:24]:** of the flow value. Okay. So, our lemma here, which is going to lead us to this statement, is that for any flow f and any cut st

**[1:01:49]:** we have

**[1:01:55]:** really powerful a a dilemma. Maybe we should call it a theorem. But it essentially says look, it doesn't matter what cut you choose. Right? You got a flow on the network. And uh when you look at the the the flow on the network, it's going to equal the flow across the cut. And the only reason for this is simply because you got the source on one side of the cut and you got the sink on the other side of the cut. That's it. That's the only thing that you need. Right? You dump these vertices into two bins, you know, dump the source on the left and dump the source sink, excuse me, on the right and you compute the flow the way we've defined it, that's the flow. It doesn't matter how you partition these vertices as long as you got the source on the left and the sink on the right.

**[1:02:45]:** Okay? And so we can prove this using implicit summation notation. We'll do that. And that'll give you a a really good sense of why this statement is true because we know that I for any given cut, the flow of the of that cut is bounded by the capacity of that cut. Right? We know that. Um but to show this, here's here's how we can show that. f of st is f of sv minus f of ss Okay? So, I I'm playing around just like I did before. I've taken the cap t. I know that s union t is cap v. Right? I'm going This is a partition. So, I know that s union t is cap v. So, I can put a v here and an s here. Right? And that's the subtraction over there, of course. Right? So, put that up here and finish this.

**[1:03:53]:** Couple more lines.

**[1:04:01]:** And uh what can I say about uh either of these? Something I I could say something about one of these terms. Yep. The one on the right. The one on the right is zero. So, call this f of sv Right? And now I'm going to uh break it up again. Make it small s big v plus f of cap s minus s cap v. So, broken this up into small s, which is disjoint from cap s minus s, clearly. Um and uh what can I say about this? This is a little

**[1:04:51]:** more subtle than perhaps the previous question. Uh what can I say about that quantity? I mean, the answer is not subtle. But uh yeah, go ahead. That value is equal to zero. And why? Because s the cap s doesn't contain t Ah, beautiful. That's right. So, that's what I wanted. So, this does not contain t.

**[1:05:14]:** And so now you can use flow conservation, right? And that's that's the important thing. Uh you can uh um you can use flow conservation because this does not contain t. And and then uh you know, clearly does not contain small s because I just took it out of it. Right? So, so that goes to zero. And voila. That's simply f of sv, which we know is uh uh is is is f, right? We just We proved that. Uh we did our first implicit summation proof was uh showing that um uh well, this is definition, excuse me. So, uh we showed that uh we we did it for for for the sink. Uh but this is simply the definition um of of the flow value. Right? So, this is beautiful. I mean, it's like fantastic, right? I mean, why aren't people excited? Because I put people to sleep before in the hour before.

**[1:06:10]:** Right? But this is absolutely fantastic because this says that I have ways of uh uh of figuring out what the maximum flow of the network would be uh by making arbitrary cuts through this network and looking for capacities of these cuts. Right? Because I know that the capacity of any cut And now you see why min-cut is interesting. But you know that the capacity of any cut is going to bound the flow of the network. Right? Because the flow through a cut is the flow through the network. So, if I go through and look at the min-cut uh corresponding to the minimum capacity associated with the flow network, that's going to point me to my max flow. Right? Because that's going to be a bound on an upper bound on the on the max flow. Right? And so now you see why the min flow not the min flow, sorry.

**[1:07:04]:** The min-cut max-flow theorem is is is an interesting one, but it it it relates and this is the beginning of that relationship. We're not quite done to prove it, but the beginning of the relationship is that uh you can look at any cut and you can look at the flow through the cut as being the flow through the network. And then you use the second part of it, which is the capacity bonding, of course, in a very similar way because of edge capacities, the flow through the cut, and you can put those two things together. All right? We still don't quite know how to find these cuts. Right? So, we don't quite know how to find these cuts and that's the last thing that we're going to do today. Give you a sense of how we're going to find these min-cuts so we can find the max flow.

**[1:07:50]:** All right? Cool. So, uh the one last notion uh that we have here that is going to allow us to go into the algorithm domain as opposed to the analysis domain, right? We all All we've done so far is analysis, analysis, analysis is the notion of a residual network. Okay? And a residual network, as its name implies, is something that has residual capacities. It's the network that points you to places where you can increase the flow because there's capacity left. There's your flow is less than the edge capacity. It's a local notion, so it's easy to compute. I There's a capacity of three on this edge, there's a flow of two. The residual capacity is one, right? 3 - 2. Um and so the residual network

**[1:08:49]:** um is gfv ef. Right? So, the actual network is gve. And the vertices are going to be the same. The graph is obviously different, but the edges are going to be different. There's going to be a different uh set of edges in the residual network as opposed to the flow network. Okay? And um uh you have strictly positive, that means greater than zero, strictly greater than zero residual capacities.

**[1:09:27]:** Right? Right. So, c f u v equals c u v minus f u v. And that's strictly greater than zero. I'm going to put an edge in there if there is a residual capacity. Zero doesn't mean there's any residual capacity. Um edges in e f admit more flow. Okay? Um and one last thing if v u does not belong to e, so we're talking about the the original network here. E means the original network. Then we know that c of v u equals zero. That was our definition. If you don't have that edge, the capacity is zero. But I we're talking now about f, which is a flow, which doesn't necessarily require that there be an edge, and we're simply going to use uh our skew-symmetry relationship, and you'll see that uh this may not be completely clear as to why I wrote this at this moment, but as I draw the residual network, you'll see why that is important.

**[1:10:53]:** It's going to be the case that we're going to have extra edges in the residual network that don't exist in the original network because of that last line there. Right? So, let me clear that up. So, we're going to draw a a a residual network uh for uh I'm going to change that yet again. Uh but we're going to draw the residual network for our example up there. Topology is going to stay the same. Numbers are going to change because I want something slightly more interesting than uh what we have there. So, I'm going to take this out. Uh two one one two Go back to what it was before, I think. One

**[1:11:50]:** All right. Good. So, um I want a one over here. Uh I want a a one over here. Uh a two over here. And keep checking to make sure that I'm not messing up here in terms of flow constraints. But that's pretty much all I got.

**[1:12:15]:** Okay? Um so, the flow here uh and that that the s and t don't particularly matter. The max flow is four. The flow that you see up there is three. This is what we had right up at the beginning. All right? So, what I want to do now is uh give you what the residual network is for this particular flow. Remember that the residual network is defined based on a flow. That's why you have g of f, g subscript f. F is a flow. So, you're going to have a different residual network if the flow is different. So, the original example that I had would have a different residual network. This one is going to have the one I'm going to draw. All right? So, the residual network has the same set of vertices. So, I can go ahead and draw uh these vertices.

**[1:13:05]:** I'll just mark t and s over here. Those are exactly the same as before. And this is g f. Okay? That's our residual network. And the edges are going to be different. All I have to do is look it up look up there and say, "Look, I'm going to have a residual capacity of two." Uh let me use a different color since I have them. Uh corresponding to that edge from s to a because I clearly have a capacity of three and I only have a flow of one. Right? So, that's all there is to it. Now, the interesting thing is that I'm because of this line over here, I'm actually going to define an edge in e f uh in g f or e f that corresponds to this edge that didn't exist in e because I can shrink the flow from one to zero.

**[1:13:58]:** And that essentially says that that shrinkage is represented in the residual network by an edge that goes from this node a up there to s. Right? And that is going to have a residual capacity of of one. Right? So, that's it. That's the only extra thing that you have to remember when you draw the residual network. You not only can increase the flow, you can also shrink it. You have to represent the shrinkage of the flow by an edge in the residual network. And you obviously represent the increase of the flow by an edge in the residual network. And now you see why this all going to make sense. Remember way back um uh eons ago, only an hour ago, but uh we we had this example where uh we had to shrink the flow in a particular uh edge in order to get the overall flow to increase.

**[1:14:54]:** Right? The residual network is going to point us in the direction of uh potentially those edges whose flow has to shrink, but they're going to be represented at in in effect as these reverse edges with positive numbers associated with them. So, there's a one here, it's positive because it goes from this node, call it a, back to s. And if I if I if I if I shrink this uh um from one to zero, that is in effect taking what I have up here and making this one a zero. Okay? That's the way you want to think about this. So, that's pretty much it. Um I can draw the rest of this, and it should all make sense. Um I have an edge like that.

**[1:15:41]:** So, there's not going to be a I There's the edges that are at capacity up there aren't going to show up here. The edges that are not at capacity end up with two edges down below if they have a a flow that is nonzero. Right? If if you have a zero flow up there, uh you're only going to get one edge. Uh assuming that obviously you'll get one edge because the capacity is nonzero. But the ones that are not quite at capacity end up with two edges. Right? Think of that as being the simple rule. Right? And make sure that I'm following this rule. Good exercise is to check for bugs, lecturer bugs, best way of understanding the material.

**[1:16:26]:** And

**[1:16:35]:** Okay, so that's my residual network. Um and uh let me just point I'll I'll put in some numbers. Uh or maybe you can tell me some of what what some of these numbers are. What is this number? Two. Right? Now, this is a little more tricky. Um take a look at the the the number that goes up versus the number that comes down. What is this number? Goes up. Uh that's two because I can go from one to three. And this number would be? Beautiful. All right, you guys got it. Did my job.

**[1:17:16]:** All right, so that's our residual network for this particular flow. All right? So, mechanical way of computing it uh and you should be able to do that. Um now uh what exactly uh can we do with this residual network? Um it turns out that the algorithm now can be described in a couple of sentences. Right? Our essentially our Ford-Fulkerson algorithm, I'm not going to bother writing this out because I'm going to have to prove the max-flow min-cut theorem next time, and we're going to talk about the Ford-Fulkerson algorithm and issues with it next time. But I'm going to show you how the Ford-Fulkerson algorithm works on this particular example, and it's only going to have one step. All right? So, it's going to converge in one step. So, it is going to be relatively easy. Right? But the bottom line is the the Ford-Fulkerson algorithm is going to look for um augmenting paths.

**[1:18:12]:** Right? in g f Augmenting paths are defined in the residual network. What is an augmenting path, you ask? Well, an augmenting path is simply a path from s in g f to t in g f. Okay? That's it. That's That's all there is to it. If you can find a path, you could use depth-first search, you could use breadth-first search, you could use whatever you wanted. You find a path from s to t. Okay? If you find such a path, if this path exists, it means that the flow is not maximum. Okay? If no path exists, the flow is maximum, and you're done. If such a path exists, you will be able to increase the flow, in this case because we have integral quantities, by at least one. Okay? And you will be able to increase the flow by one. And not only that, the augmenting path is going to tell you exactly what to do with respect to what edges to change, you know, sometimes subtract at the flow from, sometimes increase.

**[1:19:26]:** Right? So, the augmenting path is going to take care of it, but we have flipped it, so everything is positive. You know, life is great. Positive numbers. You know, just look at uh S to T and tell me give me any path from S to T here in uh in the uh in the residual network. So, let me let me just call them A uh B uh D and C. And we don't care about partitions or cuts at this point. That's required for proofs, but uh give me a path from S to T. Yeah, go ahead. S to A to B All right, a little bit more slowly. S to A Okay, and then? B to C A to B, beautiful. B to C B to C C to and C to T. Wonderful. And um I I have a a a capacity a residual capacity of two here.

**[1:20:26]:** I have a residual capacity of one here, one here, and one here. And so, um the uh value of this augmenting path um is is one. Right? It's not two uh because uh the minimum value is what I can push through the network. And I just need to take the min of all of the residual capacities corresponding to the edges that I traversed that correspond to this particular path, and that min value of two one one one is one. Right? So, what this means is I've discovered an augmenting path uh of uh residual capacity one. Now, I can go back to this thing over here, and these edges are going to point me in some cases to complementary edges, in some cases to the direct edges that uh have are going to have to have their flows changed either increased or decreased to increase the flow in the original network.

**[1:21:27]:** So, you're guaranteed now that F, which caused this residual network to have an augmenting path in it, was not maximum. You're guaranteed that because you found this path. Okay? So, what happens here? Well, you go back up and you say, I remember I'm going to increment by plus one because that's the residual capacity. So, I'm going to go up here, and I have S to A. You need to You You need to help me out again. So, I'm going to make this two. Right? Because I needed to add a one to it. What happens here? This is the key step. Subtract and make this a zero. Right? We're not quite done. What's What's next? I have B to C, right? Right? You're still on the hook. B to C becomes? Three. Right? And then lastly this becomes two.

**[1:22:27]:** Okay? And at this point, if you create a residual network for this new flow, you will not be able to find a path in that residual network from S to T. And you know you're done. Right? So, all of this uh works. We haven't quite shown that it works because we haven't done enough of the proofs, but you have a sense as to why this works. You could probably code this up. It It would all work. Couple of issues and applications. See you next time.
