Chapter 24: Maximum Flow: Flow Networks and the Ford-Fulkerson Method

Welcome to Last Minute Lecture.

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement not replaced the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

All right, welcome back everyone to the Deep Dive.

Ready to jump into something pretty fascinating today, we're going to be talking about flow networks.

Flow networks.

Yeah, I think a lot of people when they hear flow networks,

they probably think of, you know, like water flowing through pipes or something like that.

Yeah, it's a very visual concept.

Very visual, right.

But it's actually much more abstract and versatile than that.

Absolutely.

It can really be applied to all sorts of different things.

Yeah, and it has applications in so many different fields, really anywhere where you're trying to move something from one place to

and there's limited capacity in the connections between those places.

So yeah, it could be fluids through pipes.

It could be, as you said, cars on a highway system, packets of data on the internet.

Oh yeah, data flow, right?

Absolutely.

Data flow is a great example.

That's a really good one.

Any kind of network where you have these capacity constraints.

Yeah.

So we're going to be taking a deep dive into this whole concept today.

Okay, that's good.

We've got some really great material that explains it from the ground up.

So we're going to be talking about what a flow network is exactly, what the maximum flow problem is, and then some of the really clever algorithms that have been developed to solve it.

It's a very rich area with some pretty elegant solutions.

It is.

It really is.

I was reading through this and I've just kind of blown away by how clever some of these algorithms are.

Yeah, some very bright people have worked on this problem.

Yeah, for sure.

Okay, so let's just start at the very beginning.

What exactly is a flow network?

Well, a flow network is, at its core, a directed graph.

So, you know, you've got your set of vertices, which we'll call bile, and your set of edges connecting them.

I dollars.

And so when we say directed, that means the connections between these points, these vertices, have a direction.

You know, it's like a one -way street.

Okay, so it's not just a connection.

It's a connection in a particular direction.

Exactly.

And each one of those connections, those edges, has what we call a capacity.

And we represent that with, you know, niche UVL.

So if you have an edge going from vertex to vertex, the capacity V is the maximum amount of whatever's flowing that can go through that particular connection.

Okay, so like the width of the pipe or the number of lanes on the highway or something like that.

Exactly.

You got it.

And this capacity is always non -negative, C -O -V -VALOR.

And to make things a bit simpler, we're going to start by assuming that we don't have any anti -parallel edges.

What that means is, if there's a connection from U to V, there isn't one going directly back from V to U at the same time.

We'll deal with that little wrinkle a bit later.

All right, so one -way connections with a maximum limit.

Got it.

What else is part of the definition of a flow network?

Okay, so two other crucial components.

First, we always have a single source vertex, which we usually label as EZ.

This is where everything originates, like the starting point of our flow.

Okay, so everything starts at EZ.

Exactly.

And second, we have a single sync vertex labeled as T.

This is our destination, where all the flow is ultimately trying to get to.

So it's all about getting from O's to T through this network.

Right.

And one more practical point to keep in mind,

we assume that every single vertex in our flow network is on at least one path from the sources to the sync T.

So no dead ends, everything's connected and playing a role in the flow.

Yeah, precisely.

No isolated parts of the network that don't contribute to getting stuff from source to sync.

Got it.

So we've got this network, these limits on connections, a starting point, and a goal.

Now, what exactly is a flow within this setup?

How do we define what's moving?

All right, good question.

So flow, we represent it with a function.

You know, all the math notation, we use a function, $5, V times V right arrow math.

We don't have to get too deep into the mic.

Don't worry, we'll keep it intuitive.

Basically, this flow function tells us how much of whatever we're moving is going from one point to another at any given time.

And this flow has to follow two main rules.

Rules.

Okay.

Yeah.

Rules of the flow game.

First one is the capacity constraint.

It's pretty straightforward.

The flow between any two vertices V V E D can't be bigger than the capacity of the edge connecting them C U V E.

Okay, that makes sense.

Can't put more through a pipe than it can handle.

Exactly.

So it has to be greater than or equal to zero, zero dollar new V V, but it can't exceed the capacity V V V V E.

All right.

So flow is always positive or zero and can't break the capacity limit.

What's the other rule?

The second one is called flow conservation.

Basically for every vertex in the network, except the source and the sink, the total flow coming into that vertex has to be equal to the total flow going out of it.

Okay.

So no leaks or storage in the middle.

You got it.

Everything that comes in has to go out.

So how do we write that rule down?

In math terms, it's some V and V F V E E U some V U A E U simple V for any vertex.

That's not the sources or the sink T.

Don't worry too much about the symbols.

The concept is what matters.

Yeah, no worries.

So no buildup, no loss, just passing through.

Okay.

Now how do we actually measure the total flow in the whole network?

Like how much are we successfully moving from start to finish?

Good question.

So the value of a flow and we write that as $5 is basically the net flow that's coming out of the source.

Okay.

So how much we're pushing out of the starting point.

Exactly.

And we calculate it by taking the total flow going from the source as to all the vertices it's connected to.

And then we subtract any flow that might be coming back into the source.

It usually in a classic maximum flow problem, you wouldn't have flow going back to the some V some V some V F S.

Okay.

Makes sense.

We're trying to maximize that value, get as much as possible from S to T.

Exactly.

That's the whole point of the maximum flow problem.

Finding the flow that gives us the biggest possible $5 value.

Okay.

I think we've got a pretty good grasp on the basics now, what a flow network is, what flow itself is, and how we measure how much we're moving.

Sounds good.

You mentioned earlier those anti -parallel edges, those two -way connections we're initially ignoring.

How do we actually deal with those in our model?

Yeah.

So remember, we assumed there wouldn't be a direct connection going back and forth between the same two vertices.

But what if we do have a situation where there's an edge from, say, vertex of V to do or to, and also an edge going directly back from V to V to large.

That gets a bit messy.

It does.

But we can use a little trick.

We basically introduce a new vertex.

Oh, okay.

Yeah.

So let's say we've got both V to do and V to feel V1 dollars in our network.

We pick one of those edges, let's say V or V to do.

And we replace it with a new vertex.

We'll call it V dollars and two new edges.

One going from V land to V dollars and another going from V dollar to the V dollar.

Okay.

So we're basically splitting that two -way connection into two one -way connections with a stop in the middle.

Exactly.

And the important thing is we give both those new edges the same capacity as the original edge we replaced.

That way we're still allowing the same amount of flow between VL1 and VL2 just now it's going through this intermediary.

And now we don't have those pesky anti -parallel edges anymore.

So everything sits nicely into our initial assumptions.

That's pretty clever.

Keeps things tidy, but still allows for the same flow.

Exactly.

Okay.

What about situations where you might have multiple sources or multiple sinks?

You know, like in a real world scenario, you might have goods flowing out of multiple factories to multiple distribution centers.

Yeah, that's a great point.

It's definitely more realistic.

So imagine we have multiple sources, we'll call them

S2, S -E -L -S -S -M -E and multiple sinks, $2, T2, T -T -E.

We can actually simplify this into our basic single source, single sink framework.

Glad that we do that.

We create what we call a super source and a super sink.

Yeah.

So we introduce a new source vertex, we'll just call it clings, and we add edges from this new as to each of our original sources, sex, dollars, S2, and so on.

And we give each of those new edges a huge capacity, like effectively infinite.

So we're basically creating a central starting point that can feed unlimited amounts to all the original sources.

Exactly.

And we do the same thing on the sink side.

We create a new sink vertex T, our super sink, and add edges from each of the original sinks, T dollars, T2D, et cetera, to this new T, also with infinite capacity.

So now anything coming from any of the original sources can reach any of the original sinks through this new super source and super sink.

Precisely.

And the maximum flow from this new super source as to the new super sink T in this modified network will be the same as the maximum total flow we could have achieved from all the original sources to all the original sinks.

That's really elegant.

It's a neat way to handle more complex real world situations.

Yeah.

Okay.

So we've set up the problem.

We know what a flow network is, how to handle variations.

Now, how do we actually solve this?

How do we find that maximum flow?

All right.

Now comes the fun part.

So one of the most fundamental algorithms for solving this is called the Ford -Fulkerson method.

Ford -Fulkerson.

Okay.

Yep.

And it's an iterative method.

We start with some initial flow, often just zero flow everywhere in the network, and then we try to increase that flow step by step.

And we do this by finding what we call augmenting paths in something called the residual network.

Okay.

Two new terms.

Augmenting paths and residual network.

Let's break those down.

All right.

So residual network first.

Think of it this way.

The residual network tells us where we have room to increase the flow, given the current flow we have in the network.

So it's like a map of potential flow increases.

Exactly.

So for any edge in the original network, let's say from uv with a capacity ddb and a current flow of u, the residual capacity in that same direction from u to v is simply the remaining capacity, which is stino vev.

Okay.

So how much more we can push through that edge makes sense.

Right.

Now here's where it gets really interesting.

If there's some flow going in the opposite direction from v back to u in the original network, we also include a reverse edge in the residual network.

The reverse edge.

Yeah.

So in our residual network, we have an edge from v to u with a residual capacity equal to the current flow in the opposite direction, 5v u dollar.

Think of it like this.

We could potentially reduce that backward flow to create more space for flow going from u to v.

Oh, I see.

So the residual network considers both how much more we can add in the original direction and how much we can potentially undo in the opposite direction.

Exactly.

And if there's no original edge between two vertices and no flow going in the opposite direction, the residual capacity is just zero.

Okay.

That makes sense.

So this residual network, gwlbgbi is like a dynamic map that's constantly changing based on the current flow, showing all the possibilities for increasing it.

You got it.

And now an augmenting path is simply a path in this residual network key dollars that goes from the source s to the sink t.

Okay.

A path through the residual network where we still have capacity to add more flow.

Precisely.

Now, since every edge on this path has a positive residual capacity, it means we can push some more flow along this entire path.

All right.

But how much more?

There got to be a limit, right?

Right.

Good point.

The amount of flow we can add along this path is limited by the edge with the smallest residual capacity.

We call this the residual capacity of the augmenting path written as sacfp, where p is the path.

It's like the bottleneck of the path.

Okay.

So the weakest link makes sense.

So we found this path and the maximum we can add along it.

What's the next step?

Now we actually augment the flow.

So we take that residual capacity of the path, sacps, and for every edge on the path that's in the same direction as the original network, we increase the flow on that edge by sacps.

And for any edge on the path that's in the opposite direction of the original network, we decrease the flow by sacps.

So we're pushing more flow in the right direction and maybe taking some back from the opposite direction, all based on that bottleneck value.

Exactly.

And that gives us a new flow in the original network with a higher total flow value.

Then we do it all again.

We recalculate the residual network based on this new flow and look for another augmenting path.

We keep doing this iterating until - Until we can't find any more augmenting paths.

And then we know we've reached the maximum flow.

You got it.

That's when the Ford -Fulkerson method stops, when there are no more paths from s to t in the residual network.

But there's a bit of a caveat here.

If all the capacities in our network are integers, whole numbers, then we're guaranteed to eventually find the maximum flow and the algorithm will stop.

But the problem is the number of these iterations we have to go through could potentially be as a large as the value of the maximum flow itself.

Let's call that $5.

And each time we have to find a path and update the flows, it takes some time roughly proportional to the number of edges in the network.

So in the worst case, the total time Ford -Fulkerson might take is estaline.

Okay.

So if the maximum flow is huge, you could take a really long time.

Yeah.

And the thing is this maximum flow value might not be directly related to how complex the network itself is.

It could be a really simple network structure, but with huge flow capacities.

That's one of the reasons people develop more efficient algorithms to avoid this potential problem.

Okay.

So Ford -Fulkerson gives us the basic idea, but it has its limitations.

Yeah.

It seems like a good place to talk about cuts in flow networks.

Yeah.

What are those and how do they relate to finding the maximum flow?

All right.

So a cut in a flow network, we write it as E and E is essentially a way of dividing all the vertices in the network into two separate groups.

One group we call S the other T and the important rule is that the source as has to be in group S and the sink T has to be in group T.

So we're slicing the network into two source on one side, sink on the other.

How does this relate to the flow?

Well, we can talk about the net flow across this cut.

Yeah.

That's the total flow going from any vertex in S to any vertex in T minus any flow going back the other way from T back to S.

And we can write this mathematically as fun you F U F V.

Okay.

So we're measuring the flow crossing the boundary we created.

What's interesting about that?

Well, there's this really important result called Lemma 24 .4 that says for any flow we have in the network and any cut we make, the net flow across that cut will always be equal to the total value of the flow five dollars coming out of the source.

Wow.

So it doesn't matter how we slice it, the flow across that dividing line always matches the total flow from the source.

Exactly.

And from there we get something called corollary 24 .5.

This one says that the value of any flow ballers in the network will always be less than or equal to the capacity of any cut.

Okay.

So the flow is limited by the bottleneck of any cut we can make.

What do we mean by capacity of a cut though?

Ah, good point.

So the capacity of a cut written as 6S to 6S is the sum of the capacities of all the edges that go directly from a vertex in the S group to a vertex in the T group.

Only the forward direction counts here.

So what this corollary is telling us is that we can't have more flow than what the tightest cut will allow.

That's very intuitive.

The total amount we can push from source to sink can't be more than what the most restricted set of connections between them can handle.

This sounds like it's leading up to something important.

It is.

This leads us to one of the most fundamental theorems in the theory of flow networks, the max flow min -cut theorem.

Okay, let's hear it.

It's theorem 24 .6 in our material.

And it basically connects these two ideas, the maximum flow and the minimum cut, in a really beautiful way.

It says that these three things are all equivalent.

First, the flow F is a maximum flow.

Second, there are no more augmenting paths in the residual network.

And third, the value of the flow dollars is equal to the capacity of some cut in the network.

And not just any cut, but a cut with the minimum possible capacity.

So when we can't find any more ways to increase the flow, we haven't just reached the point where Ford -Fulkerson stops, but we've actually found the absolute maximum flow possible.

And that maximum flow is exactly equal to the capacity of the smallest bottleneck in the network, the minimum cut.

That's incredible.

It really is remarkable.

It means the maximum throughput of the whole system is fundamentally limited by its most restrictive point.

And this theorem gives us not only a way to find that maximum flow, but also a way to confirm we found it by checking if there's a cut whose capacity matches the flow value.

That's really powerful.

So Ford -Fulkerson gives us the idea, but it can be inefficient.

How do we improve on it?

This is where the Edmonds -Karp algorithm comes in.

Edmonds -Karp, okay.

Yeah, it's a specific implementation of Ford -Fulkerson, but with a key tweak.

Instead of just picking any augmenting path in the residual network, Edmonds -Karp always uses something called breadth -first search or BFS to find the shortest augmenting path.

Shortest in terms of number of edges.

Exactly.

So it's like trying to take the most direct routes first.

Okay.

So instead of potentially going on these long winding paths through the residual network to add flow, we try the straightest paths first.

That makes intuitive sense.

Does that actually make a big difference in performance?

It does, surprisingly.

There's something called Lemma 24 .7 that proves that when we always choose the shortest augmenting path, the distances between the source and all the other vertices in the residual network never decrease.

They either stay the same or get bigger.

And this seemingly small change leads to a much better bound on how many times we have to augment the flow.

Theorem 24 .8 shows that with Edmonds -Karp, the number of augmentations is at most $VE, where V is the number of vertices and E is the number of edges in the network.

Okay.

Much better than potentially being as large as the flow value itself.

Right.

And because each augmentation step using BFS and updating the flow takes about $1, the total running time for Edmonds -Karp becomes a VE2.

So it's a polynomial time algorithm.

That's a huge improvement over the potential non -polynomial time of Ford -Fulkerson, especially when we're dealing with large flow values.

Exactly.

Edmonds -Karp gives us a much more practical and efficient way to solve these problems.

Okay.

That's really cool.

So we've got a pretty good handle on flow networks, maximum flow, Ford -Fulkerson, Edmonds -Karp.

But you mentioned earlier that these ideas can be applied to other things, not just physical flows.

Can you give us an example?

Of course.

One really neat example is using flow networks to solve the maximum bipartite matching problem.

Bipartite matching.

That doesn't sound like it has anything to do with flows at first glance.

It might not, but the connection is actually quite elegant.

So first, a quick reminder.

A bipartite graph is a special kind of graph where you can divide all the vertices into two groups.

Let's call them L and R so that every edge in the graph connects a vertex from group L to a vertex from group R.

No connections within the same group.

Okay.

So two distinct sets of things and connections only between them.

What's matching in this context?

A matching in a bipartite graph is a set of edges where no two edges share a common vertex.

So it's like pairing things up from the two groups, one to one.

And the maximum bipartite matching problem is finding the largest possible matching, the way to pair up the most things from these two groups.

Okay.

Like if you have a bunch of people and a bunch of jobs and you're trying to assign as many people to jobs as possible with each person getting at most one job and each job taken by at most one person.

That's a great example.

So how do we connect this to flow networks?

Well, we can construct a flow network from any bipartite graph.

Okay.

Tell me how.

All right.

So let's say our bipartite graph is called D dollars with the vertices divided into sets L and R and edges connecting them.

So DL dollar V equals L cup RE.

To create a flow network from this, we first add a new source vertex and connect it to every vertex in group L with an edge, each with a capacity of one.

Okay.

So all the things in L get a connection from the source with capacity one.

Exactly.

Then for every original edge that exists in the bipartite graph, connecting something in L to something in R, we make that a directed edge in our flow network going from L to R and we give each of those edges a capacity of one as well.

Okay.

So the original connections now have direction and a capacity of one.

Yep.

Finally, we add a sync vertex T and connect every vertex in group R to it with an edge, again, each with capacity one.

So now we've got a flow network where everything in L can flow through the original connections to R and then everything in R can flow to the sync.

Exactly.

And the brilliant part is there's this lemma, lemma 24 .9 that says there's a one -to -one correspondence between matchings in the original bipartite graph and integer flows in this new flow network we've built.

What does that mean exactly?

It means that any matching we find in the bipartite graph directly corresponds to a flow in the network where all the flow values are whole numbers and the value of that flow, five dollars, is exactly equal to the number of edges in the matching.

And the other way around is true too.

Any integer flow in the network corresponds to a matching with the same number of edges.

Okay.

So the number of pairings in the matching is equal to the total flow value.

Precisely.

And now comes the really important part.

Remember the Integrality Theorem we talked about earlier, Term 24 .0?

It guarantees that if all the capacities in a flow network are integers, then the maximum flow that algorithms like Fort Fulkerson or Edmund's Carp find will also have integer values on all the edges.

Right.

So we're not going to get fractions of flow on any edge.

It's either one or zero.

Exactly.

And since all our capacities are one in this network we built, the maximum flow we find will have a flow of one on some edges and O on others.

And those edges with a flow of one, those directly correspond to the edges that are part of the maximum matching in the original bipartite graph.

Oh, I see.

So by finding the maximum flow, we're essentially figuring out which connections to activate to get the most pairings.

You got it.

Corollary 24 .11 summarizes this beautifully.

It says the size of the maximum matching in a bipartite graph is exactly equal to the value of the maximum flow in this flow network we constructed.

And because we have efficient algorithms like Edmund's Carp to find that maximum flow, we get an efficient algorithm for maximum bipartite matching as well.

It runs an EVE time.

Wow, that's a really cool application.

Who would have thought flow networks could be used for that?

It really shows how powerful these concepts are.

Now, I know the material we have also includes a glossary of terms.

Maybe we can go through some of the key definitions just to make sure everything is crystal clear for our listeners.

That's a great idea.

Sometimes it's helpful to revisit the key terms.

Okay, so augmenting path.

That's the path we find in the residual network to increase the flow.

Capacity is the maximum flow allowed on an edge.

We have capacity constraint and flow conservation, the two fundamental rules.

Right, those are crucial.

And then we have cuts, which are those ways of dividing the network.

The Edmund's Carp algorithm is our efficient way of finding the maximum flow.

Flow itself is the movement through the network and the flow network is the model itself.

Ford -Fulkerson method is the general approach to finding the maximum flow.

Integrality theorem assures us that if capacities are integers, then the maximum flow values will also be integers.

Yeah, that's a big one for certain applications like the bipartite matching we just discussed.

And of course, maximum bipartite matching was our example of how flow networks can solve other problems.

Maximum flow problem is the core problem we're focusing on.

Max flow min -cut theorem links the maximum flow to the capacity of the minimum cut.

And then residual capacity is the remaining capacity on an edge.

And the residual network shows us all the places where we can potentially add more flow.

And finally, the sink and source are our starting and ending points.

And the value of a flow is the total amount we're moving from source to sink.

Great summary.

Having a solid grasp of these terms really helps understand the whole subject.

All right.

So to wrap things up,

in this deep dive, we've really explored this whole world of flow networks in depth.

We talked about what a flow network is, the maximum flow problem, the idea of augmenting paths and residual networks, that amazing max flow min -cut theorem, and how the Edmonds -Karp algorithm gives us a practical way to solve these problems.

And we even saw how it can be applied to things like bipartite matching, which might seem totally unrelated at first.

Yeah, I thought that was really cool.

So as you go about your day, think about where these ideas might pop up.

Where are those bottlenecks in different systems, whether it's physical flow, information flow, anything?

And how might changing those capacities affect the overall performance?

It's a really useful way of thinking about all sorts of problems.

It really is.

It encourages you to look for those constraints and think about how they impact the whole system.

And with that, I think we've covered everything from this chapter on maximum flow problems and algorithms.

Thanks for joining us on the deep dive, and we'll see you next time.

See you next time.

Bye.

Bye.