Editing Flow network (section)

{{Short description|Directed graph where edges have a capacity}}
In [[graph theory]], a '''flow network''' (also known as a '''transportation 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. Often in [[operations research]], a directed graph is called a '''network''', the vertices are called '''nodes''' and the edges are called '''arcs'''.  A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a '''source''', which has only outgoing flow, or '''sink''', which has only incoming flow. A flow network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes. As such, efficient algorithms for solving network flows can also be applied to solve problems that can be reduced to a flow network, including survey design, airline scheduling, [[image segmentation]], and the [[Matching (graph theory)|matching problem]].
[[File:Network Flow Cropped2 - revised.png|thumb|332x332px|Sample Figure: A flow network showing flow and capacity]]