A flow network is a directed and weighted graph used to model the movement of resources through a system of interconnected nodes. It consists of a directed graph with nodes representing points in the system and edges representing pathways along which resources can flow. Each edge has a capacity that determines the maximum amount of flow it can handle. Flow networks are generally used to find the maximum amount of flow between two nodes and are crucial in solving various optimization problems, with wide-ranging applications in real-world scenarios.
One of the most common applications of flow networks is in transportation systems. For example, a road network can be modeled as a flow network, with intersections as nodes and roads as edges. The capacity of each road represents the maximum number of vehicles it can handle. This model helps urban planners optimize traffic flow and identify potential bottlenecks. Similarly, flow networks are used in communication systems to manage data transmission, ensuring efficient routing of information through networks of servers and communication channels.
Representation of Flow Networks
A Flow Network is typically represented as a directed graph G = (V, E), where V is the set of vertices (nodes) and E is the set of edges (arcs) connecting these vertices. This graph structure allows us to model the flow of resources, such as water, electricity, or data, from one point to another within a network. Below is how the representation looks like:
Let’s now take a look at how each component of the Flow network is mapped to the undirected graph represented above:
-
Source Vertex (
s): This vertex represents the starting point (source) of the flow, where more flow exits the node than enters. -
Sink Vertex (
t): This is another special vertex that represents the destination of the flow, where more flow enters the node than exits. -
Intermediate nodes (
v1,v2,v3,v4): Intermediate nodes are the regular vertices within the flow network, where the amount of incoming flow must equal the amount of outgoing flow. These nodes help in routing the flow from the source to the sink while satisfying capacity constraints on the edges. -
Edges: These are the directed connections between vertices, representing the paths through which resources can flow. Each edge
(u, v)has two important attributes:- Capacity
c(u, v): A non-negative number which represents the maximum amount of flow that can pass through the edge. - Flow
f(u, v): The actual amount of flow actually passing through the edge, which must be non-negative and cannot exceed the capacity.
- Capacity
Below is how the flow network looks like after labeling the Capacity of each edge with some flow along each edge:
Between source vertex s and an intermediate node v1, the edge is represented by 12/16. Here 16 represents the flow capacity of the edge i.e., the maximum possible flow between nodes s and v1. Whereas the number 12 represents the actual flow through the edge.
Practically Relating to Flow Networks
You can practically relate to each term used in the representation of flow networks by taking an example involving road transportation networks:
-
Source and sink nodes: In a road network, we can think of the source node as the starting point of a journey, such as your home or a major transportation hub like an airport. The sink node would be your final destination, like your workplace or a popular tourist attraction. Just as all flow originates from the source in a flow network, all traffic begins at these starting points in a road network. In the illustration shown above, you can consider
CITY-Aas the source node andCITY-Bas the destination/sink node. -
Edge Capacities: In a flow network, edges have capacities that limit the amount of flow. In a road network, this is analogous to the maximum number of vehicles a road can handle. For example, a small residential street might have a low capacity, allowing only a few cars to pass through comfortably. In contrast, a multi-lane highway would have a much higher capacity, able to accommodate a large volume of traffic.
-
Flow Conservation: Flow conservation in a flow network states that the amount of flow entering a node must equal the amount leaving it (except for source and sink nodes). In a road network, this principle applies to intersections. The number of vehicles entering an intersection from various roads should roughly equal the number of vehicles leaving it through other roads. This ensures that traffic doesn’t mysteriously appear or disappear at intersections.
-
Maximum Flow: In flow networks, we often try to maximize the flow from source to sink. Similarly, in road networks, traffic engineers aim to optimize the flow of vehicles to reduce congestion and minimize travel times. This might involve adjusting traffic light timings, creating one-way streets, or building new roads to increase the overall capacity of the network and allow more vehicles to reach their destinations efficiently.
Operations on Flow Networks
Finding Maximum Flow
Finding Maximum Flow in a Flow network (also known as Max-Flow problem) involves finding the maximum amount of flow that can be pushed through a network from a source node to a sink node, while respecting the capacity constraints on each edge.
For example, in the Flow network shown below, the maximum flow which can pass from source node to the sink node is 23:
Notice that even though the capacity of some of the edges is not utilized fully, the overall flow between source and sink nodes cannot be increased further as the capacities of other edges in the flow path are fully utilized.
Below are some of the algorithms designed to find the maximum possible flow through a Flow network:
- Ford-Fulkerson Algorithm: This is one of the earliest and most well-known algorithms. It works by repeatedly finding augmenting paths from source to sink and pushing flow along these paths until no more augmenting paths exist.
- Edmonds-Karp Algorithm: This is an implementation of Ford-Fulkerson that uses breadth-first search to find augmenting paths.
- Dinic’s Algorithm: An improvement over Edmonds-Karp, Dinic’s algorithm uses the concept of level graphs and blocking flows to achieve better performance.
- Push-Relabel Algorithm: This algorithm takes a different approach by working with preflows instead of flows and uses local operations to move flow through the network.
Finding Minimum Cut
A cut in a flow network involves removal of certain edges in the graph such that the source node and the sink node are separated from each other. In other words, a cut in a Flow network partitions all the nodes into two disjoint sets, with the source node in one set and the sink node in the other. The capacity of a cut is the sum of the capacities of the edges that are removed as part of the cut.
For example, in the Network Flow graph shown below, removing edges v1->v3, v3->v2, v2->v4 constitute a cut which separates out the source and sink nodes. So after this cut is made (edges are removed), no flow can be made between source and destination nodes.
The capacity of the cut made in the graph shown above is equal to the sum of capacities of all the edges removed which is 12+9+14=35. The minimum cut problem aims to find the cut with the smallest capacity.
Max-Flow Min-Cut theorem
The max-flow min-cut theorem defines relation between max-flow problem and min-cut problem discussed before. The theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut. This means that the maximum amount of flow that can be sent from the source to the sink is limited by the capacity of the minimum cut. This theorem has profound implications for network analysis and optimization. It establishes that the max-flow and min-cut problems are dual to each other, meaning that solving one automatically solves the other.
For example, in the Network Flow graph shown below, removing the edges v1->v3, v4->v3 and v4->t will create a minimum cut. And according to the theorem, the minimum cut capacity is the maximum flow which can flow from source node to sink node. This comes out to be weight of edges E(v1,v3), E(v4,v3), E(v4,t) which is 12+7+4=23.
Notice that the minimum cut need not physically disconnect all the nodes. As long as the flow is not possible between source and sink nodes, it can be considered as a cut in the graph. In the Flow network shown before, after the cut, even though the edge v3->v2 is present, it cannot cause any flow to happen between source and sink vertices.
Applications of Flow Networks
Network flow algorithms have a wide range of applications across various industries and problem domains. Below are some key areas where network flow algorithms have significant practical applications:
- Transportation and Logistics: Network flow algorithms optimize routes and minimize shipping costs and delivery times in supply chains.
- Communication Networks: Used to efficiently manage data traffic and network capacity, ensuring smooth internet connectivity with less maintenance costs.
- Energy Distribution: Optimize electricity routing in power grids, reducing power losses and ensuring a stable supply.
- Bipartite Matching Problems: Solve job assignment problems by matching applicants to positions based on skills and requirements.
- Project Scheduling: Optimize task sequences and resource allocation to minimize project completion times.
- Airline Scheduling: Optimize flight and crew scheduling, reducing costs and maximizing efficiency.