A flow network is a directed graph where each edge has a capacity and is used to model the movement of some quantity (often referred to as "flow") through the network. It is a fundamental concept in combinatorial optimization and graph theory, widely used to represent various real-world systems involving transportation, communication, and resource allocation.
Components of a Flow Network
A typical flow network consists of the following elements:
- Directed Graph (G = (V, E)): A set of vertices (or nodes) V and a set of directed edges (or arcs) E connecting pairs of vertices.
- Source (s ∈ V): A designated vertex from which all flow originates. It has only outgoing edges in the conceptual model of flow.
- Sink (t ∈ V): A designated vertex where all flow terminates. It has only incoming edges.
- Capacity (c(u,v)): Every edge (u,v) ∈ E has a non-negative capacity, denoted c(u,v), which represents the maximum amount of flow that can pass through that edge. If an edge does not exist, its capacity is considered zero.
- Flow (f(u,v)): For each edge (u,v) ∈ E, there is a non-negative flow, denoted f(u,v), representing the actual amount of quantity passing through that edge.
Properties and Constraints of Flow
The flow within a network must adhere to the following properties:
- Capacity Constraint: For every edge (u,v) ∈ E, the flow f(u,v) cannot exceed its capacity c(u,v). That is, 0 ≤ f(u,v) ≤ c(u,v).
- Flow Conservation (or Kirchhoff's Current Law): For every vertex v ∈ V that is neither the source nor the sink, the total flow entering the vertex must be equal to the total flow leaving it. Mathematically, for v ≠ s, t: $$ \sum_{(u,v) \in E} f(u,v) = \sum_{(v,w) \in E} f(v,w) $$ This means that no flow is created or destroyed at any intermediate node.
- Skew Symmetry (often used in residual graphs): While not strictly a property of the flow itself in the initial definition, in algorithms like Edmonds-Karp or Dinic's, it's often convenient to define flow such that f(u,v) = -f(v,u). This facilitates modeling "reverse" flow in a residual graph, which effectively means canceling out some flow on an edge.
The total flow of the network is defined as the net flow out of the source (or equivalently, the net flow into the sink).
Related Concepts and Problems
Flow networks are central to several fundamental algorithmic problems:
- Maximum Flow Problem: The most common problem, aiming to find the maximum possible total flow from the source to the sink while respecting all capacity and conservation constraints.
- Minimum Cut Problem: Closely related to the max-flow problem, it seeks to find a set of edges whose removal disconnects the source from the sink, and the sum of whose capacities is minimized. The Max-flow Min-cut Theorem states that the maximum flow through a network is equal to the capacity of a minimum s-t cut.
- Residual Graph: A concept used in max-flow algorithms, representing the remaining capacity on edges for potential flow augmentation. It includes both forward and backward edges.
- Augmenting Path: A path from the source to the sink in the residual graph along which additional flow can be sent.
- Minimum Cost Flow Problem: An extension where each edge also has an associated cost per unit of flow, and the goal is to find a flow of a given amount with the minimum total cost.
- Multi-commodity Flow Problem: Deals with multiple types of flow (commodities) originating from and terminating at different source-sink pairs, each with its own demand, sharing the same network capacities.
Applications
Flow networks have a wide range of applications in various fields:
- Transportation and Logistics: Modeling traffic flow in road networks, material flow in supply chains, pipeline networks for oil or gas, and data packet routing in computer networks.
- Project Scheduling: Representing tasks and dependencies, where flow can signify progress or resources.
- Bipartite Matching: Finding a maximum matching in a bipartite graph can be formulated as a maximum flow problem.
- Image Segmentation: Algorithms like graph cuts use flow networks to divide an image into foreground and background regions.
- Circulation Problems: Where flow must satisfy conservation at all nodes, and there might be lower bounds on edge flows.
- Network Reliability and Vulnerability Analysis: Assessing how much flow a network can sustain under edge failures.