Flow network

A directed graph whose edges have capacities, used to model how a quantity moves from a source to a sink.

Flow: An assignment of nonnegative quantities to a directed network’s edges, respecting capacity limits and conservation at intermediate vertices. A feasible flow is the quantity assigned to each edge of this network.
Directed graph: A graph whose edges have orientations, specifying which direction each connection permits movement. Every network edge specifies a permitted direction for flow.
Maximum flow problem: The optimization problem of finding the greatest feasible flow from a specified source to a sink. It asks for the network’s maximum possible source-to-sink throughput.
Minimum-cost flow problem: A flow optimization problem that minimizes edge costs while meeting specified supplies, demands, or flow amounts. Unlike plain maximum flow, it optimizes cost as well as feasibility.
Flow conservation: A rule requiring total inflow to equal total outflow at every vertex except designated sources and sinks. It prevents quantities from accumulating or disappearing at intermediate vertices.
Graph (discrete mathematics): A mathematical structure consisting of vertices connected by edges. The network is a graph with added directions and capacity limits.
Bipartite matching: A set of edges in a bipartite graph with no shared endpoints. A flow construction can find the largest compatible assignment.
Multi-commodity flow problem: A network optimization problem routing several distinct flows through shared capacity-constrained edges. Separate commodities compete for capacities that a single-flow model treats collectively.
Residual graph: A graph encoding remaining capacity for increasing or reversing flow along edges. It reveals which changes can increase the current flow.
Capacity (network flow): An upper bound on the amount of flow allowed through an edge. Edge capacities set the network’s transmission limits.

Linked from 9 pages