# Maximum Flow Equals Minimum Cut: Proof by Example > A proof you can watch happen. We take one small directed network with capacities, define what a flow is and what a cut is, and then run the augmenting path method by hand: three paths, four units, and a dead end. The residual graph then supplies a backward arrow that lets a later path undo an earlier bad decision, and the flow climbs to five. When no augmenting path is left, the vertices still reachable in the residual graph turn out to be exactly one side of a cut, and that cut's capacity is five as well. Maximum flow equals minimum cut, arrived at rather than asserted. The lecture closes with bipartite matching, where the same backward arrow performs the swap a person would make out loud. - Canonical watch page: [Maximum Flow Equals Minimum Cut: Proof by Example](https://academa.ai/lectures/maxflow-mincut-theorem) - Publisher: [Academa, Inc.](https://academa.ai) - Subject: Computer Science - Published: 2026-08-28T18:45:48.185Z - Updated: 2026-08-28T18:45:48.185Z - Duration: PT1139S (18 minutes 59 seconds) - Chapters: 4 - Views: 0 - Language: en-US - Access: Free - Video stream: [HLS content](https://academa.ai/media/l/01M14TXHCXEMC5NM1W4SXGF7P6/0/dark/master.m3u8) - Audiovisual record: [Semantic JSON](https://academa.ai/media/l/01M14TXHCXEMC5NM1W4SXGF7P6/0/semantic.json) - Thumbnail: [Image](https://academa.ai/media/l/01M14TXHCXEMC5NM1W4SXGF7P6/0/dark/poster.jpg) ## Description Max flow equals min cut, worked by hand on one small network: augmenting paths, a residual backward edge, and the cut that certifies the answer. ## Chapters - [00:00–05:9.648 · Flows and Cuts](https://academa.ai/lectures/maxflow-mincut-theorem?t=0) - [05:9.648–11:18.067 · Augmenting Paths and the Residual Graph](https://academa.ai/lectures/maxflow-mincut-theorem?t=309.6483958333333) - [11:18.067–15:41.611 · The Cut That Certifies It](https://academa.ai/lectures/maxflow-mincut-theorem?t=678.0674166666668) - [15:41.611–18:59 · Matching, and Why It Is the Same Problem](https://academa.ai/lectures/maxflow-mincut-theorem?t=941.6113333333335) ## Transcript ### [00:00 · Flows and Cuts](https://academa.ai/lectures/maxflow-mincut-theorem?t=0) Here is a question with a genuinely beautiful answer. You have a network of pipes, and every pipe has a limit on how much it can carry. You want to push as much as possible from one end of the thing to the other. How much can you push, and how would you ever prove that you cannot do better? This is the network we will work with for the whole lecture. There are four nodes in it. s is the source, where everything starts, and t is the sink, where everything has to end up. In between sit two junctions, called a and b. Five directed edges join them up. The gray number on each edge is its capacity, the most that edge could ever carry. The green number beside it is how much is flowing along it right now, which for the moment is nothing at all. Read the capacities off. The source can send three units into a, and four into b. The edge from a down to b can carry two. And into the sink, a to t can carry two, and b to t can carry three. The arrows matter. An edge from a to b is not an edge from b to a, and that capacity of two is a limit on units travelling downward only. Nothing at all is allowed to travel back up it. A flow is an assignment of a number to every edge, and it has to obey two rules. The first one is obvious. No edge may carry more than its capacity, and no edge may carry a negative amount. The second rule is conservation. At every node except the source and the sink, whatever flows in has to flow out again. A junction does not store anything, and it does not invent anything either. Let me push something through, so you can watch both rules working. Send two units out of the source along the top edge into a. Now a has two units arriving and nothing leaving, which breaks conservation. So send them onward. One unit goes down to b, and one goes straight across to the sink. And b has one unit arriving, so one unit leaves for the sink. Every junction balances now, no edge is over its capacity, and what you are looking at is a perfectly legal flow. Its value is simply what leaves the source, which here is two units. The two units arriving at the sink agree with that, and they always will, because nothing is created or destroyed in the middle. It is not a very good flow. The edge from the source into b is carrying nothing whatsoever, and the edge out of b has two units of room going spare. We are going to do considerably better than this. Now the other half of the story, and it is the half that does the proving. Take any way at all of splitting the four nodes into two groups, with the source in one group and the sink in the other. That is called a cut. Here is the simplest one there is. Draw a line just to the right of the source, so that the source is on its own and a, b and the sink are together on the far side. Two edges cross it, s to a and s to b. The capacity of a cut is the total capacity of the edges crossing it forwards. Three plus four is seven, so this particular cut has capacity seven. And here is why that matters so much. Every single unit of flow begins at the source, on the left of that line, and ends at the sink, on the right of it. So every unit has to cross somewhere, and the value of the flow can never be more than seven. That is worth saying twice, because the entire proof rests on it. A cut is a wall. Whatever the flow does, however cleverly it is routed, it has to get through the wall, and the wall has a fixed total width. Try a different one. Move the line over to the far side, so that the source, a and b are together and only the sink is on its own. Now the crossing edges are a to t and b to t. Their capacities are two and three, so this cut has capacity five. Five is a far better piece of information than seven was, because it says the flow can never get past five. A network this small has only four cuts, one for each way of deciding which junctions go on the source side. The other two come out at eight and at six. So five is the best ceiling any cut here can give us. So every cut hands us a ceiling, and the smallest cut hands us the best ceiling this kind of argument could ever produce. The theorem we are going to prove says something much stronger than that. The best ceiling is always reached exactly. Maximum flow equals minimum cut. Not at most. Equal. In a few minutes you will watch the flow climb to five, and then watch a cut of capacity five appear out of the leftovers, and the two numbers will meet in the middle. ### [05:9.648 · Augmenting Paths and the Residual Graph](https://academa.ai/lectures/maxflow-mincut-theorem?t=309.6483958333333) We have a network, and we have the rules a flow has to obey. What we need now is a way to actually find the biggest flow, and the method is almost embarrassingly simple. Find a route from the source to the sink that still has room on every edge, and push as much along it as the tightest edge will allow. A route like that has a name. It is called an augmenting path, because sending flow along it augments what we already have. The amount it can take is decided by whichever edge has the least room left, and that edge is called the bottleneck. Nothing is flowing yet, so every edge has all of its room available. Take the top edge into a, then the edge down to b, then out of b to the sink. The room on those three edges is three, then two, then three. The smallest is two, so two units is everything this path can carry. Push it through. All three edges on the path go up by two, and the flow we are holding now has value two. Now look at the middle edge. Two units on a capacity of two, which means it is completely full. Nothing more can ever go along it while this flow stands. Look for another path. From the source into a there is one unit of room left, and from a straight across to the sink there are two units. The bottleneck is one, so one unit is what we send. Three units are leaving the source now. And the edge out of the source into a is full as well, three out of three, with nothing to spare. One more path. From the source into b there is plenty of room, three units of it. But the edge from b to the sink has only one unit left, so one unit is all we can send along this one. Four units. And now we are stuck. Look at what is left. The edge from the source to a is full, so a cannot be reached that way at all. The edge from the source to b does have room, so we can get as far as b. But b to t is full, and b has no other edge leading forward. There is nowhere to go. So the simple method has run out of paths at a value of four. And the uncomfortable question is whether four really is the answer, or whether we made a bad choice somewhere and the method has no way at all of noticing. We did make a bad choice, and it was the very first path. Those two units went from a down into b, and then out of b to the sink, and between them they used up nearly the whole edge into the sink. But b had a supply of its own, coming straight from the source, and now there is no room left for it. The two units that came down from a squeezed it out. What we would like to do is take one of those two units back off the edge from a to b, push it across from a to the sink instead, and let a unit from the source into b move into the space it leaves behind. But the method as we stated it cannot walk backwards. So we change what the method is allowed to walk on. This is the residual graph, and it records not what is flowing, but what could still change. Forwards, it is what you would expect. An edge of capacity four carrying one unit has three units of room, so three more could still be pushed along it. Every number on the picture is already telling you that. Backwards is the new idea. An edge carrying one unit could have that unit taken away again, so the residual graph also holds a reverse arrow along it, pointing back the way the flow came, with capacity equal to the flow currently on the edge. Here they all are, one for every edge that is carrying something. Most of them are no use to us. These two come out of the sink, and these two point back at the source, and reaching them gets us nowhere new. This one is the one that matters. Two units are currently running from a down to b, so the residual graph offers two units of capacity going the other way, from b back up to a. Now search again, and this time walk on residual edges. From the source into b there is room. From b, take the backward arrow up to a. And from a there is one unit of room left into the sink. That is a path from the source to the sink: s, then b, then a, then t. Its bottleneck is one unit, so one unit is what we push along it. The edge from the source into b goes up to two. The edge from a to b is walked backwards, so it goes down by one, from two to one. And the edge from a to the sink goes up to two. The value is five. So check that nothing has broken. At a, three units arrive from the source, one leaves downward into b, and two leave across to the sink. Three in and three out. At b, two units arrive from the source and one arrives from a, and three leave for the sink. Three in and three out again. Every capacity is respected, and this is a perfectly legal flow of value five. And look at what the backward step actually did to the picture. It did not cancel the first path, and it did not throw anything away. One unit that used to go source, a, b, sink now travels source, a, sink. And one unit that previously had nowhere to go now travels source, b, sink. The bookkeeping did the rerouting for us. Nobody had to spot that swap in advance, and nobody had to go back and edit an earlier decision. The backward arrow made an old choice reversible, and the search took the reversal without knowing it was being clever. That is the whole algorithm. Find a path in the residual graph, push the bottleneck along it, rebuild the residual graph, and repeat until there is no path left. It is called Ford Fulkerson. Which leaves exactly one question. When it stops, has it actually won? Or is there some cleverer route that this procedure simply cannot see? ### [11:18.067 · The Cut That Certifies It](https://academa.ai/lectures/maxflow-mincut-theorem?t=678.0674166666668) Here is the flow we finished with. Five units, and every number on it is the number we left it at. The question now is not how to improve it. The question is how to be certain that nobody can. So run the search one more time, and this time watch where it can get to, rather than whether it finishes. Start at the source, and mark every node the residual graph can still reach. From the source, the edge to a is full, three units on a capacity of three, so there is no room that way. The edge to b carries two units on a capacity of four, so it has two units of room, and b is reachable. From b, the edge to the sink is full as well, three on three. But one unit is currently flowing from a down into b, so the residual graph has a backward arrow there. Walk it, and a is reachable too. And from a, the edge to the sink carries two units on a capacity of two. Full. So the search stops there, with the source, a and b all marked, and the sink not marked at all. Call that set of marked nodes S. It contains the source by construction. And it does not contain the sink, because if it did we would have found an augmenting path, and we would not have stopped. So S and everything outside it form a cut, and we already know how to price a cut. The edges crossing forwards out of S are a to t, with capacity two, and b to t, with capacity three. Two plus three is five. The cut has capacity five. And the flow has value five. The ceiling we could never beat, and the flow we actually built, are the same number. That is not a coincidence, and the reason is worth seeing properly, because the reason is the whole proof. Take any edge that crosses forwards out of S, from a marked node to an unmarked one. It has to be completely full. Because if it had any room left on it at all, the search would have walked along it, and the node at the far end would have been marked as well. It is not marked. So the edge is full. Now take an edge crossing the other way, from an unmarked node back into S. That one has to be completely empty. Because if it were carrying anything, the residual graph would hold a backward arrow along it, running from the marked end to the unmarked end, and the search would have crossed that arrow instead. Again, it did not. In this particular network there is nothing to check on that side, because nothing at all leaves the sink. But that half of the argument is exactly what makes the general theorem work. So put the two halves together. The value of a flow is what crosses the cut forwards, minus whatever crosses back. Forwards, every crossing edge is full, so that first sum is the entire capacity of the cut. Backwards, every crossing edge is empty, so nothing whatsoever is subtracted. So the value of the flow is exactly the capacity of this cut. And we already knew that no flow anywhere can exceed the capacity of any cut. Two facts, and between them they nail the answer down completely. No flow can beat five, because this cut has capacity five and our flow reaches five. So our flow is a maximum flow. And no cut can dip below five, because the flow has value five and this cut achieves it. So this cut is a minimum cut. Maximum flow equals minimum cut. And notice how it arrived. We never went looking for the cut. We ran out of augmenting paths, and the cut was already sitting there in the leftovers, made of exactly the nodes the search could still see. That is a genuinely useful property of the algorithm, and not just a pretty fact. When it stops, it hands you a certificate. Anyone who doubts that five is the best possible can be shown two edges, of total capacity five, that every single unit has to cross. One more thing before we finish, because this theorem turns up in places that have nothing obvious to do with pipes at all. ### [15:41.611 · Matching, and Why It Is the Same Problem](https://academa.ai/lectures/maxflow-mincut-theorem?t=941.6113333333335) Here are three people, and three jobs, and a line whenever a person is able to do a job. The problem is to give as many people as possible a job of their own, with nobody sharing. The lines say who can do what. Person one is able to take either the first job or the second. Person two is qualified for the first job alone. And person three can take the second job or the third. This is bipartite matching, and it looks like a completely different kind of question from pushing water down pipes. It is exactly the same question. Add a source on the left, joined to every person. Add a sink on the right, joined to every job. And give every edge in the whole picture a capacity of one. Now push flow through it. A unit of flow leaving the source has to pick one person, because that person's own edge from the source has capacity one and can carry nothing more. It then crosses to a job that person can do, and leaves through that job's edge to the sink, which also has capacity one. So one unit of flow is exactly one person doing one job, and no job can ever be taken twice. The value of the flow is the size of the matching. Maximum flow is maximum matching, and it is the same algorithm, completely unchanged. Now watch the same mistake happen again. Send the first unit through person one to job one. And send a second unit through person three to job three. Now person two. The only job on their list is job one, and job one is taken. Greedy stops with two people placed and one left out in the cold. But the residual graph has a backward arrow on the edge from person one to job one, because that edge is carrying a unit. Follow it. From the source to person two. Across to job one. Backwards up to person one. Across to job two, which nobody has taken. And out to the sink. Push one unit along that path, and the picture rearranges itself. Person one moves over to job two. Person two takes job one. And person three keeps job three. Three people, three jobs, and nobody sharing. The backward edge did exactly what a person would do out loud. You take that one, and I will take another. And the minimum cut says something too. When a matching cannot cover everybody, the cut tells you why. It exhibits a set of people whose lists of jobs, taken together, are simply too short to go round. That is Hall's condition, and it falls straight out of the theorem we have just proved. So there it is. Push flow along augmenting paths. When you get stuck, let the residual graph undo an earlier decision. And when even that runs out, the nodes you can still reach form a cut, its capacity equals the flow you are holding, and neither number can move any further. Maximum flow equals minimum cut. ## About Academa, Inc. Academa makes technical knowledge easier to understand through visual lectures and lets learners request new lecture videos on the topics they need. ## Complete audiovisual record Immutable source: [semantic.json](https://academa.ai/media/l/01M14TXHCXEMC5NM1W4SXGF7P6/0/semantic.json) Record version: 1. Render attempt: 0. ### How to read this timeline Each scene owns its object identifiers. A beat's board is the complete board when listed, empty when marked empty, and unchanged from the nearest earlier listed board in the same scene when marked unchanged. Action times are absolute positions in the published video. ### Scene 1: [Flows and Cuts](https://academa.ai/lectures/maxflow-mincut-theorem?t=0) Span: 00:00–05:9.648 (0s–309.6483958333333s). #### Objects - bound: a Math \[text\] that says "$\|f\| \<= 7$" - cap\_rule: a Math \[text\] that says "$0 \<= f(e) \<= c(e)$" - card: a Title that says "Algorithms — Maximum Flow Equals Minimum Cut: Proof by Example" - cons\_rule: a Math \[text\] that says "$sum upright("in") = sum upright("out")$" - cut\_cap: a Math \[text\] that says "$c(S) = 3 + 4 = 7$" - cut\_def: a Panel that says "A cut splits the nodes into two sides, with $s$ on one side and $t$ on the other. Its capacity is the total capacity of the edges pointing from the $s$ side to the $t$ side." - cut\_one: a Line \[magenta\] drawn in network (start=(1.9, 0.15), end=(1.9, 4.55), dashed=True) - cut\_two: a Line \[magenta\] drawn in network (start=(5.1, 0.15), end=(5.1, 4.55), dashed=True) - edge\_ab: a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True) - edge\_at: a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True) - edge\_bt: a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True) - edge\_sa: a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True) - edge\_sb: a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True) - f\_ab: a VariableNumber (format\_spec='.0f') - f\_at: a VariableNumber (format\_spec='.0f') - f\_bt: a VariableNumber (format\_spec='.0f') - f\_sa: a VariableNumber (format\_spec='.0f') - flow\_ab: a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False) - flow\_at: a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False) - flow\_bt: a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False) - flow\_sa: a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False) - flow\_sb: a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False) - head\_cut: a Heading that says "Every Cut Is a Ceiling" - head\_network: a Heading that says "A Network With Capacities" - network: a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)) - node\_a: a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13) - node\_b: a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13) - node\_s: a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13) - node\_t: a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13) - point: a Point \[yellow\] drawn in network (location=(3.2, 4.0)) - point\_2: a Point \[yellow\] drawn in network (location=(3.2, 0.7)) - point\_3: a Point \[yellow\] drawn in network (location=(3.2, 4.0)) - point\_4: a Point \[yellow\] drawn in network (location=(3.2, 0.7)) - theorem: a Math \[text\] that says "$max \|f\| = min c(S)$" - value\_def: a Math \[text\] that says "$\|f\| = 2$" #### Beats ##### [00:00](https://academa.ai/lectures/maxflow-mincut-theorem?t=0) Narration: Here is a question with a genuinely beautiful answer. You have a network of pipes, and every pipe has a limit on how much it can carry. You want to push as much as possible from one end of the thing to the other. How much can you push, and how would you ever prove that you cannot do better? Board: Empty. Actions: - [00:00](https://academa.ai/lectures/maxflow-mincut-theorem?t=0): card is shown on the screen, written out. - [00:1.5](https://academa.ai/lectures/maxflow-mincut-theorem?t=1.5): card: enter:write-left-to-right. - [00:17.183](https://academa.ai/lectures/maxflow-mincut-theorem?t=17.1825): card is hidden from the screen — left the board. ##### [00:18.383](https://academa.ai/lectures/maxflow-mincut-theorem?t=18.3825) Narration: This is the network we will work with for the whole lecture. There are four nodes in it. s is the source, where everything starts, and t is the sink, where everything has to end up. In between sit two junctions, called a and b. Board: Unchanged from the preceding beat in this scene. Actions: - [00:18.383](https://academa.ai/lectures/maxflow-mincut-theorem?t=18.3825): head\_network is shown on the screen, written out. - [00:18.383](https://academa.ai/lectures/maxflow-mincut-theorem?t=18.3825): network is shown on the screen, written out. - [00:24.28](https://academa.ai/lectures/maxflow-mincut-theorem?t=24.279999999999998): node\_s is shown on the screen, written out. - [00:27.136](https://academa.ai/lectures/maxflow-mincut-theorem?t=27.136): node\_t is shown on the screen, written out. - [00:31.478](https://academa.ai/lectures/maxflow-mincut-theorem?t=31.477999999999998): node\_a is shown on the screen, written out. - [00:31.638](https://academa.ai/lectures/maxflow-mincut-theorem?t=31.637999999999998): node\_b is shown on the screen, written out. ##### [00:34.493](https://academa.ai/lectures/maxflow-mincut-theorem?t=34.493) Narration: Five directed edges join them up. The gray number on each edge is its capacity, the most that edge could ever carry. The green number beside it is how much is flowing along it right now, which for the moment is nothing at all. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_network — a Heading that says "A Network With Capacities"; node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13) Actions: - [00:35.701](https://academa.ai/lectures/maxflow-mincut-theorem?t=35.701): edge\_sa is shown on the screen, drawn. - [00:35.831](https://academa.ai/lectures/maxflow-mincut-theorem?t=35.831): edge\_sb is shown on the screen, drawn. - [00:35.961](https://academa.ai/lectures/maxflow-mincut-theorem?t=35.961): edge\_ab is shown on the screen, drawn. - [00:36.091](https://academa.ai/lectures/maxflow-mincut-theorem?t=36.091): edge\_at is shown on the screen, drawn. - [00:36.221](https://academa.ai/lectures/maxflow-mincut-theorem?t=36.221000000000004): edge\_bt is shown on the screen, drawn. - [00:43.514](https://academa.ai/lectures/maxflow-mincut-theorem?t=43.514): flow\_sa is shown on the screen, written out. - [00:43.624](https://academa.ai/lectures/maxflow-mincut-theorem?t=43.624): flow\_sb is shown on the screen, written out. - [00:43.734](https://academa.ai/lectures/maxflow-mincut-theorem?t=43.734): flow\_ab is shown on the screen, written out. - [00:43.844](https://academa.ai/lectures/maxflow-mincut-theorem?t=43.844): flow\_at is shown on the screen, written out. - [00:43.954](https://academa.ai/lectures/maxflow-mincut-theorem?t=43.954): flow\_bt is shown on the screen, written out. ##### [00:50.151](https://academa.ai/lectures/maxflow-mincut-theorem?t=50.151) Narration: Read the capacities off. The source can send three units into a, and four into b. The edge from a down to b can carry two. And into the sink, a to t can carry two, and b to t can carry three. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_network — a Heading that says "A Network With Capacities"; node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False) Actions: - [00:53.646](https://academa.ai/lectures/maxflow-mincut-theorem?t=53.646): edge\_sa is emphasized. - [00:55.41](https://academa.ai/lectures/maxflow-mincut-theorem?t=55.410000000000004): edge\_sa is no longer emphasized. - [00:55.41](https://academa.ai/lectures/maxflow-mincut-theorem?t=55.410000000000004): edge\_sb is emphasized. - [00:58.754](https://academa.ai/lectures/maxflow-mincut-theorem?t=58.754000000000005): edge\_sb is no longer emphasized. - [00:58.754](https://academa.ai/lectures/maxflow-mincut-theorem?t=58.754000000000005): edge\_ab is emphasized. - [01:2.156](https://academa.ai/lectures/maxflow-mincut-theorem?t=62.156000000000006): edge\_ab is no longer emphasized. - [01:2.156](https://academa.ai/lectures/maxflow-mincut-theorem?t=62.156000000000006): edge\_at is emphasized. - [01:4.037](https://academa.ai/lectures/maxflow-mincut-theorem?t=64.037): edge\_at is no longer emphasized. - [01:4.037](https://academa.ai/lectures/maxflow-mincut-theorem?t=64.037): edge\_bt is emphasized. ##### [01:5.427](https://academa.ai/lectures/maxflow-mincut-theorem?t=65.4265) Narration: The arrows matter. An edge from a to b is not an edge from b to a, and that capacity of two is a limit on units travelling downward only. Nothing at all is allowed to travel back up it. Board: Unchanged from the preceding beat in this scene. Actions: - [01:5.427](https://academa.ai/lectures/maxflow-mincut-theorem?t=65.4265): edge\_bt is no longer emphasized. - [01:14.563](https://academa.ai/lectures/maxflow-mincut-theorem?t=74.56300000000002): edge\_ab is indicated — a transient flash. ##### [01:19.308](https://academa.ai/lectures/maxflow-mincut-theorem?t=79.308) Narration: A flow is an assignment of a number to every edge, and it has to obey two rules. The first one is obvious. No edge may carry more than its capacity, and no edge may carry a negative amount. Board: Unchanged from the preceding beat in this scene. Actions: - [01:24.103](https://academa.ai/lectures/maxflow-mincut-theorem?t=84.10300000000001): network moves to a new place on the board. - [01:24.103](https://academa.ai/lectures/maxflow-mincut-theorem?t=84.10300000000001): cap\_rule is shown on the screen, written out. ##### [01:33.608](https://academa.ai/lectures/maxflow-mincut-theorem?t=93.6075) Narration: The second rule is conservation. At every node except the source and the sink, whatever flows in has to flow out again. A junction does not store anything, and it does not invent anything either. Board: cap\_rule — a Math \[text\] that says "$0 \<= f(e) \<= c(e)$"; network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_network — a Heading that says "A Network With Capacities"; node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False) Actions: - [01:34.966](https://academa.ai/lectures/maxflow-mincut-theorem?t=94.966): cons\_rule is shown on the screen, written out. - [01:42.57](https://academa.ai/lectures/maxflow-mincut-theorem?t=102.57000000000001): point is shown on the screen, grown. - [01:43.429](https://academa.ai/lectures/maxflow-mincut-theorem?t=103.429): point\_2 is shown on the screen, grown. - [01:44.57](https://academa.ai/lectures/maxflow-mincut-theorem?t=104.57000000000001): point is hidden from the screen. - [01:45.429](https://academa.ai/lectures/maxflow-mincut-theorem?t=105.429): point\_2 is hidden from the screen. ##### [01:47.547](https://academa.ai/lectures/maxflow-mincut-theorem?t=107.547) Narration: Let me push something through, so you can watch both rules working. Send two units out of the source along the top edge into a. Board: cap\_rule — a Math \[text\] that says "$0 \<= f(e) \<= c(e)$"; cons\_rule — a Math \[text\] that says "$sum upright("in") = sum upright("out")$"; network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_network — a Heading that says "A Network With Capacities"; node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False) Actions: - [01:51.68](https://academa.ai/lectures/maxflow-mincut-theorem?t=111.67999999999999): flow\_sa is redrawn as the numbers it depends on change. - [01:51.68](https://academa.ai/lectures/maxflow-mincut-theorem?t=111.67999999999999): f\_sa ticks to 2.0. ##### [01:55.879](https://academa.ai/lectures/maxflow-mincut-theorem?t=115.87899999999999) Narration: Now a has two units arriving and nothing leaving, which breaks conservation. So send them onward. One unit goes down to b, and one goes straight across to the sink. Board: Unchanged from the preceding beat in this scene. Actions: - [02:4.47](https://academa.ai/lectures/maxflow-mincut-theorem?t=124.46999999999998): flow\_ab is redrawn as the numbers it depends on change. - [02:4.47](https://academa.ai/lectures/maxflow-mincut-theorem?t=124.46999999999998): f\_ab ticks to 1.0. - [02:6.525](https://academa.ai/lectures/maxflow-mincut-theorem?t=126.52499999999999): flow\_at is redrawn as the numbers it depends on change. - [02:6.525](https://academa.ai/lectures/maxflow-mincut-theorem?t=126.52499999999999): f\_at ticks to 1.0. ##### [02:8.449](https://academa.ai/lectures/maxflow-mincut-theorem?t=128.44899999999998) Narration: And b has one unit arriving, so one unit leaves for the sink. Every junction balances now, no edge is over its capacity, and what you are looking at is a perfectly legal flow. Board: Unchanged from the preceding beat in this scene. Actions: - [02:11.606](https://academa.ai/lectures/maxflow-mincut-theorem?t=131.606): flow\_bt is redrawn as the numbers it depends on change. - [02:11.606](https://academa.ai/lectures/maxflow-mincut-theorem?t=131.606): f\_bt ticks to 1.0. ##### [02:20.925](https://academa.ai/lectures/maxflow-mincut-theorem?t=140.92549999999997) Narration: Its value is simply what leaves the source, which here is two units. The two units arriving at the sink agree with that, and they always will, because nothing is created or destroyed in the middle. Board: Unchanged from the preceding beat in this scene. Actions: - [02:21.552](https://academa.ai/lectures/maxflow-mincut-theorem?t=141.55199999999996): value\_def is shown on the screen, written out. - [02:22.655](https://academa.ai/lectures/maxflow-mincut-theorem?t=142.65499999999997): edge\_sa is emphasized. - [02:26.591](https://academa.ai/lectures/maxflow-mincut-theorem?t=146.59099999999995): edge\_sa is no longer emphasized. - [02:26.591](https://academa.ai/lectures/maxflow-mincut-theorem?t=146.59099999999995): edge\_at is emphasized. - [02:26.591](https://academa.ai/lectures/maxflow-mincut-theorem?t=146.59099999999995): edge\_bt is emphasized. - [02:31.444](https://academa.ai/lectures/maxflow-mincut-theorem?t=151.44399999999996): edge\_at is no longer emphasized. - [02:31.444](https://academa.ai/lectures/maxflow-mincut-theorem?t=151.44399999999996): edge\_bt is no longer emphasized. ##### [02:33.484](https://academa.ai/lectures/maxflow-mincut-theorem?t=153.48399999999998) Narration: It is not a very good flow. The edge from the source into b is carrying nothing whatsoever, and the edge out of b has two units of room going spare. We are going to do considerably better than this. Board: cap\_rule — a Math \[text\] that says "$0 \<= f(e) \<= c(e)$"; cons\_rule — a Math \[text\] that says "$sum upright("in") = sum upright("out")$"; value\_def — a Math \[text\] that says "$\|f\| = 2$"; network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_network — a Heading that says "A Network With Capacities"; node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False) Actions: - [02:38.557](https://academa.ai/lectures/maxflow-mincut-theorem?t=158.557): edge\_sb is indicated — a transient flash. - [02:42.667](https://academa.ai/lectures/maxflow-mincut-theorem?t=162.66699999999997): edge\_bt is indicated — a transient flash. - [02:46.916](https://academa.ai/lectures/maxflow-mincut-theorem?t=166.91649999999998): cap\_rule is hidden from the screen — left the board. - [02:46.916](https://academa.ai/lectures/maxflow-mincut-theorem?t=166.91649999999998): cons\_rule is hidden from the screen — left the board. - [02:46.916](https://academa.ai/lectures/maxflow-mincut-theorem?t=166.91649999999998): head\_network is hidden from the screen — left the board. - [02:46.916](https://academa.ai/lectures/maxflow-mincut-theorem?t=166.91649999999998): value\_def is hidden from the screen — left the board. ##### [02:48.116](https://academa.ai/lectures/maxflow-mincut-theorem?t=168.11649999999997) Narration: Now the other half of the story, and it is the half that does the proving. Take any way at all of splitting the four nodes into two groups, with the source in one group and the sink in the other. That is called a cut. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False) Actions: - [02:48.116](https://academa.ai/lectures/maxflow-mincut-theorem?t=168.11649999999997): head\_cut is shown on the screen, written out. - [02:54.223](https://academa.ai/lectures/maxflow-mincut-theorem?t=174.22299999999998): cut\_def is shown on the screen, written out. ##### [03:2.741](https://academa.ai/lectures/maxflow-mincut-theorem?t=182.74099999999999) Narration: Here is the simplest one there is. Draw a line just to the right of the source, so that the source is on its own and a, b and the sink are together on the far side. Two edges cross it, s to a and s to b. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); cut\_def — a Panel that says "A cut splits the nodes into two sides, with $s$ on one side and $t$ on the other. Its capacity is the total capacity of the edges pointing from the $s$ side to the $t$ side."; head\_cut — a Heading that says "Every Cut Is a Ceiling" Actions: - [03:5.69](https://academa.ai/lectures/maxflow-mincut-theorem?t=185.68999999999997): cut\_one is shown on the screen, written out. - [03:14.432](https://academa.ai/lectures/maxflow-mincut-theorem?t=194.43199999999996): edge\_sa is emphasized. - [03:14.432](https://academa.ai/lectures/maxflow-mincut-theorem?t=194.43199999999996): edge\_sb is emphasized. ##### [03:18.341](https://academa.ai/lectures/maxflow-mincut-theorem?t=198.34099999999998) Narration: The capacity of a cut is the total capacity of the edges crossing it forwards. Three plus four is seven, so this particular cut has capacity seven. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); cut\_def — a Panel that says "A cut splits the nodes into two sides, with $s$ on one side and $t$ on the other. Its capacity is the total capacity of the edges pointing from the $s$ side to the $t$ side."; head\_cut — a Heading that says "Every Cut Is a Ceiling"; cut\_one — a Line \[magenta\] drawn in network (start=(1.9, 0.15), end=(1.9, 4.55), dashed=True) Actions: - [03:23.949](https://academa.ai/lectures/maxflow-mincut-theorem?t=203.94899999999996): cut\_cap is shown on the screen, written out. ##### [03:29.285](https://academa.ai/lectures/maxflow-mincut-theorem?t=209.28499999999997) Narration: And here is why that matters so much. Every single unit of flow begins at the source, on the left of that line, and ends at the sink, on the right of it. So every unit has to cross somewhere, and the value of the flow can never be more than seven. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); cut\_def — a Panel that says "A cut splits the nodes into two sides, with $s$ on one side and $t$ on the other. Its capacity is the total capacity of the edges pointing from the $s$ side to the $t$ side."; cut\_cap — a Math \[text\] that says "$c(S) = 3 + 4 = 7$"; head\_cut — a Heading that says "Every Cut Is a Ceiling"; cut\_one — a Line \[magenta\] drawn in network (start=(1.9, 0.15), end=(1.9, 4.55), dashed=True) Actions: - [03:43.739](https://academa.ai/lectures/maxflow-mincut-theorem?t=223.73899999999998): bound is shown on the screen, written out. ##### [03:45.964](https://academa.ai/lectures/maxflow-mincut-theorem?t=225.96449999999996) Narration: That is worth saying twice, because the entire proof rests on it. A cut is a wall. Whatever the flow does, however cleverly it is routed, it has to get through the wall, and the wall has a fixed total width. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); cut\_def — a Panel that says "A cut splits the nodes into two sides, with $s$ on one side and $t$ on the other. Its capacity is the total capacity of the edges pointing from the $s$ side to the $t$ side."; cut\_cap — a Math \[text\] that says "$c(S) = 3 + 4 = 7$"; bound — a Math \[text\] that says "$\|f\| \<= 7$"; head\_cut — a Heading that says "Every Cut Is a Ceiling"; cut\_one — a Line \[magenta\] drawn in network (start=(1.9, 0.15), end=(1.9, 4.55), dashed=True) Actions: - [03:51.468](https://academa.ai/lectures/maxflow-mincut-theorem?t=231.46799999999996): cut\_one is indicated — a transient flash. ##### [03:59.881](https://academa.ai/lectures/maxflow-mincut-theorem?t=239.88099999999997) Narration: Try a different one. Move the line over to the far side, so that the source, a and b are together and only the sink is on its own. Now the crossing edges are a to t and b to t. Board: Unchanged from the preceding beat in this scene. Actions: - [04:1.855](https://academa.ai/lectures/maxflow-mincut-theorem?t=241.855): cut\_one is hidden from the screen. - [04:2.482](https://academa.ai/lectures/maxflow-mincut-theorem?t=242.482): cut\_two is shown on the screen, written out. - [04:9.773](https://academa.ai/lectures/maxflow-mincut-theorem?t=249.773): edge\_sa is no longer emphasized. - [04:9.773](https://academa.ai/lectures/maxflow-mincut-theorem?t=249.773): edge\_sb is no longer emphasized. - [04:9.773](https://academa.ai/lectures/maxflow-mincut-theorem?t=249.773): edge\_at is emphasized. - [04:9.773](https://academa.ai/lectures/maxflow-mincut-theorem?t=249.773): edge\_bt is emphasized. ##### [04:13.228](https://academa.ai/lectures/maxflow-mincut-theorem?t=253.22849999999997) Narration: Their capacities are two and three, so this cut has capacity five. Five is a far better piece of information than seven was, because it says the flow can never get past five. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); cut\_def — a Panel that says "A cut splits the nodes into two sides, with $s$ on one side and $t$ on the other. Its capacity is the total capacity of the edges pointing from the $s$ side to the $t$ side."; cut\_cap — a Math \[text\] that says "$c(S) = 3 + 4 = 7$"; bound — a Math \[text\] that says "$\|f\| \<= 7$"; head\_cut — a Heading that says "Every Cut Is a Ceiling"; cut\_two — a Line \[magenta\] drawn in network (start=(5.1, 0.15), end=(5.1, 4.55), dashed=True) Actions: - [04:17.025](https://academa.ai/lectures/maxflow-mincut-theorem?t=257.025): cut\_cap becomes "$c(S) = 2 + 3 = 5$". - [04:23.503](https://academa.ai/lectures/maxflow-mincut-theorem?t=263.503): bound becomes "$\|f\| \<= 5$". ##### [04:25.229](https://academa.ai/lectures/maxflow-mincut-theorem?t=265.2295) Narration: A network this small has only four cuts, one for each way of deciding which junctions go on the source side. The other two come out at eight and at six. So five is the best ceiling any cut here can give us. Board: Unchanged from the preceding beat in this scene. Actions: - [04:29.908](https://academa.ai/lectures/maxflow-mincut-theorem?t=269.90799999999996): point\_3 is shown on the screen, grown. - [04:31.908](https://academa.ai/lectures/maxflow-mincut-theorem?t=271.90799999999996): point\_3 is hidden from the screen. - [04:32.308](https://academa.ai/lectures/maxflow-mincut-theorem?t=272.30799999999994): point\_4 is shown on the screen, grown. - [04:34.308](https://academa.ai/lectures/maxflow-mincut-theorem?t=274.30799999999994): point\_4 is hidden from the screen. - [04:36.375](https://academa.ai/lectures/maxflow-mincut-theorem?t=276.37499999999994): cut\_two is indicated — a transient flash. ##### [04:39.018](https://academa.ai/lectures/maxflow-mincut-theorem?t=279.018) Narration: So every cut hands us a ceiling, and the smallest cut hands us the best ceiling this kind of argument could ever produce. The theorem we are going to prove says something much stronger than that. The best ceiling is always reached exactly. Board: Unchanged from the preceding beat in this scene. Actions: - [04:48.341](https://academa.ai/lectures/maxflow-mincut-theorem?t=288.341): theorem is shown on the screen, written out. ##### [04:53.179](https://academa.ai/lectures/maxflow-mincut-theorem?t=293.179) Narration: Maximum flow equals minimum cut. Not at most. Equal. In a few minutes you will watch the flow climb to five, and then watch a cut of capacity five appear out of the leftovers, and the two numbers will meet in the middle. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); cut\_def — a Panel that says "A cut splits the nodes into two sides, with $s$ on one side and $t$ on the other. Its capacity is the total capacity of the edges pointing from the $s$ side to the $t$ side."; cut\_cap — a Math \[text\] that says "$c(S) = 3 + 4 = 7$"; bound — a Math \[text\] that says "$\|f\| \<= 7$"; theorem — a Math \[text\] that says "$max \|f\| = min c(S)$"; head\_cut — a Heading that says "Every Cut Is a Ceiling"; cut\_two — a Line \[magenta\] drawn in network (start=(5.1, 0.15), end=(5.1, 4.55), dashed=True) Actions: - [04:58.229](https://academa.ai/lectures/maxflow-mincut-theorem?t=298.229): A box is drawn around theorem. - [05:5.288](https://academa.ai/lectures/maxflow-mincut-theorem?t=305.28799999999995): cut\_two is indicated — a transient flash. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): bound is hidden from the screen — left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): cut\_cap is hidden from the screen — left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): cut\_def is hidden from the screen — left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): head\_cut is hidden from the screen — left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): network is hidden from the screen — left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): node\_s is hidden from the screen — network left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): node\_t is hidden from the screen — network left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): node\_a is hidden from the screen — network left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): node\_b is hidden from the screen — network left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): edge\_sa is hidden from the screen — network left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): edge\_sb is hidden from the screen — network left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): edge\_ab is hidden from the screen — network left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): edge\_at is hidden from the screen — network left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): edge\_bt is hidden from the screen — network left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): flow\_sa is hidden from the screen — network left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): flow\_sb is hidden from the screen — network left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): flow\_ab is hidden from the screen — network left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): flow\_at is hidden from the screen — network left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): flow\_bt is hidden from the screen — network left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): cut\_two is hidden from the screen — network left the board. - [05:8.607](https://academa.ai/lectures/maxflow-mincut-theorem?t=308.60672916666664): theorem is hidden from the screen — left the board. ### Scene 2: [Augmenting Paths and the Residual Graph](https://academa.ai/lectures/maxflow-mincut-theorem?t=309.6483958333333) Span: 05:9.648–11:18.067 (309.6483958333333s–678.0674166666668s). #### Objects - aug\_def: a Panel that says "A path from $s$ to $t$ on edges that still have room. It carries the least room on it, its bottleneck." - back\_rule: a Math \[text\] that says "$c\_f(v,u) = f(u,v)$" - check\_a: a Math \[text\] that says "$a: quad 3 = 1 + 2$" - check\_b: a Math \[text\] that says "$b: quad 2 + 1 = 3$" - edge\_ab: a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True) - edge\_at: a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True) - edge\_bt: a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True) - edge\_sa: a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True) - edge\_sb: a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True) - f\_ab: a VariableNumber (format\_spec='.0f') - f\_at: a VariableNumber (format\_spec='.0f') - f\_bt: a VariableNumber (format\_spec='.0f') - f\_sa: a VariableNumber (format\_spec='.0f') - f\_sb: a VariableNumber (format\_spec='.0f') - flow\_ab: a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False) - flow\_at: a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False) - flow\_bt: a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False) - flow\_sa: a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False) - flow\_sb: a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False) - flow\_value: a VariableNumber (format\_spec='.0f') - forward\_rule: a Math \[text\] that says "$c\_f(u,v) = c(u,v) - f(u,v)$" - head\_push: a Heading that says "Pushing Flow Along a Path" - head\_res: a Heading that says "The Residual Graph" - head\_undo: a Heading that says "Undoing an Earlier Decision" - network: a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)) - node\_a: a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13) - node\_b: a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13) - node\_s: a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13) - node\_t: a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13) - path\_math: a Math \[text\] that says "$s arrow.r b arrow.r a arrow.r t$" - point: a Point \[yellow\] drawn in network (location=(3.2, 0.7)) - res\_as: a CurvedArrow \[red\] drawn in network (start=(3.2, 4.0), end=(0.7, 2.3), bend=0.4) - res\_ba: a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(3.2, 4.0), bend=0.45) - res\_bs: a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(0.7, 2.3), bend=0.4) - res\_def: a Panel that says "The residual graph records what could still change: forwards, the room left on an edge; backwards, the flow currently on it." - res\_ta: a CurvedArrow \[red\] drawn in network (start=(6.5, 2.3), end=(3.2, 4.0), bend=0.4) - res\_tb: a CurvedArrow \[red\] drawn in network (start=(6.5, 2.3), end=(3.2, 0.7), bend=0.4) - stuck\_note: a Panel that says "Four units, and no path left. Is four the answer?" - value\_num: a Point \[green\] labelled "0" drawn in network (location=(5.3, 4.45), show\_marker=False) - value\_word: a Math \[green\] that says "$upright("units")$" drawn in network #### Beats ##### [05:9.648](https://academa.ai/lectures/maxflow-mincut-theorem?t=309.6483958333333) Narration: We have a network, and we have the rules a flow has to obey. What we need now is a way to actually find the biggest flow, and the method is almost embarrassingly simple. Find a route from the source to the sink that still has room on every edge, and push as much along it as the tightest edge will allow. Board: Empty. Actions: - [05:9.648](https://academa.ai/lectures/maxflow-mincut-theorem?t=309.6483958333333): head\_push is shown on the screen, written out. - [05:9.648](https://academa.ai/lectures/maxflow-mincut-theorem?t=309.6483958333333): network is shown on the screen, written out. - [05:9.648](https://academa.ai/lectures/maxflow-mincut-theorem?t=309.6483958333333): node\_s is shown on the screen, written out. - [05:9.648](https://academa.ai/lectures/maxflow-mincut-theorem?t=309.6483958333333): node\_a is shown on the screen, written out. - [05:9.648](https://academa.ai/lectures/maxflow-mincut-theorem?t=309.6483958333333): node\_b is shown on the screen, written out. - [05:9.648](https://academa.ai/lectures/maxflow-mincut-theorem?t=309.6483958333333): node\_t is shown on the screen, written out. - [05:11.982](https://academa.ai/lectures/maxflow-mincut-theorem?t=311.9823958333333): flow\_sa is shown on the screen, written out. - [05:12.082](https://academa.ai/lectures/maxflow-mincut-theorem?t=312.08239583333335): flow\_sb is shown on the screen, written out. - [05:12.182](https://academa.ai/lectures/maxflow-mincut-theorem?t=312.1823958333333): flow\_ab is shown on the screen, written out. - [05:12.282](https://academa.ai/lectures/maxflow-mincut-theorem?t=312.28239583333334): flow\_at is shown on the screen, written out. - [05:12.382](https://academa.ai/lectures/maxflow-mincut-theorem?t=312.3823958333333): flow\_bt is shown on the screen, written out. - [05:12.655](https://academa.ai/lectures/maxflow-mincut-theorem?t=312.65539583333333): edge\_sa is shown on the screen, drawn. - [05:12.775](https://academa.ai/lectures/maxflow-mincut-theorem?t=312.77539583333333): edge\_sb is shown on the screen, drawn. - [05:12.895](https://academa.ai/lectures/maxflow-mincut-theorem?t=312.89539583333334): edge\_ab is shown on the screen, drawn. - [05:13.015](https://academa.ai/lectures/maxflow-mincut-theorem?t=313.01539583333334): edge\_at is shown on the screen, drawn. - [05:13.135](https://academa.ai/lectures/maxflow-mincut-theorem?t=313.13539583333335): edge\_bt is shown on the screen, drawn. ##### [05:28.522](https://academa.ai/lectures/maxflow-mincut-theorem?t=328.5218958333333) Narration: A route like that has a name. It is called an augmenting path, because sending flow along it augments what we already have. The amount it can take is decided by whichever edge has the least room left, and that edge is called the bottleneck. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_push — a Heading that says "Pushing Flow Along a Path"; node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False) Actions: - [05:31.575](https://academa.ai/lectures/maxflow-mincut-theorem?t=331.57539583333335): network moves to a new place on the board. - [05:31.575](https://academa.ai/lectures/maxflow-mincut-theorem?t=331.57539583333335): aug\_def is shown on the screen, written out. - [05:35.186](https://academa.ai/lectures/maxflow-mincut-theorem?t=335.18639583333334): value\_num is shown on the screen, written out. - [05:35.186](https://academa.ai/lectures/maxflow-mincut-theorem?t=335.18639583333334): value\_word is shown on the screen, written out. ##### [05:43.53](https://academa.ai/lectures/maxflow-mincut-theorem?t=343.53039583333333) Narration: Nothing is flowing yet, so every edge has all of its room available. Take the top edge into a, then the edge down to b, then out of b to the sink. Board: aug\_def — a Panel that says "A path from $s$ to $t$ on edges that still have room. It carries the least room on it, its bottleneck."; network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_push — a Heading that says "Pushing Flow Along a Path"; node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "0" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network Actions: - [05:48.871](https://academa.ai/lectures/maxflow-mincut-theorem?t=348.87139583333334): edge\_sa is emphasized. - [05:51.135](https://academa.ai/lectures/maxflow-mincut-theorem?t=351.1353958333333): edge\_ab is emphasized. - [05:52.528](https://academa.ai/lectures/maxflow-mincut-theorem?t=352.5283958333333): edge\_bt is emphasized. ##### [05:54.904](https://academa.ai/lectures/maxflow-mincut-theorem?t=354.9043958333333) Narration: The room on those three edges is three, then two, then three. The smallest is two, so two units is everything this path can carry. Board: Unchanged from the preceding beat in this scene. Actions: - [05:56.239](https://academa.ai/lectures/maxflow-mincut-theorem?t=356.23939583333333): edge\_sa is indicated — a transient flash. - [05:57.017](https://academa.ai/lectures/maxflow-mincut-theorem?t=357.01739583333335): edge\_bt is indicated — a transient flash. - [05:57.864](https://academa.ai/lectures/maxflow-mincut-theorem?t=357.86439583333333): edge\_ab is indicated — a transient flash. ##### [06:4.896](https://academa.ai/lectures/maxflow-mincut-theorem?t=364.8963958333333) Narration: Push it through. All three edges on the path go up by two, and the flow we are holding now has value two. Board: Unchanged from the preceding beat in this scene. Actions: - [06:5.372](https://academa.ai/lectures/maxflow-mincut-theorem?t=365.3723958333333): flow\_sa is redrawn as the numbers it depends on change. - [06:5.372](https://academa.ai/lectures/maxflow-mincut-theorem?t=365.3723958333333): flow\_ab is redrawn as the numbers it depends on change. - [06:5.372](https://academa.ai/lectures/maxflow-mincut-theorem?t=365.3723958333333): flow\_bt is redrawn as the numbers it depends on change. - [06:5.372](https://academa.ai/lectures/maxflow-mincut-theorem?t=365.3723958333333): value\_num is redrawn as the numbers it depends on change. - [06:5.372](https://academa.ai/lectures/maxflow-mincut-theorem?t=365.3723958333333): f\_sa ticks to 2.0. - [06:5.372](https://academa.ai/lectures/maxflow-mincut-theorem?t=365.3723958333333): f\_ab ticks to 2.0. - [06:5.372](https://academa.ai/lectures/maxflow-mincut-theorem?t=365.3723958333333): f\_bt ticks to 2.0. - [06:5.372](https://academa.ai/lectures/maxflow-mincut-theorem?t=365.3723958333333): flow\_value ticks to 2.0. ##### [06:12.927](https://academa.ai/lectures/maxflow-mincut-theorem?t=372.9273958333333) Narration: Now look at the middle edge. Two units on a capacity of two, which means it is completely full. Nothing more can ever go along it while this flow stands. Board: Unchanged from the preceding beat in this scene. Actions: - [06:12.927](https://academa.ai/lectures/maxflow-mincut-theorem?t=372.9273958333333): edge\_sa is no longer emphasized. - [06:12.927](https://academa.ai/lectures/maxflow-mincut-theorem?t=372.9273958333333): edge\_bt is no longer emphasized. - [06:14.018](https://academa.ai/lectures/maxflow-mincut-theorem?t=374.01839583333333): edge\_ab is no longer emphasized. - [06:18.372](https://academa.ai/lectures/maxflow-mincut-theorem?t=378.3723958333333): edge\_ab is indicated — a transient flash. ##### [06:23.419](https://academa.ai/lectures/maxflow-mincut-theorem?t=383.4188958333333) Narration: Look for another path. From the source into a there is one unit of room left, and from a straight across to the sink there are two units. The bottleneck is one, so one unit is what we send. Board: Unchanged from the preceding beat in this scene. Actions: - [06:28.213](https://academa.ai/lectures/maxflow-mincut-theorem?t=388.2133958333333): edge\_sa is emphasized. - [06:29.943](https://academa.ai/lectures/maxflow-mincut-theorem?t=389.9433958333333): edge\_at is emphasized. - [06:34.807](https://academa.ai/lectures/maxflow-mincut-theorem?t=394.8073958333333): flow\_sa is redrawn as the numbers it depends on change. - [06:34.807](https://academa.ai/lectures/maxflow-mincut-theorem?t=394.8073958333333): flow\_at is redrawn as the numbers it depends on change. - [06:34.807](https://academa.ai/lectures/maxflow-mincut-theorem?t=394.8073958333333): value\_num is redrawn as the numbers it depends on change. - [06:34.807](https://academa.ai/lectures/maxflow-mincut-theorem?t=394.8073958333333): f\_sa ticks to 3.0. - [06:34.807](https://academa.ai/lectures/maxflow-mincut-theorem?t=394.8073958333333): f\_at ticks to 1.0. - [06:34.807](https://academa.ai/lectures/maxflow-mincut-theorem?t=394.8073958333333): flow\_value ticks to 3.0. ##### [06:36.185](https://academa.ai/lectures/maxflow-mincut-theorem?t=396.1853958333333) Narration: Three units are leaving the source now. And the edge out of the source into a is full as well, three out of three, with nothing to spare. Board: Unchanged from the preceding beat in this scene. Actions: - [06:36.185](https://academa.ai/lectures/maxflow-mincut-theorem?t=396.1853958333333): edge\_sa is no longer emphasized. - [06:36.185](https://academa.ai/lectures/maxflow-mincut-theorem?t=396.1853958333333): edge\_at is no longer emphasized. - [06:41.166](https://academa.ai/lectures/maxflow-mincut-theorem?t=401.1663958333333): edge\_sa is indicated — a transient flash. ##### [06:45.469](https://academa.ai/lectures/maxflow-mincut-theorem?t=405.46939583333335) Narration: One more path. From the source into b there is plenty of room, three units of it. But the edge from b to the sink has only one unit left, so one unit is all we can send along this one. Board: Unchanged from the preceding beat in this scene. Actions: - [06:48.755](https://academa.ai/lectures/maxflow-mincut-theorem?t=408.7553958333333): edge\_sb is emphasized. - [06:52.737](https://academa.ai/lectures/maxflow-mincut-theorem?t=412.7373958333333): edge\_bt is emphasized. - [06:55.547](https://academa.ai/lectures/maxflow-mincut-theorem?t=415.5473958333333): flow\_sb is redrawn as the numbers it depends on change. - [06:55.547](https://academa.ai/lectures/maxflow-mincut-theorem?t=415.5473958333333): flow\_bt is redrawn as the numbers it depends on change. - [06:55.547](https://academa.ai/lectures/maxflow-mincut-theorem?t=415.5473958333333): value\_num is redrawn as the numbers it depends on change. - [06:55.547](https://academa.ai/lectures/maxflow-mincut-theorem?t=415.5473958333333): f\_sb ticks to 1.0. - [06:55.547](https://academa.ai/lectures/maxflow-mincut-theorem?t=415.5473958333333): f\_bt ticks to 3.0. - [06:55.547](https://academa.ai/lectures/maxflow-mincut-theorem?t=415.5473958333333): flow\_value ticks to 4.0. ##### [06:57.552](https://academa.ai/lectures/maxflow-mincut-theorem?t=417.55189583333333) Narration: Four units. And now we are stuck. Board: Unchanged from the preceding beat in this scene. Actions: - [06:57.552](https://academa.ai/lectures/maxflow-mincut-theorem?t=417.55189583333333): edge\_sb is no longer emphasized. - [06:57.552](https://academa.ai/lectures/maxflow-mincut-theorem?t=417.55189583333333): edge\_bt is no longer emphasized. - [06:57.9](https://academa.ai/lectures/maxflow-mincut-theorem?t=417.90039583333333): value\_num is indicated — a transient flash. ##### [07:1.53](https://academa.ai/lectures/maxflow-mincut-theorem?t=421.5298958333333) Narration: Look at what is left. The edge from the source to a is full, so a cannot be reached that way at all. The edge from the source to b does have room, so we can get as far as b. But b to t is full, and b has no other edge leading forward. There is nowhere to go. Board: Unchanged from the preceding beat in this scene. Actions: - [07:4.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=424.9783958333333): edge\_sa is indicated — a transient flash. - [07:9.622](https://academa.ai/lectures/maxflow-mincut-theorem?t=429.6223958333333): edge\_sb is indicated — a transient flash. - [07:10.876](https://academa.ai/lectures/maxflow-mincut-theorem?t=430.87639583333333): point is shown on the screen, grown. - [07:12.876](https://academa.ai/lectures/maxflow-mincut-theorem?t=432.87639583333333): point is hidden from the screen. - [07:13.21](https://academa.ai/lectures/maxflow-mincut-theorem?t=433.21039583333334): edge\_bt is indicated — a transient flash. ##### [07:18.5](https://academa.ai/lectures/maxflow-mincut-theorem?t=438.5003958333333) Narration: So the simple method has run out of paths at a value of four. And the uncomfortable question is whether four really is the answer, or whether we made a bad choice somewhere and the method has no way at all of noticing. Board: Unchanged from the preceding beat in this scene. Actions: - [07:22.912](https://academa.ai/lectures/maxflow-mincut-theorem?t=442.91239583333333): stuck\_note is shown on the screen, written out. - [07:31.109](https://academa.ai/lectures/maxflow-mincut-theorem?t=451.1088958333333): aug\_def is hidden from the screen — left the board. - [07:31.109](https://academa.ai/lectures/maxflow-mincut-theorem?t=451.1088958333333): head\_push is hidden from the screen — left the board. - [07:31.109](https://academa.ai/lectures/maxflow-mincut-theorem?t=451.1088958333333): stuck\_note is hidden from the screen — left the board. ##### [07:32.309](https://academa.ai/lectures/maxflow-mincut-theorem?t=452.3088958333333) Narration: We did make a bad choice, and it was the very first path. Those two units went from a down into b, and then out of b to the sink, and between them they used up nearly the whole edge into the sink. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "0" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network Actions: - [07:32.309](https://academa.ai/lectures/maxflow-mincut-theorem?t=452.3088958333333): head\_res is shown on the screen, written out. - [07:37.823](https://academa.ai/lectures/maxflow-mincut-theorem?t=457.8233958333333): edge\_ab is emphasized. - [07:41.701](https://academa.ai/lectures/maxflow-mincut-theorem?t=461.7013958333333): edge\_bt is emphasized. ##### [07:44.762](https://academa.ai/lectures/maxflow-mincut-theorem?t=464.7623958333333) Narration: But b had a supply of its own, coming straight from the source, and now there is no room left for it. The two units that came down from a squeezed it out. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "0" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; head\_res — a Heading that says "The Residual Graph" Actions: - [07:45.807](https://academa.ai/lectures/maxflow-mincut-theorem?t=465.8073958333333): edge\_sb is emphasized. ##### [07:54.592](https://academa.ai/lectures/maxflow-mincut-theorem?t=474.5923958333333) Narration: What we would like to do is take one of those two units back off the edge from a to b, push it across from a to the sink instead, and let a unit from the source into b move into the space it leaves behind. But the method as we stated it cannot walk backwards. Board: Unchanged from the preceding beat in this scene. Actions: - [07:57.471](https://academa.ai/lectures/maxflow-mincut-theorem?t=477.4713958333333): edge\_ab is no longer emphasized. - [07:57.471](https://academa.ai/lectures/maxflow-mincut-theorem?t=477.4713958333333): edge\_bt is no longer emphasized. - [07:57.471](https://academa.ai/lectures/maxflow-mincut-theorem?t=477.4713958333333): edge\_sb is no longer emphasized. - [07:59.933](https://academa.ai/lectures/maxflow-mincut-theorem?t=479.9333958333333): edge\_at is indicated — a transient flash. ##### [08:10.622](https://academa.ai/lectures/maxflow-mincut-theorem?t=490.6218958333333) Narration: So we change what the method is allowed to walk on. This is the residual graph, and it records not what is flowing, but what could still change. Board: Unchanged from the preceding beat in this scene. Actions: - [08:14.418](https://academa.ai/lectures/maxflow-mincut-theorem?t=494.4183958333333): res\_def is shown on the screen, written out. ##### [08:19.836](https://academa.ai/lectures/maxflow-mincut-theorem?t=499.8363958333333) Narration: Forwards, it is what you would expect. An edge of capacity four carrying one unit has three units of room, so three more could still be pushed along it. Every number on the picture is already telling you that. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "0" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; res\_def — a Panel that says "The residual graph records what could still change: forwards, the room left on an edge; backwards, the flow currently on it."; head\_res — a Heading that says "The Residual Graph" Actions: - [08:22.042](https://academa.ai/lectures/maxflow-mincut-theorem?t=502.04239583333333): forward\_rule is shown on the screen, written out. - [08:31.539](https://academa.ai/lectures/maxflow-mincut-theorem?t=511.5393958333333): edge\_sb is indicated — a transient flash. ##### [08:34.09](https://academa.ai/lectures/maxflow-mincut-theorem?t=514.0898958333333) Narration: Backwards is the new idea. An edge carrying one unit could have that unit taken away again, so the residual graph also holds a reverse arrow along it, pointing back the way the flow came, with capacity equal to the flow currently on the edge. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "0" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; res\_def — a Panel that says "The residual graph records what could still change: forwards, the room left on an edge; backwards, the flow currently on it."; forward\_rule — a Math \[text\] that says "$c\_f(u,v) = c(u,v) - f(u,v)$"; head\_res — a Heading that says "The Residual Graph" Actions: - [08:34.647](https://academa.ai/lectures/maxflow-mincut-theorem?t=514.6473958333333): back\_rule is shown on the screen, written out. - [08:42.716](https://academa.ai/lectures/maxflow-mincut-theorem?t=522.7163958333333): res\_as is shown on the screen, drawn. - [08:42.836](https://academa.ai/lectures/maxflow-mincut-theorem?t=522.8363958333333): res\_bs is shown on the screen, drawn. - [08:42.956](https://academa.ai/lectures/maxflow-mincut-theorem?t=522.9563958333333): res\_ba is shown on the screen, drawn. - [08:43.076](https://academa.ai/lectures/maxflow-mincut-theorem?t=523.0763958333333): res\_ta is shown on the screen, drawn. - [08:43.196](https://academa.ai/lectures/maxflow-mincut-theorem?t=523.1963958333333): res\_tb is shown on the screen, drawn. ##### [08:49.388](https://academa.ai/lectures/maxflow-mincut-theorem?t=529.3878958333333) Narration: Here they all are, one for every edge that is carrying something. Most of them are no use to us. These two come out of the sink, and these two point back at the source, and reaching them gets us nowhere new. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "0" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; res\_def — a Panel that says "The residual graph records what could still change: forwards, the room left on an edge; backwards, the flow currently on it."; forward\_rule — a Math \[text\] that says "$c\_f(u,v) = c(u,v) - f(u,v)$"; back\_rule — a Math \[text\] that says "$c\_f(v,u) = f(u,v)$"; head\_res — a Heading that says "The Residual Graph"; res\_as — a CurvedArrow \[red\] drawn in network (start=(3.2, 4.0), end=(0.7, 2.3), bend=0.4); res\_bs — a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(0.7, 2.3), bend=0.4); res\_ba — a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(3.2, 4.0), bend=0.45); res\_ta — a CurvedArrow \[red\] drawn in network (start=(6.5, 2.3), end=(3.2, 4.0), bend=0.4); res\_tb — a CurvedArrow \[red\] drawn in network (start=(6.5, 2.3), end=(3.2, 0.7), bend=0.4) Actions: - [08:57.433](https://academa.ai/lectures/maxflow-mincut-theorem?t=537.4333958333334): res\_ta is indicated — a transient flash. - [08:57.433](https://academa.ai/lectures/maxflow-mincut-theorem?t=537.4333958333334): res\_tb is indicated — a transient flash. - [08:59.337](https://academa.ai/lectures/maxflow-mincut-theorem?t=539.3373958333334): res\_as is indicated — a transient flash. - [08:59.337](https://academa.ai/lectures/maxflow-mincut-theorem?t=539.3373958333334): res\_bs is indicated — a transient flash. - [09:0.707](https://academa.ai/lectures/maxflow-mincut-theorem?t=540.7073958333333): res\_ta is hidden from the screen. - [09:0.707](https://academa.ai/lectures/maxflow-mincut-theorem?t=540.7073958333333): res\_tb is hidden from the screen. - [09:0.707](https://academa.ai/lectures/maxflow-mincut-theorem?t=540.7073958333333): res\_as is hidden from the screen. - [09:0.707](https://academa.ai/lectures/maxflow-mincut-theorem?t=540.7073958333333): res\_bs is hidden from the screen. ##### [09:2.55](https://academa.ai/lectures/maxflow-mincut-theorem?t=542.5503958333334) Narration: This one is the one that matters. Two units are currently running from a down to b, so the residual graph offers two units of capacity going the other way, from b back up to a. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "0" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; res\_def — a Panel that says "The residual graph records what could still change: forwards, the room left on an edge; backwards, the flow currently on it."; forward\_rule — a Math \[text\] that says "$c\_f(u,v) = c(u,v) - f(u,v)$"; back\_rule — a Math \[text\] that says "$c\_f(v,u) = f(u,v)$"; head\_res — a Heading that says "The Residual Graph"; res\_ba — a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(3.2, 4.0), bend=0.45) Actions: - [09:4.175](https://academa.ai/lectures/maxflow-mincut-theorem?t=544.1753958333334): res\_ba is emphasized. ##### [09:14.888](https://academa.ai/lectures/maxflow-mincut-theorem?t=554.8878958333333) Narration: Now search again, and this time walk on residual edges. From the source into b there is room. From b, take the backward arrow up to a. And from a there is one unit of room left into the sink. Board: Unchanged from the preceding beat in this scene. Actions: - [09:20.936](https://academa.ai/lectures/maxflow-mincut-theorem?t=560.9363958333333): edge\_sb is emphasized. - [09:22.829](https://academa.ai/lectures/maxflow-mincut-theorem?t=562.8293958333334): res\_ba is indicated — a transient flash. - [09:27.124](https://academa.ai/lectures/maxflow-mincut-theorem?t=567.1243958333333): edge\_at is emphasized. ##### [09:29.222](https://academa.ai/lectures/maxflow-mincut-theorem?t=569.2223958333334) Narration: That is a path from the source to the sink: s, then b, then a, then t. Its bottleneck is one unit, so one unit is what we push along it. Board: Unchanged from the preceding beat in this scene. Actions: - [09:30.012](https://academa.ai/lectures/maxflow-mincut-theorem?t=570.0123958333334): path\_math is shown on the screen, written out. ##### [09:39.702](https://academa.ai/lectures/maxflow-mincut-theorem?t=579.7023958333334) Narration: The edge from the source into b goes up to two. The edge from a to b is walked backwards, so it goes down by one, from two to one. And the edge from a to the sink goes up to two. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "0" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; res\_def — a Panel that says "The residual graph records what could still change: forwards, the room left on an edge; backwards, the flow currently on it."; forward\_rule — a Math \[text\] that says "$c\_f(u,v) = c(u,v) - f(u,v)$"; back\_rule — a Math \[text\] that says "$c\_f(v,u) = f(u,v)$"; path\_math — a Math \[text\] that says "$s arrow.r b arrow.r a arrow.r t$"; head\_res — a Heading that says "The Residual Graph"; res\_ba — a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(3.2, 4.0), bend=0.45) Actions: - [09:42.256](https://academa.ai/lectures/maxflow-mincut-theorem?t=582.2563958333334): flow\_sb is redrawn as the numbers it depends on change. - [09:42.256](https://academa.ai/lectures/maxflow-mincut-theorem?t=582.2563958333334): f\_sb ticks to 2.0. - [09:46.54](https://academa.ai/lectures/maxflow-mincut-theorem?t=586.5403958333334): flow\_ab is redrawn as the numbers it depends on change. - [09:46.54](https://academa.ai/lectures/maxflow-mincut-theorem?t=586.5403958333334): f\_ab ticks to 1.0. - [09:50.499](https://academa.ai/lectures/maxflow-mincut-theorem?t=590.4993958333334): flow\_at is redrawn as the numbers it depends on change. - [09:50.499](https://academa.ai/lectures/maxflow-mincut-theorem?t=590.4993958333334): value\_num is redrawn as the numbers it depends on change. - [09:50.499](https://academa.ai/lectures/maxflow-mincut-theorem?t=590.4993958333334): f\_at ticks to 2.0. - [09:50.499](https://academa.ai/lectures/maxflow-mincut-theorem?t=590.4993958333334): flow\_value ticks to 5.0. - [09:51.196](https://academa.ai/lectures/maxflow-mincut-theorem?t=591.1958958333333): path\_math moves to a new place on the board. - [09:51.196](https://academa.ai/lectures/maxflow-mincut-theorem?t=591.1958958333333): back\_rule is hidden from the screen — left the board. - [09:51.196](https://academa.ai/lectures/maxflow-mincut-theorem?t=591.1958958333333): forward\_rule is hidden from the screen — left the board. - [09:51.196](https://academa.ai/lectures/maxflow-mincut-theorem?t=591.1958958333333): head\_res is hidden from the screen — left the board. - [09:51.196](https://academa.ai/lectures/maxflow-mincut-theorem?t=591.1958958333333): res\_def is hidden from the screen — left the board. ##### [09:51.796](https://academa.ai/lectures/maxflow-mincut-theorem?t=591.7958958333334) Narration: The value is five. So check that nothing has broken. At a, three units arrive from the source, one leaves downward into b, and two leave across to the sink. Three in and three out. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "0" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; path\_math — a Math \[text\] that says "$s arrow.r b arrow.r a arrow.r t$"; res\_ba — a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(3.2, 4.0), bend=0.45) Actions: - [09:51.796](https://academa.ai/lectures/maxflow-mincut-theorem?t=591.7958958333334): head\_undo is shown on the screen, written out. - [09:51.796](https://academa.ai/lectures/maxflow-mincut-theorem?t=591.7958958333334): edge\_sb is no longer emphasized. - [09:51.796](https://academa.ai/lectures/maxflow-mincut-theorem?t=591.7958958333334): edge\_at is no longer emphasized. - [09:51.796](https://academa.ai/lectures/maxflow-mincut-theorem?t=591.7958958333334): res\_ba is no longer emphasized. - [09:52.748](https://academa.ai/lectures/maxflow-mincut-theorem?t=592.7483958333335): value\_num is indicated — a transient flash. - [10:2.977](https://academa.ai/lectures/maxflow-mincut-theorem?t=602.9773958333334): check\_a is shown on the screen, written out. ##### [10:5.353](https://academa.ai/lectures/maxflow-mincut-theorem?t=605.3533958333334) Narration: At b, two units arrive from the source and one arrives from a, and three leave for the sink. Three in and three out again. Every capacity is respected, and this is a perfectly legal flow of value five. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "0" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; path\_math — a Math \[text\] that says "$s arrow.r b arrow.r a arrow.r t$"; res\_ba — a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(3.2, 4.0), bend=0.45); check\_a — a Math \[text\] that says "$a: quad 3 = 1 + 2$"; head\_undo — a Heading that says "Undoing an Earlier Decision" Actions: - [10:12.563](https://academa.ai/lectures/maxflow-mincut-theorem?t=612.5633958333334): check\_b is shown on the screen, written out. - [10:16.58](https://academa.ai/lectures/maxflow-mincut-theorem?t=616.5803958333333): value\_num is indicated — a transient flash. ##### [10:18.841](https://academa.ai/lectures/maxflow-mincut-theorem?t=618.8408958333334) Narration: And look at what the backward step actually did to the picture. It did not cancel the first path, and it did not throw anything away. One unit that used to go source, a, b, sink now travels source, a, sink. And one unit that previously had nowhere to go now travels source, b, sink. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "0" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "0" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "0" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "0" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "0" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "0" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; path\_math — a Math \[text\] that says "$s arrow.r b arrow.r a arrow.r t$"; res\_ba — a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(3.2, 4.0), bend=0.45); check\_a — a Math \[text\] that says "$a: quad 3 = 1 + 2$"; check\_b — a Math \[text\] that says "$b: quad 2 + 1 = 3$"; head\_undo — a Heading that says "Undoing an Earlier Decision" Actions: - [10:29.963](https://academa.ai/lectures/maxflow-mincut-theorem?t=629.9633958333334): edge\_sa is emphasized. - [10:29.963](https://academa.ai/lectures/maxflow-mincut-theorem?t=629.9633958333334): edge\_at is emphasized. - [10:33.527](https://academa.ai/lectures/maxflow-mincut-theorem?t=633.5273958333335): edge\_sa is no longer emphasized. - [10:33.527](https://academa.ai/lectures/maxflow-mincut-theorem?t=633.5273958333335): edge\_at is no longer emphasized. - [10:33.527](https://academa.ai/lectures/maxflow-mincut-theorem?t=633.5273958333335): edge\_sb is emphasized. - [10:33.527](https://academa.ai/lectures/maxflow-mincut-theorem?t=633.5273958333335): edge\_bt is emphasized. ##### [10:37.448](https://academa.ai/lectures/maxflow-mincut-theorem?t=637.4478958333334) Narration: The bookkeeping did the rerouting for us. Nobody had to spot that swap in advance, and nobody had to go back and edit an earlier decision. The backward arrow made an old choice reversible, and the search took the reversal without knowing it was being clever. Board: Unchanged from the preceding beat in this scene. Actions: - [10:37.448](https://academa.ai/lectures/maxflow-mincut-theorem?t=637.4478958333334): edge\_sb is no longer emphasized. - [10:37.448](https://academa.ai/lectures/maxflow-mincut-theorem?t=637.4478958333334): edge\_bt is no longer emphasized. - [10:46.341](https://academa.ai/lectures/maxflow-mincut-theorem?t=646.3413958333335): res\_ba is indicated — a transient flash. ##### [10:53.257](https://academa.ai/lectures/maxflow-mincut-theorem?t=653.2568958333334) Narration: That is the whole algorithm. Find a path in the residual graph, push the bottleneck along it, rebuild the residual graph, and repeat until there is no path left. It is called Ford Fulkerson. Board: Unchanged from the preceding beat in this scene. Actions: - [10:56.554](https://academa.ai/lectures/maxflow-mincut-theorem?t=656.5543958333335): path\_math is indicated — a transient flash. ##### [11:7.139](https://academa.ai/lectures/maxflow-mincut-theorem?t=667.1388958333334) Narration: Which leaves exactly one question. When it stops, has it actually won? Or is there some cleverer route that this procedure simply cannot see? Board: Unchanged from the preceding beat in this scene. Actions: - [11:9.936](https://academa.ai/lectures/maxflow-mincut-theorem?t=669.9363958333334): value\_num is indicated — a transient flash. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): check\_a is hidden from the screen — left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): check\_b is hidden from the screen — left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): head\_undo is hidden from the screen — left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): network is hidden from the screen — left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): node\_s is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): node\_a is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): node\_b is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): node\_t is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): edge\_sa is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): edge\_sb is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): edge\_ab is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): edge\_at is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): edge\_bt is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): flow\_sa is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): flow\_sb is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): flow\_ab is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): flow\_at is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): flow\_bt is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): value\_num is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): value\_word is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): res\_ba is hidden from the screen — network left the board. - [11:17.026](https://academa.ai/lectures/maxflow-mincut-theorem?t=677.0257500000001): path\_math is hidden from the screen — left the board. ### Scene 3: [The Cut That Certifies It](https://academa.ai/lectures/maxflow-mincut-theorem?t=678.0674166666668) Span: 11:18.067–15:41.611 (678.0674166666668s–941.6113333333335s). #### Objects - certificate: a Panel that says "When the search stops it hands you a proof: a set of edges, totalling the value of your flow, that every unit has to cross." - cut\_cap: a Math \[text\] that says "$c(S) = 2 + 3 = 5$" - cut\_line: a Line \[magenta\] drawn in network (start=(5.1, 0.15), end=(5.1, 4.55), dashed=True) - derivation: a Derivation \[text\] that says "$\|f\| &= f(S arrow.r T) - f(T arrow.r S) \\ &= c(S) - 0 \\ &= c(S)$" - edge\_ab: a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True) - edge\_at: a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True) - edge\_bt: a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True) - edge\_sa: a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True) - edge\_sb: a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True) - equality: a Math \[text\] that says "$\|f\| = c(S) = 5$" - flow\_ab: a Point \[green\] labelled "1" drawn in network (location=(2.8, 2.35), show\_marker=False) - flow\_at: a Point \[green\] labelled "2" drawn in network (location=(5.08, 3.55), show\_marker=False) - flow\_bt: a Point \[green\] labelled "3" drawn in network (location=(5.05, 1.1), show\_marker=False) - flow\_sa: a Point \[green\] labelled "3" drawn in network (location=(1.7, 3.52), show\_marker=False) - flow\_sb: a Point \[green\] labelled "2" drawn in network (location=(1.71, 1.12), show\_marker=False) - head\_stop: a Heading that says "Where the Search Can Still Reach" - head\_theorem: a Heading that says "Maximum Flow Equals Minimum Cut" - head\_why: a Heading that says "Why the Two Numbers Agree" - network: a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)) - node\_a: a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13) - node\_b: a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13) - node\_s: a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13) - node\_t: a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13) - point: a Point \[yellow\] drawn in network (location=(0.7, 2.3)) - point\_2: a Point \[yellow\] drawn in network (location=(3.2, 0.7)) - point\_3: a Point \[yellow\] drawn in network (location=(3.2, 4.0)) - point\_4: a Point \[yellow\] drawn in network (location=(6.5, 2.3)) - point\_5: a Point \[yellow\] drawn in network (location=(6.5, 2.3)) - point\_6: a Point \[yellow\] drawn in network (location=(6.5, 2.3)) - reach\_note: a Panel that says "Mark every node the residual graph can still reach from $s$." - region\_s: a Polygon \[blue\] drawn in network (vertices=((0.15, 2.35), (0.95, 4.45), (4.35, 4.6), (4.55, 0.2), (0.9, 0.…, fill\_opacity=0.16) - res\_ba: a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(3.2, 4.0), bend=0.45) - s\_set: a Math \[text\] that says "$S: quad s, a, b$" - theorem: a Math \[text\] that says "$max\_f \|f\| = min\_S c(S)$" - value\_num: a Point \[green\] labelled "5" drawn in network (location=(5.3, 4.45), show\_marker=False) - value\_word: a Math \[green\] that says "$upright("units")$" drawn in network #### Beats ##### [11:18.067](https://academa.ai/lectures/maxflow-mincut-theorem?t=678.0674166666668) Narration: Here is the flow we finished with. Five units, and every number on it is the number we left it at. The question now is not how to improve it. The question is how to be certain that nobody can. Board: Empty. Actions: - [11:18.067](https://academa.ai/lectures/maxflow-mincut-theorem?t=678.0674166666668): head\_stop is shown on the screen, written out. - [11:18.067](https://academa.ai/lectures/maxflow-mincut-theorem?t=678.0674166666668): network is shown on the screen, written out. - [11:18.067](https://academa.ai/lectures/maxflow-mincut-theorem?t=678.0674166666668): node\_s is shown on the screen, written out. - [11:18.067](https://academa.ai/lectures/maxflow-mincut-theorem?t=678.0674166666668): node\_a is shown on the screen, written out. - [11:18.067](https://academa.ai/lectures/maxflow-mincut-theorem?t=678.0674166666668): node\_b is shown on the screen, written out. - [11:18.067](https://academa.ai/lectures/maxflow-mincut-theorem?t=678.0674166666668): node\_t is shown on the screen, written out. - [11:20.366](https://academa.ai/lectures/maxflow-mincut-theorem?t=680.3664166666667): edge\_sa is shown on the screen, drawn. - [11:20.476](https://academa.ai/lectures/maxflow-mincut-theorem?t=680.4764166666668): edge\_sb is shown on the screen, drawn. - [11:20.586](https://academa.ai/lectures/maxflow-mincut-theorem?t=680.5864166666668): edge\_ab is shown on the screen, drawn. - [11:20.696](https://academa.ai/lectures/maxflow-mincut-theorem?t=680.6964166666668): edge\_at is shown on the screen, drawn. - [11:20.806](https://academa.ai/lectures/maxflow-mincut-theorem?t=680.8064166666668): edge\_bt is shown on the screen, drawn. - [11:21.98](https://academa.ai/lectures/maxflow-mincut-theorem?t=681.9804166666668): flow\_sa is shown on the screen, written out. - [11:22.08](https://academa.ai/lectures/maxflow-mincut-theorem?t=682.0804166666668): flow\_sb is shown on the screen, written out. - [11:22.18](https://academa.ai/lectures/maxflow-mincut-theorem?t=682.1804166666668): flow\_ab is shown on the screen, written out. - [11:22.28](https://academa.ai/lectures/maxflow-mincut-theorem?t=682.2804166666667): flow\_at is shown on the screen, written out. - [11:22.38](https://academa.ai/lectures/maxflow-mincut-theorem?t=682.3804166666667): flow\_bt is shown on the screen, written out. - [11:23.222](https://academa.ai/lectures/maxflow-mincut-theorem?t=683.2224166666667): value\_num is shown on the screen, written out. - [11:23.222](https://academa.ai/lectures/maxflow-mincut-theorem?t=683.2224166666667): value\_word is shown on the screen, written out. ##### [11:30.904](https://academa.ai/lectures/maxflow-mincut-theorem?t=690.9044166666667) Narration: So run the search one more time, and this time watch where it can get to, rather than whether it finishes. Start at the source, and mark every node the residual graph can still reach. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_stop — a Heading that says "Where the Search Can Still Reach"; node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "3" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "2" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "1" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "2" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "3" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "5" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network Actions: - [11:38.253](https://academa.ai/lectures/maxflow-mincut-theorem?t=698.2534166666668): point is shown on the screen, grown. - [11:39.669](https://academa.ai/lectures/maxflow-mincut-theorem?t=699.6694166666667): reach\_note is shown on the screen, written out. - [11:40.253](https://academa.ai/lectures/maxflow-mincut-theorem?t=700.2534166666668): point is hidden from the screen. ##### [11:43.427](https://academa.ai/lectures/maxflow-mincut-theorem?t=703.4274166666668) Narration: From the source, the edge to a is full, three units on a capacity of three, so there is no room that way. The edge to b carries two units on a capacity of four, so it has two units of room, and b is reachable. Board: reach\_note — a Panel that says "Mark every node the residual graph can still reach from $s$."; network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_stop — a Heading that says "Where the Search Can Still Reach"; node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "3" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "2" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "1" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "2" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "3" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "5" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network Actions: - [11:45.714](https://academa.ai/lectures/maxflow-mincut-theorem?t=705.7144166666668): edge\_sa is indicated — a transient flash. - [11:57.359](https://academa.ai/lectures/maxflow-mincut-theorem?t=717.3594166666668): point\_2 is shown on the screen, grown. - [11:57.359](https://academa.ai/lectures/maxflow-mincut-theorem?t=717.3594166666668): edge\_sb is emphasized. ##### [11:58.981](https://academa.ai/lectures/maxflow-mincut-theorem?t=718.9814166666667) Narration: From b, the edge to the sink is full as well, three on three. But one unit is currently flowing from a down into b, so the residual graph has a backward arrow there. Walk it, and a is reachable too. Board: reach\_note — a Panel that says "Mark every node the residual graph can still reach from $s$."; network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_stop — a Heading that says "Where the Search Can Still Reach"; node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "3" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "2" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "1" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "2" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "3" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "5" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; point\_2 — a Point \[yellow\] drawn in network (location=(3.2, 0.7)) Actions: - [11:59.359](https://academa.ai/lectures/maxflow-mincut-theorem?t=719.3594166666668): point\_2 is hidden from the screen. - [12:1.233](https://academa.ai/lectures/maxflow-mincut-theorem?t=721.2334166666668): edge\_bt is indicated — a transient flash. - [12:7.955](https://academa.ai/lectures/maxflow-mincut-theorem?t=727.9554166666668): res\_ba is shown on the screen, written out. - [12:11.694](https://academa.ai/lectures/maxflow-mincut-theorem?t=731.6944166666667): point\_3 is shown on the screen, grown. ##### [12:12.968](https://academa.ai/lectures/maxflow-mincut-theorem?t=732.9679166666667) Narration: And from a, the edge to the sink carries two units on a capacity of two. Full. So the search stops there, with the source, a and b all marked, and the sink not marked at all. Board: reach\_note — a Panel that says "Mark every node the residual graph can still reach from $s$."; network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_stop — a Heading that says "Where the Search Can Still Reach"; node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "3" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "2" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "1" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "2" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "3" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "5" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; res\_ba — a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(3.2, 4.0), bend=0.45); point\_3 — a Point \[yellow\] drawn in network (location=(3.2, 4.0)) Actions: - [12:13.694](https://academa.ai/lectures/maxflow-mincut-theorem?t=733.6944166666667): point\_3 is hidden from the screen. - [12:18.308](https://academa.ai/lectures/maxflow-mincut-theorem?t=738.3084166666667): edge\_at is indicated — a transient flash. - [12:20.131](https://academa.ai/lectures/maxflow-mincut-theorem?t=740.1314166666667): edge\_sb is no longer emphasized. - [12:22.859](https://academa.ai/lectures/maxflow-mincut-theorem?t=742.8594166666668): region\_s is shown on the screen, faded in. - [12:22.859](https://academa.ai/lectures/maxflow-mincut-theorem?t=742.8594166666668): s\_set is shown on the screen, written out. ##### [12:26.211](https://academa.ai/lectures/maxflow-mincut-theorem?t=746.2109166666668) Narration: Call that set of marked nodes S. It contains the source by construction. And it does not contain the sink, because if it did we would have found an augmenting path, and we would not have stopped. Board: reach\_note — a Panel that says "Mark every node the residual graph can still reach from $s$."; s\_set — a Math \[text\] that says "$S: quad s, a, b$"; network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_stop — a Heading that says "Where the Search Can Still Reach"; node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "3" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "2" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "1" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "2" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "3" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "5" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; res\_ba — a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(3.2, 4.0), bend=0.45); region\_s — a Polygon \[blue\] drawn in network (vertices=((0.15, 2.35), (0.95, 4.45), (4.35, 4.6), (4.55, 0.2), (0.9, 0.…, fill\_opacity=0.16) Actions: - [12:26.559](https://academa.ai/lectures/maxflow-mincut-theorem?t=746.5594166666667): region\_s is indicated — a transient flash. - [12:32.875](https://academa.ai/lectures/maxflow-mincut-theorem?t=752.8754166666668): point\_4 is shown on the screen, grown. - [12:34.875](https://academa.ai/lectures/maxflow-mincut-theorem?t=754.8754166666668): point\_4 is hidden from the screen. ##### [12:39.269](https://academa.ai/lectures/maxflow-mincut-theorem?t=759.2689166666668) Narration: So S and everything outside it form a cut, and we already know how to price a cut. The edges crossing forwards out of S are a to t, with capacity two, and b to t, with capacity three. Board: Unchanged from the preceding beat in this scene. Actions: - [12:41.95](https://academa.ai/lectures/maxflow-mincut-theorem?t=761.9504166666668): cut\_line is shown on the screen, written out. - [12:45.909](https://academa.ai/lectures/maxflow-mincut-theorem?t=765.9094166666667): edge\_at is emphasized. - [12:45.909](https://academa.ai/lectures/maxflow-mincut-theorem?t=765.9094166666667): edge\_bt is emphasized. ##### [12:53.661](https://academa.ai/lectures/maxflow-mincut-theorem?t=773.6614166666668) Narration: Two plus three is five. The cut has capacity five. And the flow has value five. The ceiling we could never beat, and the flow we actually built, are the same number. Board: reach\_note — a Panel that says "Mark every node the residual graph can still reach from $s$."; s\_set — a Math \[text\] that says "$S: quad s, a, b$"; network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_stop — a Heading that says "Where the Search Can Still Reach"; node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "3" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "2" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "1" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "2" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "3" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "5" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; res\_ba — a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(3.2, 4.0), bend=0.45); region\_s — a Polygon \[blue\] drawn in network (vertices=((0.15, 2.35), (0.95, 4.45), (4.35, 4.6), (4.55, 0.2), (0.9, 0.…, fill\_opacity=0.16); cut\_line — a Line \[magenta\] drawn in network (start=(5.1, 0.15), end=(5.1, 4.55), dashed=True) Actions: - [12:54.067](https://academa.ai/lectures/maxflow-mincut-theorem?t=774.0674166666668): cut\_cap is shown on the screen, written out. - [12:58.885](https://academa.ai/lectures/maxflow-mincut-theorem?t=778.8854166666667): value\_num is indicated — a transient flash. - [13:4.423](https://academa.ai/lectures/maxflow-mincut-theorem?t=784.4234166666668): equality is shown on the screen, written out. ##### [13:6.173](https://academa.ai/lectures/maxflow-mincut-theorem?t=786.1729166666668) Narration: That is not a coincidence, and the reason is worth seeing properly, because the reason is the whole proof. Board: reach\_note — a Panel that says "Mark every node the residual graph can still reach from $s$."; s\_set — a Math \[text\] that says "$S: quad s, a, b$"; cut\_cap — a Math \[text\] that says "$c(S) = 2 + 3 = 5$"; equality — a Math \[text\] that says "$\|f\| = c(S) = 5$"; network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_stop — a Heading that says "Where the Search Can Still Reach"; node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "3" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "2" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "1" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "2" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "3" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "5" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; res\_ba — a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(3.2, 4.0), bend=0.45); region\_s — a Polygon \[blue\] drawn in network (vertices=((0.15, 2.35), (0.95, 4.45), (4.35, 4.6), (4.55, 0.2), (0.9, 0.…, fill\_opacity=0.16); cut\_line — a Line \[magenta\] drawn in network (start=(5.1, 0.15), end=(5.1, 4.55), dashed=True) Actions: - [13:7.194](https://academa.ai/lectures/maxflow-mincut-theorem?t=787.1944166666667): A box is drawn around equality. - [13:12.767](https://academa.ai/lectures/maxflow-mincut-theorem?t=792.7674166666668): network moves to a new place on the board. - [13:12.767](https://academa.ai/lectures/maxflow-mincut-theorem?t=792.7674166666668): cut\_cap is hidden from the screen — left the board. - [13:12.767](https://academa.ai/lectures/maxflow-mincut-theorem?t=792.7674166666668): equality is hidden from the screen — left the board. - [13:12.767](https://academa.ai/lectures/maxflow-mincut-theorem?t=792.7674166666668): head\_stop is hidden from the screen — left the board. - [13:12.767](https://academa.ai/lectures/maxflow-mincut-theorem?t=792.7674166666668): reach\_note is hidden from the screen — left the board. - [13:12.767](https://academa.ai/lectures/maxflow-mincut-theorem?t=792.7674166666668): s\_set is hidden from the screen — left the board. ##### [13:13.967](https://academa.ai/lectures/maxflow-mincut-theorem?t=793.9674166666667) Narration: Take any edge that crosses forwards out of S, from a marked node to an unmarked one. It has to be completely full. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "3" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "2" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "1" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "2" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "3" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "5" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; res\_ba — a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(3.2, 4.0), bend=0.45); region\_s — a Polygon \[blue\] drawn in network (vertices=((0.15, 2.35), (0.95, 4.45), (4.35, 4.6), (4.55, 0.2), (0.9, 0.…, fill\_opacity=0.16); cut\_line — a Line \[magenta\] drawn in network (start=(5.1, 0.15), end=(5.1, 4.55), dashed=True) Actions: - [13:13.967](https://academa.ai/lectures/maxflow-mincut-theorem?t=793.9674166666667): head\_why is shown on the screen, written out. - [13:15.72](https://academa.ai/lectures/maxflow-mincut-theorem?t=795.7204166666668): edge\_at is indicated — a transient flash. - [13:16.02](https://academa.ai/lectures/maxflow-mincut-theorem?t=796.0204166666667): edge\_bt is indicated — a transient flash. ##### [13:22.375](https://academa.ai/lectures/maxflow-mincut-theorem?t=802.3749166666668) Narration: Because if it had any room left on it at all, the search would have walked along it, and the node at the far end would have been marked as well. It is not marked. So the edge is full. Board: network — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); node\_s — a Point \[blue\] labelled "s" drawn in network (location=(0.7, 2.3), marker\_radius=0.13); node\_a — a Point \[blue\] labelled "a" drawn in network (location=(3.2, 4.0), marker\_radius=0.13); node\_b — a Point \[blue\] labelled "b" drawn in network (location=(3.2, 0.7), marker\_radius=0.13); node\_t — a Point \[blue\] labelled "t" drawn in network (location=(6.5, 2.3), marker\_radius=0.13); edge\_sa — a Vector \[gray\] labelled "3" drawn in network (start=(0.7, 2.3), end=(3.2, 4.0), trim\_tip=True); edge\_sb — a Vector \[gray\] labelled "4" drawn in network (start=(0.7, 2.3), end=(3.2, 0.7), trim\_tip=True); edge\_ab — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(3.2, 0.7), trim\_tip=True); edge\_at — a Vector \[gray\] labelled "2" drawn in network (start=(3.2, 4.0), end=(6.5, 2.3), trim\_tip=True); edge\_bt — a Vector \[gray\] labelled "3" drawn in network (start=(3.2, 0.7), end=(6.5, 2.3), trim\_tip=True); flow\_sa — a Point \[green\] labelled "3" drawn in network (location=(1.7, 3.52), show\_marker=False); flow\_sb — a Point \[green\] labelled "2" drawn in network (location=(1.71, 1.12), show\_marker=False); flow\_ab — a Point \[green\] labelled "1" drawn in network (location=(2.8, 2.35), show\_marker=False); flow\_at — a Point \[green\] labelled "2" drawn in network (location=(5.08, 3.55), show\_marker=False); flow\_bt — a Point \[green\] labelled "3" drawn in network (location=(5.05, 1.1), show\_marker=False); value\_num — a Point \[green\] labelled "5" drawn in network (location=(5.3, 4.45), show\_marker=False); value\_word — a Math \[green\] that says "$upright("units")$" drawn in network; res\_ba — a CurvedArrow \[red\] drawn in network (start=(3.2, 0.7), end=(3.2, 4.0), bend=0.45); region\_s — a Polygon \[blue\] drawn in network (vertices=((0.15, 2.35), (0.95, 4.45), (4.35, 4.6), (4.55, 0.2), (0.9, 0.…, fill\_opacity=0.16); cut\_line — a Line \[magenta\] drawn in network (start=(5.1, 0.15), end=(5.1, 4.55), dashed=True); head\_why — a Heading that says "Why the Two Numbers Agree" Actions: - [13:28.534](https://academa.ai/lectures/maxflow-mincut-theorem?t=808.5344166666667): point\_5 is shown on the screen, grown. - [13:30.534](https://academa.ai/lectures/maxflow-mincut-theorem?t=810.5344166666667): point\_5 is hidden from the screen. ##### [13:33.697](https://academa.ai/lectures/maxflow-mincut-theorem?t=813.6969166666668) Narration: Now take an edge crossing the other way, from an unmarked node back into S. That one has to be completely empty. Board: Unchanged from the preceding beat in this scene. Actions: - [13:41.115](https://academa.ai/lectures/maxflow-mincut-theorem?t=821.1154166666668): region\_s is indicated — a transient flash. ##### [13:42.401](https://academa.ai/lectures/maxflow-mincut-theorem?t=822.4009166666667) Narration: Because if it were carrying anything, the residual graph would hold a backward arrow along it, running from the marked end to the unmarked end, and the search would have crossed that arrow instead. Again, it did not. Board: Unchanged from the preceding beat in this scene. Actions: - [13:46.011](https://academa.ai/lectures/maxflow-mincut-theorem?t=826.0114166666667): res\_ba is indicated — a transient flash. ##### [13:55.678](https://academa.ai/lectures/maxflow-mincut-theorem?t=835.6784166666667) Narration: In this particular network there is nothing to check on that side, because nothing at all leaves the sink. But that half of the argument is exactly what makes the general theorem work. Board: Unchanged from the preceding beat in this scene. Actions: - [14:0.589](https://academa.ai/lectures/maxflow-mincut-theorem?t=840.5894166666667): point\_6 is shown on the screen, grown. - [14:2.589](https://academa.ai/lectures/maxflow-mincut-theorem?t=842.5894166666667): point\_6 is hidden from the screen. ##### [14:7.029](https://academa.ai/lectures/maxflow-mincut-theorem?t=847.0289166666668) Narration: So put the two halves together. The value of a flow is what crosses the cut forwards, minus whatever crosses back. Board: Unchanged from the preceding beat in this scene. Actions: - [14:9.85](https://academa.ai/lectures/maxflow-mincut-theorem?t=849.8504166666668): derivation is shown on the screen, written out. ##### [14:15.686](https://academa.ai/lectures/maxflow-mincut-theorem?t=855.6864166666668) Narration: Forwards, every crossing edge is full, so that first sum is the entire capacity of the cut. Backwards, every crossing edge is empty, so nothing whatsoever is subtracted. Board: Unchanged from the preceding beat in this scene. Actions: - [14:19.866](https://academa.ai/lectures/maxflow-mincut-theorem?t=859.8664166666667): derivation is shown on the screen, written out. - [14:20.272](https://academa.ai/lectures/maxflow-mincut-theorem?t=860.2724166666668): derivation (the "c(S)" part) is emphasized. - [14:25.172](https://academa.ai/lectures/maxflow-mincut-theorem?t=865.1724166666668): derivation (the "0" part) is emphasized. - [14:25.172](https://academa.ai/lectures/maxflow-mincut-theorem?t=865.1724166666668): derivation (the "c(S)" part) is no longer emphasized. ##### [14:28.082](https://academa.ai/lectures/maxflow-mincut-theorem?t=868.0824166666667) Narration: So the value of the flow is exactly the capacity of this cut. And we already knew that no flow anywhere can exceed the capacity of any cut. Two facts, and between them they nail the answer down completely. Board: Unchanged from the preceding beat in this scene. Actions: - [14:28.082](https://academa.ai/lectures/maxflow-mincut-theorem?t=868.0824166666667): derivation (the "0" part) is no longer emphasized. - [14:29.707](https://academa.ai/lectures/maxflow-mincut-theorem?t=869.7074166666667): derivation is shown on the screen, written out. - [14:39.518](https://academa.ai/lectures/maxflow-mincut-theorem?t=879.5184166666668): A box is drawn around derivation. ##### [14:42.173](https://academa.ai/lectures/maxflow-mincut-theorem?t=882.1729166666668) Narration: No flow can beat five, because this cut has capacity five and our flow reaches five. So our flow is a maximum flow. And no cut can dip below five, because the flow has value five and this cut achieves it. So this cut is a minimum cut. Board: Unchanged from the preceding beat in this scene. Actions: - [14:47.351](https://academa.ai/lectures/maxflow-mincut-theorem?t=887.3514166666668): value\_num is indicated — a transient flash. - [14:55.861](https://academa.ai/lectures/maxflow-mincut-theorem?t=895.8614166666667): cut\_line is indicated — a transient flash. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): derivation is hidden from the screen — left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): head\_why is hidden from the screen — left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): network is hidden from the screen — left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): node\_s is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): node\_a is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): node\_b is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): node\_t is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): edge\_sa is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): edge\_sb is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): edge\_ab is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): edge\_at is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): edge\_bt is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): flow\_sa is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): flow\_sb is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): flow\_ab is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): flow\_at is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): flow\_bt is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): value\_num is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): value\_word is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): res\_ba is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): region\_s is hidden from the screen — network left the board. - [14:59.263](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.2634166666668): cut\_line is hidden from the screen — network left the board. ##### [14:59.863](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.8634166666668) Narration: Maximum flow equals minimum cut. And notice how it arrived. We never went looking for the cut. We ran out of augmenting paths, and the cut was already sitting there in the leftovers, made of exactly the nodes the search could still see. Board: Empty. Actions: - [14:59.863](https://academa.ai/lectures/maxflow-mincut-theorem?t=899.8634166666668): head\_theorem is shown on the screen, written out. - [15:0.118](https://academa.ai/lectures/maxflow-mincut-theorem?t=900.1184166666667): theorem is shown on the screen, written out. - [15:11.427](https://academa.ai/lectures/maxflow-mincut-theorem?t=911.4274166666668): A box is drawn around theorem. ##### [15:15.87](https://academa.ai/lectures/maxflow-mincut-theorem?t=915.8699166666668) Narration: That is a genuinely useful property of the algorithm, and not just a pretty fact. When it stops, it hands you a certificate. Anyone who doubts that five is the best possible can be shown two edges, of total capacity five, that every single unit has to cross. Board: theorem — a Math \[text\] that says "$max\_f \|f\| = min\_S c(S)$"; head\_theorem — a Heading that says "Maximum Flow Equals Minimum Cut" Actions: - [15:23.276](https://academa.ai/lectures/maxflow-mincut-theorem?t=923.2764166666667): certificate is shown on the screen, written out. ##### [15:34](https://academa.ai/lectures/maxflow-mincut-theorem?t=934.0004166666668) Narration: One more thing before we finish, because this theorem turns up in places that have nothing obvious to do with pipes at all. Board: theorem — a Math \[text\] that says "$max\_f \|f\| = min\_S c(S)$"; certificate — a Panel that says "When the search stops it hands you a proof: a set of edges, totalling the value of your flow, that every unit has to cross."; head\_theorem — a Heading that says "Maximum Flow Equals Minimum Cut" Actions: - [15:36.636](https://academa.ai/lectures/maxflow-mincut-theorem?t=936.6364166666667): theorem is indicated — a transient flash. - [15:40.57](https://academa.ai/lectures/maxflow-mincut-theorem?t=940.5696666666668): certificate is hidden from the screen — left the board. - [15:40.57](https://academa.ai/lectures/maxflow-mincut-theorem?t=940.5696666666668): head\_theorem is hidden from the screen — left the board. - [15:40.57](https://academa.ai/lectures/maxflow-mincut-theorem?t=940.5696666666668): theorem is hidden from the screen — left the board. ### Scene 4: [Matching, and Why It Is the Same Problem](https://academa.ai/lectures/maxflow-mincut-theorem?t=941.6113333333335) Span: 15:41.611–18:58.861 (941.6113333333335s–1138.860541666667s). #### Objects - bip: a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)) - e\_j1t: a Vector \[gray\] drawn in bip (start=(4.8, 3.9), end=(6.6, 2.35), trim\_tip=True) - e\_j2t: a Vector \[gray\] drawn in bip (start=(4.8, 2.35), end=(6.6, 2.35), trim\_tip=True) - e\_j3t: a Vector \[gray\] drawn in bip (start=(4.8, 0.8), end=(6.6, 2.35), trim\_tip=True) - e\_sw1: a Vector \[gray\] drawn in bip (start=(0.6, 2.35), end=(2.4, 3.9), trim\_tip=True) - e\_sw2: a Vector \[gray\] drawn in bip (start=(0.6, 2.35), end=(2.4, 2.35), trim\_tip=True) - e\_sw3: a Vector \[gray\] drawn in bip (start=(0.6, 2.35), end=(2.4, 0.8), trim\_tip=True) - e\_w1j1: a Vector \[gray\] drawn in bip (start=(2.4, 3.9), end=(4.8, 3.9), trim\_tip=True) - e\_w1j2: a Vector \[gray\] drawn in bip (start=(2.4, 3.9), end=(4.8, 2.35), trim\_tip=True) - e\_w2j1: a Vector \[gray\] drawn in bip (start=(2.4, 2.35), end=(4.8, 3.9), trim\_tip=True) - e\_w3j2: a Vector \[gray\] drawn in bip (start=(2.4, 0.8), end=(4.8, 2.35), trim\_tip=True) - e\_w3j3: a Vector \[gray\] drawn in bip (start=(2.4, 0.8), end=(4.8, 0.8), trim\_tip=True) - hall: a Panel that says "A cut that is too small is a set of people whose jobs, taken together, are too few." - head\_close: a Heading that says "Maximum Flow Equals Minimum Cut" - head\_match: a Heading that says "Three People and Three Jobs" - match\_def: a Panel that says "A matching picks lines so that no person and no job is used twice. We want as many lines as possible." - node\_j1: a Point \[blue\] labelled "J\_1" drawn in bip (location=(4.8, 3.9), marker\_radius=0.13) - node\_j2: a Point \[blue\] labelled "J\_2" drawn in bip (location=(4.8, 2.35), marker\_radius=0.13) - node\_j3: a Point \[blue\] labelled "J\_3" drawn in bip (location=(4.8, 0.8), marker\_radius=0.13) - node\_snk: a Point \[blue\] labelled "t" drawn in bip (location=(6.6, 2.35), marker\_radius=0.13) - node\_src: a Point \[blue\] labelled "s" drawn in bip (location=(0.6, 2.35), marker\_radius=0.13) - node\_w1: a Point \[blue\] labelled "P\_1" drawn in bip (location=(2.4, 3.9), marker\_radius=0.13) - node\_w2: a Point \[blue\] labelled "P\_2" drawn in bip (location=(2.4, 2.35), marker\_radius=0.13) - node\_w3: a Point \[blue\] labelled "P\_3" drawn in bip (location=(2.4, 0.8), marker\_radius=0.13) - point: a Point \[yellow\] drawn in bip (location=(2.4, 2.35)) - point\_2: a Point \[yellow\] drawn in bip (location=(2.4, 3.9)) - point\_3: a Point \[yellow\] drawn in bip (location=(2.4, 2.35)) - point\_4: a Point \[yellow\] drawn in bip (location=(2.4, 0.8)) - res\_j1w1: a CurvedArrow \[red\] drawn in bip (start=(4.8, 3.9), end=(2.4, 3.9), bend=0.45) - theorem: a Math \[text\] that says "$max\_f \|f\| = min\_S c(S)$" - unit\_rule: a Math \[text\] that says "$c(e) = 1 quad upright("everywhere")$" #### Beats ##### [15:41.611](https://academa.ai/lectures/maxflow-mincut-theorem?t=941.6113333333335) Narration: Here are three people, and three jobs, and a line whenever a person is able to do a job. The problem is to give as many people as possible a job of their own, with nobody sharing. Board: Empty. Actions: - [15:41.611](https://academa.ai/lectures/maxflow-mincut-theorem?t=941.6113333333335): head\_match is shown on the screen, written out. - [15:41.611](https://academa.ai/lectures/maxflow-mincut-theorem?t=941.6113333333335): bip is shown on the screen, written out. - [15:42.331](https://academa.ai/lectures/maxflow-mincut-theorem?t=942.3313333333335): node\_w1 is shown on the screen, written out. - [15:42.471](https://academa.ai/lectures/maxflow-mincut-theorem?t=942.4713333333335): node\_w2 is shown on the screen, written out. - [15:42.611](https://academa.ai/lectures/maxflow-mincut-theorem?t=942.6113333333335): node\_w3 is shown on the screen, written out. - [15:43.538](https://academa.ai/lectures/maxflow-mincut-theorem?t=943.5383333333335): node\_j1 is shown on the screen, written out. - [15:43.678](https://academa.ai/lectures/maxflow-mincut-theorem?t=943.6783333333335): node\_j2 is shown on the screen, written out. - [15:43.818](https://academa.ai/lectures/maxflow-mincut-theorem?t=943.8183333333335): node\_j3 is shown on the screen, written out. - [15:44.606](https://academa.ai/lectures/maxflow-mincut-theorem?t=944.6063333333335): e\_w1j1 is shown on the screen, drawn. - [15:44.736](https://academa.ai/lectures/maxflow-mincut-theorem?t=944.7363333333335): e\_w1j2 is shown on the screen, drawn. - [15:44.866](https://academa.ai/lectures/maxflow-mincut-theorem?t=944.8663333333335): e\_w2j1 is shown on the screen, drawn. - [15:44.996](https://academa.ai/lectures/maxflow-mincut-theorem?t=944.9963333333335): e\_w3j2 is shown on the screen, drawn. - [15:45.126](https://academa.ai/lectures/maxflow-mincut-theorem?t=945.1263333333335): e\_w3j3 is shown on the screen, drawn. ##### [15:53.577](https://academa.ai/lectures/maxflow-mincut-theorem?t=953.5773333333335) Narration: The lines say who can do what. Person one is able to take either the first job or the second. Person two is qualified for the first job alone. And person three can take the second job or the third. Board: bip — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_match — a Heading that says "Three People and Three Jobs"; node\_w1 — a Point \[blue\] labelled "P\_1" drawn in bip (location=(2.4, 3.9), marker\_radius=0.13); node\_w2 — a Point \[blue\] labelled "P\_2" drawn in bip (location=(2.4, 2.35), marker\_radius=0.13); node\_w3 — a Point \[blue\] labelled "P\_3" drawn in bip (location=(2.4, 0.8), marker\_radius=0.13); node\_j1 — a Point \[blue\] labelled "J\_1" drawn in bip (location=(4.8, 3.9), marker\_radius=0.13); node\_j2 — a Point \[blue\] labelled "J\_2" drawn in bip (location=(4.8, 2.35), marker\_radius=0.13); node\_j3 — a Point \[blue\] labelled "J\_3" drawn in bip (location=(4.8, 0.8), marker\_radius=0.13); e\_w1j1 — a Vector \[gray\] drawn in bip (start=(2.4, 3.9), end=(4.8, 3.9), trim\_tip=True); e\_w1j2 — a Vector \[gray\] drawn in bip (start=(2.4, 3.9), end=(4.8, 2.35), trim\_tip=True); e\_w2j1 — a Vector \[gray\] drawn in bip (start=(2.4, 2.35), end=(4.8, 3.9), trim\_tip=True); e\_w3j2 — a Vector \[gray\] drawn in bip (start=(2.4, 0.8), end=(4.8, 2.35), trim\_tip=True); e\_w3j3 — a Vector \[gray\] drawn in bip (start=(2.4, 0.8), end=(4.8, 0.8), trim\_tip=True) Actions: - [15:58.152](https://academa.ai/lectures/maxflow-mincut-theorem?t=958.1523333333336): e\_w1j1 is indicated — a transient flash. - [15:59.359](https://academa.ai/lectures/maxflow-mincut-theorem?t=959.3593333333336): e\_w1j2 is indicated — a transient flash. - [16:2.668](https://academa.ai/lectures/maxflow-mincut-theorem?t=962.6683333333335): e\_w2j1 is indicated — a transient flash. - [16:5.478](https://academa.ai/lectures/maxflow-mincut-theorem?t=965.4783333333335): e\_w3j2 is indicated — a transient flash. - [16:6.372](https://academa.ai/lectures/maxflow-mincut-theorem?t=966.3723333333335): e\_w3j3 is indicated — a transient flash. ##### [16:8.075](https://academa.ai/lectures/maxflow-mincut-theorem?t=968.0753333333334) Narration: This is bipartite matching, and it looks like a completely different kind of question from pushing water down pipes. It is exactly the same question. Board: Unchanged from the preceding beat in this scene. Actions: - [16:9.886](https://academa.ai/lectures/maxflow-mincut-theorem?t=969.8863333333335): bip moves to a new place on the board. - [16:9.886](https://academa.ai/lectures/maxflow-mincut-theorem?t=969.8863333333335): match\_def is shown on the screen, written out. ##### [16:17.673](https://academa.ai/lectures/maxflow-mincut-theorem?t=977.6728333333335) Narration: Add a source on the left, joined to every person. Add a sink on the right, joined to every job. And give every edge in the whole picture a capacity of one. Board: match\_def — a Panel that says "A matching picks lines so that no person and no job is used twice. We want as many lines as possible."; bip — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_match — a Heading that says "Three People and Three Jobs"; node\_w1 — a Point \[blue\] labelled "P\_1" drawn in bip (location=(2.4, 3.9), marker\_radius=0.13); node\_w2 — a Point \[blue\] labelled "P\_2" drawn in bip (location=(2.4, 2.35), marker\_radius=0.13); node\_w3 — a Point \[blue\] labelled "P\_3" drawn in bip (location=(2.4, 0.8), marker\_radius=0.13); node\_j1 — a Point \[blue\] labelled "J\_1" drawn in bip (location=(4.8, 3.9), marker\_radius=0.13); node\_j2 — a Point \[blue\] labelled "J\_2" drawn in bip (location=(4.8, 2.35), marker\_radius=0.13); node\_j3 — a Point \[blue\] labelled "J\_3" drawn in bip (location=(4.8, 0.8), marker\_radius=0.13); e\_w1j1 — a Vector \[gray\] drawn in bip (start=(2.4, 3.9), end=(4.8, 3.9), trim\_tip=True); e\_w1j2 — a Vector \[gray\] drawn in bip (start=(2.4, 3.9), end=(4.8, 2.35), trim\_tip=True); e\_w2j1 — a Vector \[gray\] drawn in bip (start=(2.4, 2.35), end=(4.8, 3.9), trim\_tip=True); e\_w3j2 — a Vector \[gray\] drawn in bip (start=(2.4, 0.8), end=(4.8, 2.35), trim\_tip=True); e\_w3j3 — a Vector \[gray\] drawn in bip (start=(2.4, 0.8), end=(4.8, 0.8), trim\_tip=True) Actions: - [16:18.358](https://academa.ai/lectures/maxflow-mincut-theorem?t=978.3583333333335): node\_src is shown on the screen, written out. - [16:20.296](https://academa.ai/lectures/maxflow-mincut-theorem?t=980.2963333333335): e\_sw1 is shown on the screen, drawn. - [16:20.416](https://academa.ai/lectures/maxflow-mincut-theorem?t=980.4163333333335): e\_sw2 is shown on the screen, drawn. - [16:20.536](https://academa.ai/lectures/maxflow-mincut-theorem?t=980.5363333333335): e\_sw3 is shown on the screen, drawn. - [16:21.794](https://academa.ai/lectures/maxflow-mincut-theorem?t=981.7943333333335): node\_snk is shown on the screen, written out. - [16:23.907](https://academa.ai/lectures/maxflow-mincut-theorem?t=983.9073333333336): e\_j1t is shown on the screen, drawn. - [16:24.027](https://academa.ai/lectures/maxflow-mincut-theorem?t=984.0273333333334): e\_j2t is shown on the screen, drawn. - [16:24.147](https://academa.ai/lectures/maxflow-mincut-theorem?t=984.1473333333334): e\_j3t is shown on the screen, drawn. - [16:26.972](https://academa.ai/lectures/maxflow-mincut-theorem?t=986.9723333333335): unit\_rule is shown on the screen, written out. ##### [16:29.07](https://academa.ai/lectures/maxflow-mincut-theorem?t=989.0703333333335) Narration: Now push flow through it. A unit of flow leaving the source has to pick one person, because that person's own edge from the source has capacity one and can carry nothing more. Board: match\_def — a Panel that says "A matching picks lines so that no person and no job is used twice. We want as many lines as possible."; unit\_rule — a Math \[text\] that says "$c(e) = 1 quad upright("everywhere")$"; bip — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_match — a Heading that says "Three People and Three Jobs"; node\_w1 — a Point \[blue\] labelled "P\_1" drawn in bip (location=(2.4, 3.9), marker\_radius=0.13); node\_w2 — a Point \[blue\] labelled "P\_2" drawn in bip (location=(2.4, 2.35), marker\_radius=0.13); node\_w3 — a Point \[blue\] labelled "P\_3" drawn in bip (location=(2.4, 0.8), marker\_radius=0.13); node\_j1 — a Point \[blue\] labelled "J\_1" drawn in bip (location=(4.8, 3.9), marker\_radius=0.13); node\_j2 — a Point \[blue\] labelled "J\_2" drawn in bip (location=(4.8, 2.35), marker\_radius=0.13); node\_j3 — a Point \[blue\] labelled "J\_3" drawn in bip (location=(4.8, 0.8), marker\_radius=0.13); e\_w1j1 — a Vector \[gray\] drawn in bip (start=(2.4, 3.9), end=(4.8, 3.9), trim\_tip=True); e\_w1j2 — a Vector \[gray\] drawn in bip (start=(2.4, 3.9), end=(4.8, 2.35), trim\_tip=True); e\_w2j1 — a Vector \[gray\] drawn in bip (start=(2.4, 2.35), end=(4.8, 3.9), trim\_tip=True); e\_w3j2 — a Vector \[gray\] drawn in bip (start=(2.4, 0.8), end=(4.8, 2.35), trim\_tip=True); e\_w3j3 — a Vector \[gray\] drawn in bip (start=(2.4, 0.8), end=(4.8, 0.8), trim\_tip=True); node\_src — a Point \[blue\] labelled "s" drawn in bip (location=(0.6, 2.35), marker\_radius=0.13); e\_sw1 — a Vector \[gray\] drawn in bip (start=(0.6, 2.35), end=(2.4, 3.9), trim\_tip=True); e\_sw2 — a Vector \[gray\] drawn in bip (start=(0.6, 2.35), end=(2.4, 2.35), trim\_tip=True); e\_sw3 — a Vector \[gray\] drawn in bip (start=(0.6, 2.35), end=(2.4, 0.8), trim\_tip=True); node\_snk — a Point \[blue\] labelled "t" drawn in bip (location=(6.6, 2.35), marker\_radius=0.13); e\_j1t — a Vector \[gray\] drawn in bip (start=(4.8, 3.9), end=(6.6, 2.35), trim\_tip=True); e\_j2t — a Vector \[gray\] drawn in bip (start=(4.8, 2.35), end=(6.6, 2.35), trim\_tip=True); e\_j3t — a Vector \[gray\] drawn in bip (start=(4.8, 0.8), end=(6.6, 2.35), trim\_tip=True) Actions: - [16:33.517](https://academa.ai/lectures/maxflow-mincut-theorem?t=993.5173333333335): e\_sw1 is indicated — a transient flash. - [16:33.517](https://academa.ai/lectures/maxflow-mincut-theorem?t=993.5173333333335): e\_sw2 is indicated — a transient flash. - [16:33.517](https://academa.ai/lectures/maxflow-mincut-theorem?t=993.5173333333335): e\_sw3 is indicated — a transient flash. ##### [16:41.013](https://academa.ai/lectures/maxflow-mincut-theorem?t=1001.0133333333335) Narration: It then crosses to a job that person can do, and leaves through that job's edge to the sink, which also has capacity one. So one unit of flow is exactly one person doing one job, and no job can ever be taken twice. Board: Unchanged from the preceding beat in this scene. Actions: - [16:44.438](https://academa.ai/lectures/maxflow-mincut-theorem?t=1004.4383333333335): e\_j1t is indicated — a transient flash. - [16:44.438](https://academa.ai/lectures/maxflow-mincut-theorem?t=1004.4383333333335): e\_j2t is indicated — a transient flash. - [16:44.438](https://academa.ai/lectures/maxflow-mincut-theorem?t=1004.4383333333335): e\_j3t is indicated — a transient flash. ##### [16:56.823](https://academa.ai/lectures/maxflow-mincut-theorem?t=1016.8228333333335) Narration: The value of the flow is the size of the matching. Maximum flow is maximum matching, and it is the same algorithm, completely unchanged. Board: Unchanged from the preceding beat in this scene. Actions: - [17:3.858](https://academa.ai/lectures/maxflow-mincut-theorem?t=1023.8583333333335): unit\_rule is indicated — a transient flash. ##### [17:6.675](https://academa.ai/lectures/maxflow-mincut-theorem?t=1026.6753333333336) Narration: Now watch the same mistake happen again. Send the first unit through person one to job one. And send a second unit through person three to job three. Board: Unchanged from the preceding beat in this scene. Actions: - [17:9.984](https://academa.ai/lectures/maxflow-mincut-theorem?t=1029.9843333333336): e\_sw1 is emphasized. - [17:9.984](https://academa.ai/lectures/maxflow-mincut-theorem?t=1029.9843333333336): e\_w1j1 is emphasized. - [17:9.984](https://academa.ai/lectures/maxflow-mincut-theorem?t=1029.9843333333336): e\_j1t is emphasized. - [17:13.862](https://academa.ai/lectures/maxflow-mincut-theorem?t=1033.8623333333335): e\_sw3 is emphasized. - [17:13.862](https://academa.ai/lectures/maxflow-mincut-theorem?t=1033.8623333333335): e\_w3j3 is emphasized. - [17:13.862](https://academa.ai/lectures/maxflow-mincut-theorem?t=1033.8623333333335): e\_j3t is emphasized. ##### [17:17.214](https://academa.ai/lectures/maxflow-mincut-theorem?t=1037.2138333333335) Narration: Now person two. The only job on their list is job one, and job one is taken. Greedy stops with two people placed and one left out in the cold. Board: Unchanged from the preceding beat in this scene. Actions: - [17:17.852](https://academa.ai/lectures/maxflow-mincut-theorem?t=1037.8523333333335): point is shown on the screen, grown. - [17:19.852](https://academa.ai/lectures/maxflow-mincut-theorem?t=1039.8523333333335): point is hidden from the screen. - [17:20.023](https://academa.ai/lectures/maxflow-mincut-theorem?t=1040.0233333333335): e\_w2j1 is indicated — a transient flash. - [17:22.426](https://academa.ai/lectures/maxflow-mincut-theorem?t=1042.4263333333336): e\_w1j1 is indicated — a transient flash. ##### [17:27.856](https://academa.ai/lectures/maxflow-mincut-theorem?t=1047.8563333333334) Narration: But the residual graph has a backward arrow on the edge from person one to job one, because that edge is carrying a unit. Follow it. Board: Unchanged from the preceding beat in this scene. Actions: - [17:29.888](https://academa.ai/lectures/maxflow-mincut-theorem?t=1049.8883333333335): res\_j1w1 is shown on the screen, written out. ##### [17:38.168](https://academa.ai/lectures/maxflow-mincut-theorem?t=1058.1683333333335) Narration: From the source to person two. Across to job one. Backwards up to person one. Across to job two, which nobody has taken. And out to the sink. Board: match\_def — a Panel that says "A matching picks lines so that no person and no job is used twice. We want as many lines as possible."; unit\_rule — a Math \[text\] that says "$c(e) = 1 quad upright("everywhere")$"; bip — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_match — a Heading that says "Three People and Three Jobs"; node\_w1 — a Point \[blue\] labelled "P\_1" drawn in bip (location=(2.4, 3.9), marker\_radius=0.13); node\_w2 — a Point \[blue\] labelled "P\_2" drawn in bip (location=(2.4, 2.35), marker\_radius=0.13); node\_w3 — a Point \[blue\] labelled "P\_3" drawn in bip (location=(2.4, 0.8), marker\_radius=0.13); node\_j1 — a Point \[blue\] labelled "J\_1" drawn in bip (location=(4.8, 3.9), marker\_radius=0.13); node\_j2 — a Point \[blue\] labelled "J\_2" drawn in bip (location=(4.8, 2.35), marker\_radius=0.13); node\_j3 — a Point \[blue\] labelled "J\_3" drawn in bip (location=(4.8, 0.8), marker\_radius=0.13); e\_w1j1 — a Vector \[gray\] drawn in bip (start=(2.4, 3.9), end=(4.8, 3.9), trim\_tip=True); e\_w1j2 — a Vector \[gray\] drawn in bip (start=(2.4, 3.9), end=(4.8, 2.35), trim\_tip=True); e\_w2j1 — a Vector \[gray\] drawn in bip (start=(2.4, 2.35), end=(4.8, 3.9), trim\_tip=True); e\_w3j2 — a Vector \[gray\] drawn in bip (start=(2.4, 0.8), end=(4.8, 2.35), trim\_tip=True); e\_w3j3 — a Vector \[gray\] drawn in bip (start=(2.4, 0.8), end=(4.8, 0.8), trim\_tip=True); node\_src — a Point \[blue\] labelled "s" drawn in bip (location=(0.6, 2.35), marker\_radius=0.13); e\_sw1 — a Vector \[gray\] drawn in bip (start=(0.6, 2.35), end=(2.4, 3.9), trim\_tip=True); e\_sw2 — a Vector \[gray\] drawn in bip (start=(0.6, 2.35), end=(2.4, 2.35), trim\_tip=True); e\_sw3 — a Vector \[gray\] drawn in bip (start=(0.6, 2.35), end=(2.4, 0.8), trim\_tip=True); node\_snk — a Point \[blue\] labelled "t" drawn in bip (location=(6.6, 2.35), marker\_radius=0.13); e\_j1t — a Vector \[gray\] drawn in bip (start=(4.8, 3.9), end=(6.6, 2.35), trim\_tip=True); e\_j2t — a Vector \[gray\] drawn in bip (start=(4.8, 2.35), end=(6.6, 2.35), trim\_tip=True); e\_j3t — a Vector \[gray\] drawn in bip (start=(4.8, 0.8), end=(6.6, 2.35), trim\_tip=True); res\_j1w1 — a CurvedArrow \[red\] drawn in bip (start=(4.8, 3.9), end=(2.4, 3.9), bend=0.45) Actions: - [17:38.975](https://academa.ai/lectures/maxflow-mincut-theorem?t=1058.9753333333335): e\_sw2 is emphasized. - [17:40.89](https://academa.ai/lectures/maxflow-mincut-theorem?t=1060.8903333333335): e\_w2j1 is emphasized. - [17:43.027](https://academa.ai/lectures/maxflow-mincut-theorem?t=1063.0273333333334): res\_j1w1 is emphasized. - [17:45.465](https://academa.ai/lectures/maxflow-mincut-theorem?t=1065.4653333333335): e\_w1j2 is emphasized. - [17:48.855](https://academa.ai/lectures/maxflow-mincut-theorem?t=1068.8553333333334): e\_j2t is emphasized. ##### [17:50.714](https://academa.ai/lectures/maxflow-mincut-theorem?t=1070.7143333333336) Narration: Push one unit along that path, and the picture rearranges itself. Person one moves over to job two. Person two takes job one. And person three keeps job three. Board: Unchanged from the preceding beat in this scene. Actions: - [17:50.714](https://academa.ai/lectures/maxflow-mincut-theorem?t=1070.7143333333336): e\_sw2 is no longer emphasized. - [17:50.714](https://academa.ai/lectures/maxflow-mincut-theorem?t=1070.7143333333336): e\_w2j1 is no longer emphasized. - [17:50.714](https://academa.ai/lectures/maxflow-mincut-theorem?t=1070.7143333333336): e\_w1j2 is no longer emphasized. - [17:50.714](https://academa.ai/lectures/maxflow-mincut-theorem?t=1070.7143333333336): e\_j2t is no longer emphasized. - [17:50.714](https://academa.ai/lectures/maxflow-mincut-theorem?t=1070.7143333333336): res\_j1w1 is no longer emphasized. - [17:53.646](https://academa.ai/lectures/maxflow-mincut-theorem?t=1073.6463333333336): res\_j1w1 is hidden from the screen. - [17:56.282](https://academa.ai/lectures/maxflow-mincut-theorem?t=1076.2823333333336): e\_w1j1 is no longer emphasized. - [17:56.282](https://academa.ai/lectures/maxflow-mincut-theorem?t=1076.2823333333336): e\_w1j2 is emphasized. - [17:56.282](https://academa.ai/lectures/maxflow-mincut-theorem?t=1076.2823333333336): e\_j2t is emphasized. - [17:59.022](https://academa.ai/lectures/maxflow-mincut-theorem?t=1079.0223333333336): e\_sw2 is emphasized. - [17:59.022](https://academa.ai/lectures/maxflow-mincut-theorem?t=1079.0223333333336): e\_w2j1 is emphasized. ##### [18:4.185](https://academa.ai/lectures/maxflow-mincut-theorem?t=1084.1848333333335) Narration: Three people, three jobs, and nobody sharing. The backward edge did exactly what a person would do out loud. You take that one, and I will take another. Board: match\_def — a Panel that says "A matching picks lines so that no person and no job is used twice. We want as many lines as possible."; unit\_rule — a Math \[text\] that says "$c(e) = 1 quad upright("everywhere")$"; bip — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_match — a Heading that says "Three People and Three Jobs"; node\_w1 — a Point \[blue\] labelled "P\_1" drawn in bip (location=(2.4, 3.9), marker\_radius=0.13); node\_w2 — a Point \[blue\] labelled "P\_2" drawn in bip (location=(2.4, 2.35), marker\_radius=0.13); node\_w3 — a Point \[blue\] labelled "P\_3" drawn in bip (location=(2.4, 0.8), marker\_radius=0.13); node\_j1 — a Point \[blue\] labelled "J\_1" drawn in bip (location=(4.8, 3.9), marker\_radius=0.13); node\_j2 — a Point \[blue\] labelled "J\_2" drawn in bip (location=(4.8, 2.35), marker\_radius=0.13); node\_j3 — a Point \[blue\] labelled "J\_3" drawn in bip (location=(4.8, 0.8), marker\_radius=0.13); e\_w1j1 — a Vector \[gray\] drawn in bip (start=(2.4, 3.9), end=(4.8, 3.9), trim\_tip=True); e\_w1j2 — a Vector \[gray\] drawn in bip (start=(2.4, 3.9), end=(4.8, 2.35), trim\_tip=True); e\_w2j1 — a Vector \[gray\] drawn in bip (start=(2.4, 2.35), end=(4.8, 3.9), trim\_tip=True); e\_w3j2 — a Vector \[gray\] drawn in bip (start=(2.4, 0.8), end=(4.8, 2.35), trim\_tip=True); e\_w3j3 — a Vector \[gray\] drawn in bip (start=(2.4, 0.8), end=(4.8, 0.8), trim\_tip=True); node\_src — a Point \[blue\] labelled "s" drawn in bip (location=(0.6, 2.35), marker\_radius=0.13); e\_sw1 — a Vector \[gray\] drawn in bip (start=(0.6, 2.35), end=(2.4, 3.9), trim\_tip=True); e\_sw2 — a Vector \[gray\] drawn in bip (start=(0.6, 2.35), end=(2.4, 2.35), trim\_tip=True); e\_sw3 — a Vector \[gray\] drawn in bip (start=(0.6, 2.35), end=(2.4, 0.8), trim\_tip=True); node\_snk — a Point \[blue\] labelled "t" drawn in bip (location=(6.6, 2.35), marker\_radius=0.13); e\_j1t — a Vector \[gray\] drawn in bip (start=(4.8, 3.9), end=(6.6, 2.35), trim\_tip=True); e\_j2t — a Vector \[gray\] drawn in bip (start=(4.8, 2.35), end=(6.6, 2.35), trim\_tip=True); e\_j3t — a Vector \[gray\] drawn in bip (start=(4.8, 0.8), end=(6.6, 2.35), trim\_tip=True) Actions: - [18:4.533](https://academa.ai/lectures/maxflow-mincut-theorem?t=1084.5333333333335): point\_2 is shown on the screen, grown. - [18:6.533](https://academa.ai/lectures/maxflow-mincut-theorem?t=1086.5333333333335): point\_2 is hidden from the screen. - [18:6.933](https://academa.ai/lectures/maxflow-mincut-theorem?t=1086.9333333333334): point\_3 is shown on the screen, grown. - [18:8.933](https://academa.ai/lectures/maxflow-mincut-theorem?t=1088.9333333333334): point\_3 is hidden from the screen. - [18:9.733](https://academa.ai/lectures/maxflow-mincut-theorem?t=1089.7333333333336): point\_4 is shown on the screen, grown. - [18:11.733](https://academa.ai/lectures/maxflow-mincut-theorem?t=1091.7333333333336): point\_4 is hidden from the screen. ##### [18:15.895](https://academa.ai/lectures/maxflow-mincut-theorem?t=1095.8948333333335) Narration: And the minimum cut says something too. When a matching cannot cover everybody, the cut tells you why. It exhibits a set of people whose lists of jobs, taken together, are simply too short to go round. Board: Unchanged from the preceding beat in this scene. Actions: - [18:23](https://academa.ai/lectures/maxflow-mincut-theorem?t=1103.0003333333334): hall is shown on the screen, written out. ##### [18:29.614](https://academa.ai/lectures/maxflow-mincut-theorem?t=1109.6138333333336) Narration: That is Hall's condition, and it falls straight out of the theorem we have just proved. Board: match\_def — a Panel that says "A matching picks lines so that no person and no job is used twice. We want as many lines as possible."; unit\_rule — a Math \[text\] that says "$c(e) = 1 quad upright("everywhere")$"; hall — a Panel that says "A cut that is too small is a set of people whose jobs, taken together, are too few."; bip — a Figure (x\_range=(0.0, 7.2), y\_range=(0.0, 4.7), aspect=(7.2, 4.7)); head\_match — a Heading that says "Three People and Three Jobs"; node\_w1 — a Point \[blue\] labelled "P\_1" drawn in bip (location=(2.4, 3.9), marker\_radius=0.13); node\_w2 — a Point \[blue\] labelled "P\_2" drawn in bip (location=(2.4, 2.35), marker\_radius=0.13); node\_w3 — a Point \[blue\] labelled "P\_3" drawn in bip (location=(2.4, 0.8), marker\_radius=0.13); node\_j1 — a Point \[blue\] labelled "J\_1" drawn in bip (location=(4.8, 3.9), marker\_radius=0.13); node\_j2 — a Point \[blue\] labelled "J\_2" drawn in bip (location=(4.8, 2.35), marker\_radius=0.13); node\_j3 — a Point \[blue\] labelled "J\_3" drawn in bip (location=(4.8, 0.8), marker\_radius=0.13); e\_w1j1 — a Vector \[gray\] drawn in bip (start=(2.4, 3.9), end=(4.8, 3.9), trim\_tip=True); e\_w1j2 — a Vector \[gray\] drawn in bip (start=(2.4, 3.9), end=(4.8, 2.35), trim\_tip=True); e\_w2j1 — a Vector \[gray\] drawn in bip (start=(2.4, 2.35), end=(4.8, 3.9), trim\_tip=True); e\_w3j2 — a Vector \[gray\] drawn in bip (start=(2.4, 0.8), end=(4.8, 2.35), trim\_tip=True); e\_w3j3 — a Vector \[gray\] drawn in bip (start=(2.4, 0.8), end=(4.8, 0.8), trim\_tip=True); node\_src — a Point \[blue\] labelled "s" drawn in bip (location=(0.6, 2.35), marker\_radius=0.13); e\_sw1 — a Vector \[gray\] drawn in bip (start=(0.6, 2.35), end=(2.4, 3.9), trim\_tip=True); e\_sw2 — a Vector \[gray\] drawn in bip (start=(0.6, 2.35), end=(2.4, 2.35), trim\_tip=True); e\_sw3 — a Vector \[gray\] drawn in bip (start=(0.6, 2.35), end=(2.4, 0.8), trim\_tip=True); node\_snk — a Point \[blue\] labelled "t" drawn in bip (location=(6.6, 2.35), marker\_radius=0.13); e\_j1t — a Vector \[gray\] drawn in bip (start=(4.8, 3.9), end=(6.6, 2.35), trim\_tip=True); e\_j2t — a Vector \[gray\] drawn in bip (start=(4.8, 2.35), end=(6.6, 2.35), trim\_tip=True); e\_j3t — a Vector \[gray\] drawn in bip (start=(4.8, 0.8), end=(6.6, 2.35), trim\_tip=True) Actions: - [18:30.821](https://academa.ai/lectures/maxflow-mincut-theorem?t=1110.8213333333335): hall (the "too few" part) is emphasized. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): bip is hidden from the screen — left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): node\_w1 is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): node\_w2 is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): node\_w3 is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): node\_j1 is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): node\_j2 is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): node\_j3 is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): e\_w1j1 is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): e\_w1j2 is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): e\_w2j1 is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): e\_w3j2 is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): e\_w3j3 is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): node\_src is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): e\_sw1 is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): e\_sw2 is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): e\_sw3 is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): node\_snk is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): e\_j1t is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): e\_j2t is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): e\_j3t is hidden from the screen — bip left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): hall is hidden from the screen — left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): head\_match is hidden from the screen — left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): match\_def is hidden from the screen — left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): unit\_rule is hidden from the screen — left the board. - [18:34.978](https://academa.ai/lectures/maxflow-mincut-theorem?t=1114.9778333333334): hall (the "too few" part) is no longer emphasized. ##### [18:35.578](https://academa.ai/lectures/maxflow-mincut-theorem?t=1115.5778333333335) Narration: So there it is. Push flow along augmenting paths. When you get stuck, let the residual graph undo an earlier decision. And when even that runs out, the nodes you can still reach form a cut, its capacity equals the flow you are holding, and neither number can move any further. Board: Empty. Actions: - [18:35.578](https://academa.ai/lectures/maxflow-mincut-theorem?t=1115.5778333333335): head\_close is shown on the screen, written out. - [18:48.186](https://academa.ai/lectures/maxflow-mincut-theorem?t=1128.1863333333336): theorem is shown on the screen, written out. ##### [18:54.742](https://academa.ai/lectures/maxflow-mincut-theorem?t=1134.7423333333336) Narration: Maximum flow equals minimum cut. Board: theorem — a Math \[text\] that says "$max\_f \|f\| = min\_S c(S)$"; head\_close — a Heading that says "Maximum Flow Equals Minimum Cut" Actions: - [18:55.09](https://academa.ai/lectures/maxflow-mincut-theorem?t=1135.0903333333335): A box is drawn around theorem. - [18:57.819](https://academa.ai/lectures/maxflow-mincut-theorem?t=1137.8188750000002): head\_close is hidden from the screen — left the board. - [18:57.819](https://academa.ai/lectures/maxflow-mincut-theorem?t=1137.8188750000002): theorem is hidden from the screen — left the board.