Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Flow network
Summary
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 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.
A network is a directed graph G = (V, E) with a non-negative capacity function c for each edge, and without multiple arcs (i.e. edges with the same source and target nodes). Without loss of generality, we may assume that if (u, v) ∈ E, then (v, u) is also a member of E. Additionally, if (v, u) ∉ E then we may add (v, u) to E and then set the c(v, u) = 0.
If two nodes in G are distinguished – one as the source s and the other as the sink t – then (G, c, s, t) is called a flow network.
Flow functions model the net flow of units between pairs of nodes, and are useful when asking questions such as what is the maximum number of units that can be transferred from the source node s to the sink node t? The amount of flow between two nodes is used to represent the net amount of units being transferred from one node to the other.
The excess function xf : V → represents the net flow entering a given node u (i.e. the sum of the flows entering u) and is defined byA node u is said to be active if xf (u) > 0 (i.e. the node u consumes flow), deficient if xf (u) < 0 (i.e. the node u produces flow), or conserving if xf (u) = 0. In flow networks, the source s is deficient, and the sink t is active.
Pseudo-flows, feasible flows, and pre-flows are all examples of flow functions.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.