Introduction to Network Flows
Welcome to the world of Network Flows! This chapter is all about moving "stuff"—whether that's water in pipes, data on the internet, or cars on a road—from one place to another as efficiently as possible. If you’ve ever wondered how a city manages its traffic or how Netflix streams movies to millions of people at once without the system crashing, you’re already thinking about network flows.
Don’t worry if this seems a bit abstract at first. We’ll break it down into simple steps, using plenty of analogies to help you visualize what's happening. By the end of this, you'll be a pro at finding the "bottlenecks" in any system!
1. The Basics: Nodes, Arcs, and Capacity
Before we start flowing, we need to know the parts of our map. In discrete mathematics, we call this map a network (or a directed graph).
Nodes (or Vertices): These are the circles or points. Think of them as junctions or cities.
Arcs (or Edges): These are the lines connecting the nodes. In this chapter, they always have arrows, making them directed arcs. Think of them as one-way streets.
Source (S): This is where the flow starts. Think of it as the "Water Tower" or "Factory."
Sink (T): This is where the flow ends. Think of it as the "House" or "Customer."
Capacity: Every arc has a limit. This is the maximum amount of "stuff" that can flow through it. We usually write this number next to the arc.
The Golden Rule: Conservation of Flow
For every node except the Source and the Sink, the amount of flow entering the node must equal the amount of flow leaving it. You can't just lose water in the middle of a pipe system!
Quick Review: Key Terms
Source (S): The start point.
Sink (T): The end point.
Capacity: The max limit of an arc.
Flow: The actual amount currently moving through an arc (Flow \( \le \) Capacity).
2. Understanding Cuts
Imagine you wanted to completely stop the flow from the Source to the Sink by "cutting" through some pipes. A cut is a line that partitions the nodes into two sets: one set containing the Source and the other containing the Sink.
The Value of a Cut:
The value of a cut is the sum of the capacities of all the arcs that go from the Source side to the Sink side.
Important: If an arc goes "backwards" (from the Sink side back to the Source side), we ignore its capacity when calculating the cut value. We only care about what’s trying to get across the "gap" toward the finish line.
Did you know?
The value of any cut is always greater than or equal to the value of the actual flow. If you can find a cut with a value of 50, you know for sure that your flow cannot possibly be higher than 50.
3. The Maximum Flow-Minimum Cut Theorem
This is the most important theorem in the chapter. It states that in any network:
\( \text{Maximum Flow} = \text{Value of the Minimum Cut} \)
Analogy: The Chain and the Weakest Link
Think of a network like a series of chains. The maximum weight the whole system can hold is determined by the weakest link. The "Minimum Cut" is simply the mathematical way of finding the ultimate bottleneck in the entire network.
Key Takeaway
If you are asked to prove that a flow is the maximum flow, find a cut that has a value equal to that flow. If they match, you've found the limit!
4. Supersources and Supersinks
Sometimes a problem has multiple factories (sources) or multiple customers (sinks). This looks messy, but there is a clever trick to fix it: Supersources and Supersinks.
1. Create one single "Super" node.
2. Connect it to all the original sources (or sinks) using arcs with infinite capacity (or a capacity equal to the total supply/demand).
3. Now you can treat the problem like a standard network with just one start and one end.
5. Augmenting Flows: How to reach the Max
To find the maximum flow, we use a process called augmenting. This just means "adding to."
Step-by-Step Guide:
1. Start with a flow of zero.
2. Find a path from S to T that has some spare capacity on every arc.
3. Find the bottleneck on that path (the arc with the smallest remaining capacity). Let's call this value \( x \).
4. Increase the flow along every arc on that path by \( x \).
5. Repeat this process until there are no more paths with spare capacity from S to T.
Common Mistake: Don't forget to update the remaining capacities as you go! If a pipe has a capacity of 10 and you send 4 units through it, it only has 6 left for future paths.
6. Advanced Constraints: Upper and Lower Capacities
In the real world, things get a bit more complicated.
Upper Capacities: This is what we've been using—the maximum limit.
Lower Capacities: Sometimes an arc must carry at least a certain amount of flow. For example, a power plant might need to send a minimum amount of electricity to keep a substation running.
To solve these, we check if a "feasible flow" exists that satisfies both the minimum requirements and the maximum limits. If you're struggling with this, think of it as "pre-loading" the pipes with the minimum required amount before you start looking for extra space.
7. Node Capacities
What if the junction itself is the bottleneck? Imagine a train station that can only handle 500 passengers an hour, even if the tracks leading into it can hold 1,000.
The Trick: Node Splitting
To model a node with a capacity, we "split" the node into two nodes connected by a single arc.
1. Turn Node A into Node A-in and Node A-out.
2. All arcs entering A now enter A-in.
3. All arcs leaving A now leave A-out.
4. Create a new arc from A-in to A-out and give it the capacity of the node.
Now, the node's limit is just another arc capacity that we can solve using our standard methods!
Quick Review: Common Pitfalls
- Direction matters: Only count capacities in a cut if they go from the Source side to the Sink side.
- Bottlenecks: The flow through a path is limited by its weakest arc, not the sum of its arcs.
- Conservation: Always check that Flow In = Flow Out for your final answer nodes.
Chapter Summary
Network flow is a powerful tool for solving optimisation problems. You’ve learned how to represent systems using directed arcs, how to identify bottlenecks using cuts, and how to use the Max-Flow Min-Cut Theorem to prove you've found the best possible solution. Whether you’re dealing with supersources or restricted node capacities, the core principle remains the same: keep the flow moving until you hit a limit!