information:extraction
Definition

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.