Flow network

Imagine water moving through many pipes.

Each pipe can only hold a certain amount. This is called its capacity. We call the start a source. We call the end a sink.

In a network, things move from one spot to another. Water or cars can follow a path. At every stop, the amount coming in must equal the amount going out. This keeps everything moving smoothly.

We can use math to find the most flow. This tells us the biggest amount we can move. It helps us plan roads or power lines. Math helps us solve these puzzles.

Imagine water moving through a web of pipes.

Each pipe has a limit. This limit is called its capacity. A flow network is a map of these paths. It shows how things move from a start to an end. We call the start a source. We call the end a sink.

In these networks, there are rules to follow. First, the flow cannot be more than the capacity. A pipe can only hold so much. Second, the flow must be balanced at every stop. We call these stops nodes. At any node, the amount coming in must equal the amount going out. This rule only changes at the source and the sink. This helps us model real things like traffic or electricity.

It even helps us study how energy moves in nature.

One big goal is to find the maximum flow. This is the most we can move from start to end. To find this, we look for an augmenting path. This is a path that still has room for more flow. If no paths have room, we have reached the maximum flow. This can be found using special math steps called algorithms.

Imagine a giant web of water pipes connecting different cities.

Each pipe has a certain size, which limits how much water can pass through it. In math, we call this limit the capacity. A flow network is a special map that shows these paths and their limits. We use these maps to understand how things move through a system. One point in the network is the source, where everything starts. Another point is the sink, where everything ends. This tool helps us study many real-world things like traffic or electricity.

To make the math work, the network must follow strict rules. First, the flow on any path cannot be higher than its capacity. You cannot push more water through a pipe than its size allows. Second, the flow must stay balanced at every middle stop, or node. The amount of flow entering a node must equal the amount leaving it. This is called the flow conservation constraint. The only exceptions are the source and the sink. The source produces the flow, and the sink consumes it.

Mathematicians have created many ways to solve these network puzzles. One famous method is the Ford-Fulkerson algorithm. This method looks for an augmenting path to increase the flow. An augmenting path is just a route from the source to the sink that still has room. We look for the bottleneck, which is the smallest available capacity on that path. We then push more flow through until no more augmenting paths exist. When there are no more paths with room, we have reached the maximum flow.

History shows us many clever ways to find these answers. In 1970, a mathematician named Dinic created a fast algorithm. In 1972, Edmonds and Karp found another way to solve the problem. Later, in 1988, Goldberg and Tarjan developed the push-relabel algorithm. These different methods help us solve problems in different amounts of time. Scientists even use these ideas to study how nutrients move in a food web. Robert Ulanowicz helped develop ways to study these natural networks.

Flow networks connect to many parts of our daily lives. They help engineers plan how electricity moves through a power grid. They can help airlines schedule their flights more efficiently. Even computer networks use these ideas to move data around the world. We can even use them to match people to jobs or tasks. By understanding these paths, we can make big systems work much better.

A flow network is a mathematical model used to study how units move through a system. In graph theory, it is a directed graph where every edge has a specific capacity. This capacity represents the maximum amount of flow an edge can carry. Each edge also receives a flow, which is the actual amount being moved. The amount of flow on any given edge can never exceed its capacity. These networks are essential in operations research for modeling complex movement. They help us understand how things like traffic, electricity, or fluids travel through a system of nodes and arcs.

To function correctly, a flow network must follow specific mathematical rules. The first is the capacity constraint, which ensures flow does not exceed edge limits. The second is the flow conservation constraint. This rule states that for every node in the network, the total incoming flow must equal the total outgoing flow. There are two important exceptions to this rule: the source and the sink. The source is a deficient node that produces flow. The sink is an active node that consumes flow. All other nodes are considered conserving nodes because they do not produce or consume units.

Mathematicians categorize different types of flow functions to describe these movements. A pseudo-flow is a function that satisfies two specific constraints. First, it follows skew symmetry, meaning the flow from one node to another is the negative of the flow in the opposite direction. Second, it must respect the capacity constraint. A pre-flow is a more specific type of pseudo-flow. In a pre-flow, the net flow entering a node must be non-negative, except at the source. Finally, a feasible flow, often called just a "flow," must satisfy flow conservation. This means the net flow at every node, except the source and the sink, is exactly zero.

Understanding the capacity of a network often requires looking at residual networks. A residual network shows the remaining available capacity on each edge. This is calculated as the difference between the edge's capacity and its current flow. This concept is central to the Ford-Fulkerson algorithm. This algorithm searches for an augmenting path, which is a route from the source to the sink with available capacity. Within an augmenting path, there is always a bottleneck. The bottleneck is the minimum residual capacity among all edges in that specific path. To augment the flow, you increase the flow along the path by the value of the bottleneck.

A network reaches its maximum flow when no more augmenting paths exist in the residual network. This state is also linked to the max-flow min-cut theorem. This theorem states that finding the maximum flow is equivalent to finding a cut of minimum capacity. A cut is a division of vertices that separates the source from the sink. If any augmenting path exists with a bottleneck greater than zero, the network is not yet at maximum flow. When the bottleneck value of all possible paths reaches zero, the maximum flow has been achieved.

History has provided several efficient algorithms to solve these complex problems. In 1970, Dinic developed a fast algorithm for finding maximum flow. In 1972, Edmonds and Karp introduced another method. In 1978, the MPM algorithm was created by Malhotra, Pramodh-Kumar, and Maheshwari. Later, in 1988, Goldberg and Tarjan developed the push-relabel algorithm. More recent advancements include work by James B. Orlin in 2013. In 2022, a group of researchers including Li Chen and Rasmus Kyng published further developments. These algorithms allow scientists to solve problems in polynomial time, making them practical for large-scale systems.

Flow networks have many practical applications across different scientific fields. In physics and engineering, they model fluids in pipes or currents in electrical circuits. This is similar to Kirchhoff's current law, where flow into a junction must equal flow out. In ecology, researchers like Robert Ulanowicz use these concepts to study food webs. They analyze how nutrients and energy flow between different organisms. Flow networks can also solve business problems, such as airline scheduling, bipartite matching, and the assignment problem. They even help in image segmentation and survey design, proving that these mathematical structures are vital to understanding the modern world.