Flow network

Network_Flow_Cropped2_-_revised

Network_flow_residual_PNG

A flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Typically, a flow network has a single source node, where the flow originates, and a single sink node, where the flow is consumed.

Components of a Flow Network

• Vertices: The nodes in the graph.
• Edges: The directed connections between the vertices.
• Capacity: A non-negative number associated with each edge, representing the maximum amount of flow that can pass through the edge.
• Flow: A function that assigns a non-negative number to each edge, representing the amount of flow passing through the edge.

Properties

• The flow into a vertex is equal to the flow out of the vertex, except for the source and the sink.
• The flow on an edge cannot exceed the capacity of the edge.

Applications

Flow networks are used in various fields such as:

• Transportation network
• Telecommunication network
• Water supply network
• Electrical grid

Algorithms

Several algorithms are used to find the maximum flow in a flow network:

• Ford-Fulkerson algorithm
• Edmonds-Karp algorithm
• Dinic's algorithm
• Push-relabel algorithm

Related Concepts

• Residual network
• Cut (graph theory)
• Max-flow min-cut theorem
• Circulation (graph theory)

See Also

• Graph theory
• Network flow problem
• Bipartite graph
• Matching (graph theory)