Flow network

<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a flow network (also known as a transportation network) is a <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a> 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 <a href="/facts/Operations_research/H5yJkV5n">operations research</a>, 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, <a href="/facts/Image_segmentation/jofAhbxa">image segmentation</a>, and the <a href="/facts/Matching_(graph_theory)/s0pUJ7hd">matching problem</a>.
</p>

Flow network open-in-new

Flow network