WEBVTT 00:00:00.046 --> 00:00:03.400 Here is a question with a genuinely beautiful answer. 00:00:03.483 --> 00:00:08.209 You have a network of pipes, and every pipe has a limit on how much it can carry. 00:00:08.661 --> 00:00:12.505 You want to push as much as possible from one end of the thing to the other. 00:00:12.817 --> 00:00:17.184 How much can you push, and how would you ever prove that you cannot do better? 00:00:18.580 --> 00:00:21.576 This is the network we will work with for the whole lecture. 00:00:21.773 --> 00:00:23.782 There are four nodes in it. 00:00:24.095 --> 00:00:25.359 s is the source, 00:00:25.442 --> 00:00:30.249 where everything starts, and t is the sink, where everything has to end up. 00:00:30.701 --> 00:00:34.509 In between sit two junctions, called a and b. 00:00:35.051 --> 00:00:37.325 Five directed edges join them up. 00:00:37.408 --> 00:00:40.262 The gray number on each edge is its capacity, 00:00:40.345 --> 00:00:42.737 the most that edge could ever carry. 00:00:42.934 --> 00:00:46.532 The green number beside it is how much is flowing along it right now, 00:00:46.532 --> 00:00:48.762 which for the moment is nothing at all. 00:00:49.559 --> 00:00:55.469 Read the capacities off. The source can send three units into a, and four into b. 00:00:55.666 --> 00:00:58.218 The edge from a down to b can carry two. 00:00:58.301 --> 00:01:03.538 And into the sink, a to t can carry two, and b to t can carry three. 00:01:04.451 --> 00:01:05.984 The arrows matter. 00:01:06.181 --> 00:01:11.301 An edge from a to b is not an edge from b to a, and that capacity of two is a limit 00:01:11.301 --> 00:01:13.774 on units travelling downward only. 00:01:13.878 --> 00:01:16.410 Nothing at all is allowed to travel back up it. 00:01:17.207 --> 00:01:22.177 A flow is an assignment of a number to every edge, and it has to obey two rules. 00:01:22.373 --> 00:01:24.162 The first one is obvious. 00:01:24.266 --> 00:01:29.352 No edge may carry more than its capacity, and no edge may carry a negative amount. 00:01:30.056 --> 00:01:32.343 The second rule is conservation. 00:01:32.447 --> 00:01:35.139 At every node except the source and the sink, 00:01:35.222 --> 00:01:37.449 whatever flows in has to flow out again. 00:01:37.532 --> 00:01:42.154 A junction does not store anything, and it does not invent anything either. 00:01:42.950 --> 00:01:46.271 Let me push something through, so you can watch both rules working. 00:01:46.375 --> 00:01:50.010 Send two units out of the source along the top edge into a. 00:01:50.493 --> 00:01:55.300 Now a has two units arriving and nothing leaving, which breaks conservation. 00:01:55.497 --> 00:01:57.262 So send them onward. 00:01:57.459 --> 00:02:01.488 One unit goes down to b, and one goes straight across to the sink. 00:02:02.285 --> 00:02:06.476 And b has one unit arriving, so one unit leaves for the sink. 00:02:06.673 --> 00:02:08.471 Every junction balances now, 00:02:08.554 --> 00:02:13.814 no edge is over its capacity, and what you are looking at is a perfectly legal flow. 00:02:14.517 --> 00:02:18.640 Its value is simply what leaves the source, which here is two units. 00:02:18.743 --> 00:02:22.492 The two units arriving at the sink agree with that, and they always will, 00:02:22.575 --> 00:02:25.571 because nothing is created or destroyed in the middle. 00:02:26.483 --> 00:02:28.597 It is not a very good flow. 00:02:28.794 --> 00:02:32.287 The edge from the source into b is carrying nothing whatsoever, 00:02:32.370 --> 00:02:35.877 and the edge out of b has two units of room going spare. 00:02:36.073 --> 00:02:38.825 We are going to do considerably better than this. 00:02:40.338 --> 00:02:44.667 Now the other half of the story, and it is the half that does the proving. 00:02:44.750 --> 00:02:47.952 Take any way at all of splitting the four nodes into two groups, 00:02:48.035 --> 00:02:50.846 with the source in one group and the sink in the other. 00:02:51.158 --> 00:02:52.785 That is called a cut. 00:02:53.837 --> 00:02:56.101 Here is the simplest one there is. 00:02:56.298 --> 00:02:58.467 Draw a line just to the right of the source, 00:02:58.550 --> 00:03:03.482 so that the source is on its own and a, b and the sink are together on the far side. 00:03:03.565 --> 00:03:07.049 Two edges cross it, s to a and s to b. 00:03:07.753 --> 00:03:10.110 The capacity of a cut is the total capacity 00:03:10.110 --> 00:03:12.305 of the edges crossing it forwards. 00:03:12.501 --> 00:03:17.111 Three plus four is seven, so this particular cut has capacity seven. 00:03:17.815 --> 00:03:20.253 And here is why that matters so much. 00:03:20.450 --> 00:03:24.396 Every single unit of flow begins at the source, on the left of that line, 00:03:24.479 --> 00:03:27.289 and ends at the sink, on the right of it. 00:03:27.486 --> 00:03:29.539 So every unit has to cross somewhere, 00:03:29.622 --> 00:03:32.664 and the value of the flow can never be more than seven. 00:03:33.461 --> 00:03:37.061 That is worth saying twice, because the entire proof rests on it. 00:03:37.257 --> 00:03:38.849 A cut is a wall. 00:03:39.045 --> 00:03:42.236 Whatever the flow does, however cleverly it is routed, 00:03:42.319 --> 00:03:45.919 it has to get through the wall, and the wall has a fixed total width. 00:03:46.832 --> 00:03:48.249 Try a different one. 00:03:48.353 --> 00:03:52.693 Move the line over to the far side, so that the source, a and b are together 00:03:52.776 --> 00:03:54.995 and only the sink is on its own. 00:03:55.191 --> 00:03:58.571 Now the crossing edges are a to t and b to t. 00:03:59.483 --> 00:04:03.838 Their capacities are two and three, so this cut has capacity five. 00:04:03.942 --> 00:04:06.970 Five is a far better piece of information than seven was, 00:04:07.053 --> 00:04:10.026 because it says the flow can never get past five. 00:04:10.823 --> 00:04:13.643 A network this small has only four cuts, 00:04:13.726 --> 00:04:17.476 one for each way of deciding which junctions go on the source side. 00:04:17.673 --> 00:04:20.086 The other two come out at eight and at six. 00:04:20.169 --> 00:04:23.455 So five is the best ceiling any cut here can give us. 00:04:23.880 --> 00:04:27.942 So every cut hands us a ceiling, and the smallest cut hands us the best ceiling 00:04:28.025 --> 00:04:30.313 this kind of argument could ever produce. 00:04:31.113 --> 00:04:34.725 The theorem we are going to prove says something much stronger than that. 00:04:34.828 --> 00:04:37.441 The best ceiling is always reached exactly. 00:04:38.238 --> 00:04:40.955 Maximum flow equals minimum cut. 00:04:41.152 --> 00:04:42.453 Not at most. 00:04:42.905 --> 00:04:43.951 Equal. 00:04:44.263 --> 00:04:47.106 In a few minutes you will watch the flow climb to five, 00:04:47.189 --> 00:04:50.683 and then watch a cut of capacity five appear out of the leftovers, and the two 00:04:50.683 --> 00:04:52.286 numbers will meet in the middle. 00:04:53.406 --> 00:04:57.459 We have a network, and we have the rules a flow has to obey. 00:04:57.771 --> 00:05:01.276 What we need now is a way to actually find the biggest flow, 00:05:01.359 --> 00:05:04.460 and the method is almost embarrassingly simple. 00:05:04.656 --> 00:05:08.660 Find a route from the source to the sink that still has room on every edge, 00:05:08.743 --> 00:05:12.053 and push as much along it as the tightest edge will allow. 00:05:13.267 --> 00:05:15.114 A route like that has a name. 00:05:15.218 --> 00:05:16.946 It is called an augmenting path, 00:05:17.029 --> 00:05:21.012 because sending flow along it augments what we already have. 00:05:21.116 --> 00:05:25.084 The amount it can take is decided by whichever edge has the least room left, 00:05:25.167 --> 00:05:27.618 and that edge is called the bottleneck. 00:05:28.670 --> 00:05:32.723 Nothing is flowing yet, so every edge has all of its room available. 00:05:32.919 --> 00:05:38.666 Take the top edge into a, then the edge down to b, then out of b to the sink. 00:05:39.463 --> 00:05:44.108 The room on those three edges is three, then two, then three. 00:05:44.560 --> 00:05:49.007 The smallest is two, so two units is everything this path can carry. 00:05:50.059 --> 00:05:51.407 Push it through. 00:05:51.603 --> 00:05:54.249 All three edges on the path go up by two, 00:05:54.332 --> 00:05:57.398 and the flow we are holding now has value two. 00:05:58.194 --> 00:05:59.913 Now look at the middle edge. 00:06:00.226 --> 00:06:05.080 Two units on a capacity of two, which means it is completely full. 00:06:05.276 --> 00:06:08.714 Nothing more can ever go along it while this flow stands. 00:06:09.510 --> 00:06:11.241 Look for another path. 00:06:11.437 --> 00:06:16.430 From the source into a there is one unit of room left, and from a straight across 00:06:16.430 --> 00:06:18.471 to the sink there are two units. 00:06:18.554 --> 00:06:21.968 The bottleneck is one, so one unit is what we send. 00:06:22.881 --> 00:06:25.401 Three units are leaving the source now. 00:06:25.505 --> 00:06:29.706 And the edge out of the source into a is full as well, three out of three, 00:06:29.789 --> 00:06:31.415 with nothing to spare. 00:06:32.816 --> 00:06:34.161 One more path. 00:06:34.244 --> 00:06:38.331 From the source into b there is plenty of room, three units of it. 00:06:38.528 --> 00:06:41.626 But the edge from b to the sink has only one unit left, 00:06:41.709 --> 00:06:44.682 so one unit is all we can send along this one. 00:06:45.478 --> 00:06:48.486 Four units. And now we are stuck. 00:06:49.283 --> 00:06:50.793 Look at what is left. 00:06:50.989 --> 00:06:55.739 The edge from the source to a is full, so a cannot be reached that way at all. 00:06:55.935 --> 00:07:00.427 The edge from the source to b does have room, so we can get as far as b. 00:07:00.510 --> 00:07:04.399 But b to t is full, and b has no other edge leading forward. 00:07:04.596 --> 00:07:06.315 There is nowhere to go. 00:07:07.367 --> 00:07:11.037 So the simple method has run out of paths at a value of four. 00:07:11.233 --> 00:07:15.564 And the uncomfortable question is whether four really is the answer, or whether we 00:07:15.564 --> 00:07:19.396 made a bad choice somewhere and the method has no way at all of noticing. 00:07:21.210 --> 00:07:25.019 We did make a bad choice, and it was the very first path. 00:07:25.216 --> 00:07:29.637 Those two units went from a down into b, and then out of b to the sink, 00:07:29.720 --> 00:07:33.227 and between them they used up nearly the whole edge into the sink. 00:07:34.023 --> 00:07:36.019 But b had a supply of its own, 00:07:36.102 --> 00:07:40.340 coming straight from the source, and now there is no room left for it. 00:07:40.653 --> 00:07:43.719 The two units that came down from a squeezed it out. 00:07:44.515 --> 00:07:47.580 What we would like to do is take one of those two units back off the edge 00:07:47.580 --> 00:07:51.572 from a to b, push it across from a to the sink instead, 00:07:51.655 --> 00:07:56.102 and let a unit from the source into b move into the space it leaves behind. 00:07:56.717 --> 00:08:00.166 But the method as we stated it cannot walk backwards. 00:08:01.079 --> 00:08:04.098 So we change what the method is allowed to walk on. 00:08:04.295 --> 00:08:08.183 This is the residual graph, and it records not what is flowing, 00:08:08.266 --> 00:08:10.240 but what could still change. 00:08:11.153 --> 00:08:14.172 Forwards, it is what you would expect. 00:08:14.369 --> 00:08:18.918 An edge of capacity four carrying one unit has three units of room, 00:08:19.001 --> 00:08:21.707 so three more could still be pushed along it. 00:08:22.020 --> 00:08:24.761 Every number on the picture is already telling you that. 00:08:25.557 --> 00:08:27.810 Backwards is the new idea. 00:08:28.007 --> 00:08:31.593 An edge carrying one unit could have that unit taken away again, 00:08:31.676 --> 00:08:35.449 so the residual graph also holds a reverse arrow along it, pointing 00:08:35.449 --> 00:08:40.175 back the way the flow came, with capacity equal to the flow currently on the edge. 00:08:41.088 --> 00:08:45.385 Here they all are, one for every edge that is carrying something. 00:08:45.697 --> 00:08:47.741 Most of them are no use to us. 00:08:47.938 --> 00:08:49.538 These two come out of the sink, 00:08:49.621 --> 00:08:53.779 and these two point back at the source, and reaching them gets us nowhere new. 00:08:54.575 --> 00:08:56.770 This one is the one that matters. 00:08:57.222 --> 00:09:01.135 Two units are currently running from a down to b, so the residual 00:09:01.135 --> 00:09:06.244 graph offers two units of capacity going the other way, from b back up to a. 00:09:07.041 --> 00:09:10.873 Now search again, and this time walk on residual edges. 00:09:11.186 --> 00:09:13.729 From the source into b there is room. 00:09:14.181 --> 00:09:17.479 From b, take the backward arrow up to a. 00:09:17.676 --> 00:09:21.205 And from a there is one unit of room left into the sink. 00:09:21.816 --> 00:09:27.982 That is a path from the source to the sink: s, then b, then a, then t. 00:09:28.086 --> 00:09:32.614 Its bottleneck is one unit, so one unit is what we push along it. 00:09:33.411 --> 00:09:36.616 The edge from the source into b goes up to two. 00:09:36.813 --> 00:09:42.967 The edge from a to b is walked backwards, so it goes down by one, from two to one. 00:09:43.419 --> 00:09:46.311 And the edge from a to the sink goes up to two. 00:09:47.107 --> 00:09:48.884 The value is five. 00:09:48.988 --> 00:09:51.264 So check that nothing has broken. 00:09:51.461 --> 00:09:56.208 At a, three units arrive from the source, one leaves downward into b, 00:09:56.291 --> 00:09:58.404 and two leave across to the sink. 00:09:58.601 --> 00:10:00.599 Three in and three out. 00:10:01.395 --> 00:10:05.248 At b, two units arrive from the source and one arrives from a, 00:10:05.331 --> 00:10:07.271 and three leave for the sink. 00:10:07.583 --> 00:10:09.918 Three in and three out again. 00:10:10.021 --> 00:10:15.201 Every capacity is respected, and this is a perfectly legal flow of value five. 00:10:15.997 --> 00:10:19.444 And look at what the backward step actually did to the picture. 00:10:19.527 --> 00:10:24.183 It did not cancel the first path, and it did not throw anything away. 00:10:24.380 --> 00:10:29.591 One unit that used to go source, a, b, sink now travels source, a, sink. 00:10:29.674 --> 00:10:34.400 And one unit that previously had nowhere to go now travels source, b, sink. 00:10:34.884 --> 00:10:39.516 The bookkeeping did the rerouting for us. Nobody had to spot that swap in advance, 00:10:39.516 --> 00:10:42.568 and nobody had to go back and edit an earlier decision. 00:10:42.651 --> 00:10:45.667 The backward arrow made an old choice reversible, 00:10:45.750 --> 00:10:49.269 and the search took the reversal without knowing it was being clever. 00:10:49.973 --> 00:10:52.237 That is the whole algorithm. 00:10:52.434 --> 00:10:56.368 Find a path in the residual graph, push the bottleneck along it, 00:10:56.451 --> 00:11:01.258 rebuild the residual graph, and repeat until there is no path left. 00:11:01.362 --> 00:11:03.534 It is called Ford Fulkerson. 00:11:04.238 --> 00:11:09.672 Which leaves exactly one question. When it stops, has it actually won? 00:11:09.776 --> 00:11:14.119 Or is there some cleverer route that this procedure simply cannot see? 00:11:15.252 --> 00:11:17.354 Here is the flow we finished with. 00:11:17.458 --> 00:11:21.244 Five units, and every number on it is the number we left it at. 00:11:21.556 --> 00:11:24.236 The question now is not how to improve it. 00:11:24.319 --> 00:11:27.269 The question is how to be certain that nobody can. 00:11:28.066 --> 00:11:30.258 So run the search one more time, 00:11:30.341 --> 00:11:34.614 and this time watch where it can get to, rather than whether it finishes. 00:11:35.066 --> 00:11:39.723 Start at the source, and mark every node the residual graph can still reach. 00:11:40.519 --> 00:11:45.394 From the source, the edge to a is full, three units on a capacity of three, 00:11:45.477 --> 00:11:47.521 so there is no room that way. 00:11:47.718 --> 00:11:50.850 The edge to b carries two units on a capacity of four, 00:11:50.933 --> 00:11:54.382 so it has two units of room, and b is reachable. 00:11:55.295 --> 00:11:59.348 From b, the edge to the sink is full as well, three on three. 00:11:59.544 --> 00:12:02.713 But one unit is currently flowing from a down into b, 00:12:02.796 --> 00:12:05.803 so the residual graph has a backward arrow there. 00:12:06.000 --> 00:12:08.915 Walk it, and a is reachable too. 00:12:09.618 --> 00:12:14.437 And from a, the edge to the sink carries two units on a capacity of two. 00:12:14.634 --> 00:12:15.633 Full. 00:12:15.737 --> 00:12:20.170 So the search stops there, with the source, a and b all marked, 00:12:20.253 --> 00:12:22.355 and the sink not marked at all. 00:12:23.268 --> 00:12:25.646 Call that set of marked nodes S. 00:12:25.729 --> 00:12:28.273 It contains the source by construction. 00:12:28.376 --> 00:12:31.047 And it does not contain the sink, because if it 00:12:31.047 --> 00:12:35.042 did we would have found an augmenting path, and we would not have stopped. 00:12:36.256 --> 00:12:41.458 So S and everything outside it form a cut, and we already know how to price a cut. 00:12:41.771 --> 00:12:46.436 The edges crossing forwards out of S are a to t, with capacity two, 00:12:46.519 --> 00:12:49.388 and b to t, with capacity three. 00:12:50.440 --> 00:12:52.284 Two plus three is five. 00:12:52.367 --> 00:12:54.304 The cut has capacity five. 00:12:54.387 --> 00:12:56.524 And the flow has value five. 00:12:56.720 --> 00:12:58.425 The ceiling we could never beat, 00:12:58.508 --> 00:13:01.922 and the flow we actually built, are the same number. 00:13:02.974 --> 00:13:04.505 That is not a coincidence, 00:13:04.588 --> 00:13:08.931 and the reason is worth seeing properly, because the reason is the whole proof. 00:13:10.327 --> 00:13:14.923 Take any edge that crosses forwards out of S, from a marked node to an unmarked one. 00:13:15.006 --> 00:13:17.015 It has to be completely full. 00:13:17.626 --> 00:13:21.318 Because if it had any room left on it at all, the search would have walked along 00:13:21.318 --> 00:13:24.709 it, and the node at the far end would have been marked as well. 00:13:24.813 --> 00:13:26.357 It is not marked. 00:13:26.461 --> 00:13:28.052 So the edge is full. 00:13:29.104 --> 00:13:33.958 Now take an edge crossing the other way, from an unmarked node back into S. 00:13:34.062 --> 00:13:36.640 That one has to be completely empty. 00:13:37.123 --> 00:13:39.037 Because if it were carrying anything, 00:13:39.120 --> 00:13:42.952 the residual graph would hold a backward arrow along it, running from the marked 00:13:42.952 --> 00:13:47.341 end to the unmarked end, and the search would have crossed that arrow instead. 00:13:47.538 --> 00:13:49.292 Again, it did not. 00:13:49.775 --> 00:13:52.747 In this particular network there is nothing to check on that side, 00:13:52.747 --> 00:13:55.160 because nothing at all leaves the sink. 00:13:55.243 --> 00:13:59.342 But that half of the argument is exactly what makes the general theorem work. 00:13:59.768 --> 00:14:01.963 So put the two halves together. 00:14:02.066 --> 00:14:07.280 The value of a flow is what crosses the cut forwards, minus whatever crosses back. 00:14:08.077 --> 00:14:10.513 Forwards, every crossing edge is full, 00:14:10.596 --> 00:14:13.871 so that first sum is the entire capacity of the cut. 00:14:14.068 --> 00:14:19.363 Backwards, every crossing edge is empty, so nothing whatsoever is subtracted. 00:14:20.159 --> 00:14:23.675 So the value of the flow is exactly the capacity of this cut. 00:14:23.758 --> 00:14:28.495 And we already knew that no flow anywhere can exceed the capacity of any cut. 00:14:28.808 --> 00:14:33.128 Two facts, and between them they nail the answer down completely. 00:14:33.832 --> 00:14:35.479 No flow can beat five, 00:14:35.562 --> 00:14:39.614 because this cut has capacity five and our flow reaches five. 00:14:39.718 --> 00:14:42.119 So our flow is a maximum flow. 00:14:42.202 --> 00:14:44.221 And no cut can dip below five, 00:14:44.304 --> 00:14:47.915 because the flow has value five and this cut achieves it. 00:14:48.112 --> 00:14:50.295 So this cut is a minimum cut. 00:14:50.999 --> 00:14:53.693 Maximum flow equals minimum cut. 00:14:53.797 --> 00:14:55.690 And notice how it arrived. 00:14:56.003 --> 00:14:57.835 We never went looking for the cut. 00:14:57.918 --> 00:15:01.633 We ran out of augmenting paths, and the cut was already sitting there 00:15:01.633 --> 00:15:05.721 in the leftovers, made of exactly the nodes the search could still see. 00:15:06.634 --> 00:15:11.464 That is a genuinely useful property of the algorithm, and not just a pretty fact. 00:15:11.917 --> 00:15:14.831 When it stops, it hands you a certificate. 00:15:14.935 --> 00:15:18.997 Anyone who doubts that five is the best possible can be shown two edges, 00:15:19.080 --> 00:15:23.248 of total capacity five, that every single unit has to cross. 00:15:24.161 --> 00:15:27.505 One more thing before we finish, because this theorem turns up in places 00:15:27.505 --> 00:15:30.141 that have nothing obvious to do with pipes at all. 00:15:31.273 --> 00:15:32.617 Here are three people, 00:15:32.701 --> 00:15:37.102 and three jobs, and a line whenever a person is able to do a job. 00:15:37.299 --> 00:15:40.918 The problem is to give as many people as possible a job of their own, 00:15:41.002 --> 00:15:42.617 with nobody sharing. 00:15:43.669 --> 00:15:46.201 The lines say who can do what. 00:15:46.653 --> 00:15:50.856 Person one is able to take either the first job or the second. 00:15:50.960 --> 00:15:54.188 Person two is qualified for the first job alone. 00:15:54.292 --> 00:15:57.532 And person three can take the second job or the third. 00:15:58.329 --> 00:16:02.067 This is bipartite matching, and it looks like a completely different kind 00:16:02.067 --> 00:16:04.560 of question from pushing water down pipes. 00:16:04.644 --> 00:16:06.990 It is exactly the same question. 00:16:07.531 --> 00:16:10.771 Add a source on the left, joined to every person. 00:16:10.875 --> 00:16:14.088 Add a sink on the right, joined to every job. 00:16:14.172 --> 00:16:17.958 And give every edge in the whole picture a capacity of one. 00:16:18.569 --> 00:16:20.578 Now push flow through it. 00:16:20.682 --> 00:16:25.230 A unit of flow leaving the source has to pick one person, because that person's own 00:16:25.314 --> 00:16:29.483 edge from the source has capacity one and can carry nothing more. 00:16:30.535 --> 00:16:34.842 It then crosses to a job that person can do, and leaves through that job's edge 00:16:34.842 --> 00:16:37.765 to the sink, which also has capacity one. 00:16:37.849 --> 00:16:41.457 So one unit of flow is exactly one person doing one job, 00:16:41.541 --> 00:16:44.200 and no job can ever be taken twice. 00:16:45.113 --> 00:16:48.167 The value of the flow is the size of the matching. 00:16:48.364 --> 00:16:52.276 Maximum flow is maximum matching, and it is the same algorithm, 00:16:52.276 --> 00:16:54.100 completely unchanged. 00:16:55.013 --> 00:16:57.332 Now watch the same mistake happen again. 00:16:57.416 --> 00:17:00.641 Send the first unit through person one to job one. 00:17:00.725 --> 00:17:04.243 And send a second unit through person three to job three. 00:17:05.040 --> 00:17:10.761 Now person two. The only job on their list is job one, and job one is taken. 00:17:10.845 --> 00:17:14.444 Greedy stops with two people placed and one left out in the cold. 00:17:15.241 --> 00:17:17.122 But the residual graph has a backward 00:17:17.122 --> 00:17:21.988 arrow on the edge from person one to job one, because that edge is carrying a unit. 00:17:22.184 --> 00:17:23.276 Follow it. 00:17:23.817 --> 00:17:25.920 From the source to person two. 00:17:26.116 --> 00:17:27.847 Across to job one. 00:17:28.160 --> 00:17:30.088 Backwards up to person one. 00:17:30.284 --> 00:17:33.315 Across to job two, which nobody has taken. 00:17:33.512 --> 00:17:35.080 And out to the sink. 00:17:35.993 --> 00:17:40.196 Push one unit along that path, and the picture rearranges itself. 00:17:40.300 --> 00:17:42.855 Person one moves over to job two. 00:17:43.051 --> 00:17:45.246 Person two takes job one. 00:17:45.443 --> 00:17:47.835 And person three keeps job three. 00:17:48.632 --> 00:17:52.429 Three people, three jobs, and nobody sharing. 00:17:52.742 --> 00:17:56.191 The backward edge did exactly what a person would do out loud. 00:17:56.387 --> 00:17:59.407 You take that one, and I will take another. 00:18:00.320 --> 00:18:02.712 And the minimum cut says something too. 00:18:03.025 --> 00:18:06.880 When a matching cannot cover everybody, the cut tells you why. 00:18:07.077 --> 00:18:11.044 It exhibits a set of people whose lists of jobs, taken together, 00:18:11.128 --> 00:18:13.451 are simply too short to go round. 00:18:14.665 --> 00:18:16.149 That is Hall's condition, 00:18:16.233 --> 00:18:19.403 and it falls straight out of the theorem we have just proved. 00:18:20.200 --> 00:18:21.593 So there it is. 00:18:21.790 --> 00:18:24.450 Push flow along augmenting paths. 00:18:24.553 --> 00:18:29.094 When you get stuck, let the residual graph undo an earlier decision. 00:18:29.197 --> 00:18:33.923 And when even that runs out, the nodes you can still reach form a cut, its capacity 00:18:33.923 --> 00:18:38.161 equals the flow you are holding, and neither number can move any further. 00:18:39.213 --> 00:18:42.035 Maximum flow equals minimum cut.