No history yet

Introduction to Network Flow

What is a Flow Network?

Think about the water pipes in a city. Water enters from a treatment plant, flows through a series of pipes and junctions, and ends up at your kitchen sink. This system is a type of network designed to move something from a starting point to a destination. In computer science and mathematics, we call this a flow network.

A flow network is a directed graph where each edge has a capacity, and each edge receives a flow. It's a way to model problems involving the movement of goods, information, or any other resource. These networks have a few key components.

Let's break down this example. Every flow network has a source, labeled 's', which is where the flow originates. It also has a sink, labeled 't', which is the final destination. The points in between, 'a' and 'b', are just intermediate nodes or junctions.

The connections between the nodes are called edges. Notice the arrows? They show that flow is directional, like a one-way street. Flow can go from 's' to 'a', but not from 'a' to 's'.

Capacity and Flow

Each edge in the network has a capacity, which is the maximum amount of stuff that can pass through it. If an edge is a pipe, its capacity is the maximum amount of water that can flow through it per second. If it's a road, capacity might be the number of cars that can pass per hour.

The actual amount of stuff moving through an edge is called the flow. A crucial rule is that the flow along an edge can never exceed its capacity. You can't send 10 gallons of water through a pipe that can only handle 8.

Lesson image

In the image above, each edge is labeled with a fraction, like 1/2. The first number is the current flow, and the second is the total capacity. So, 1/2 means there is a flow of 1 unit through an edge that has a maximum capacity of 2 units.

The Rule of Conservation

There's one more fundamental rule in flow networks: the conservation of flow. For any node in the network that isn't the source or the sink, the total amount of flow entering the node must equal the total amount of flow leaving it.

Total flow in = Total flow out

Think of the junctions in our water pipe system. Water doesn't magically appear or disappear at a junction. Whatever flows in from one set of pipes must flow out through another. The only exceptions are the source, which produces flow, and the sink, which consumes it.

Let's check node 'a' in the image. The edge from 's' to 'a' has a flow of 3, so 3 units are flowing in. The edges from 'a' to 'c' and 'a' to 'd' have flows of 1 and 2, respectively. That's a total of $1 + 2 = 3$ units flowing out. Since the inflow (3) equals the outflow (3), the conservation rule is satisfied at node 'a'.

These three concepts—the network structure, the capacity and flow constraints, and the conservation of flow—are the building blocks for solving complex problems. They can help find the most efficient way to route data through the internet, manage supply chains, or even schedule flights.

Quiz Questions 1/5

In a flow network, what is the fundamental rule regarding the relationship between an edge's flow and its capacity?

Quiz Questions 2/5

An intermediate node (not the source or sink) in a flow network has two incoming edges with flows of 3 and 5, and three outgoing edges with flows of 2, 4, and 2. Is the conservation of flow rule satisfied at this node?

With these basics, you can now start to see how resources move through all kinds of systems.