Notes by mraabo

Flow Networks

A flow network G = (V,E) is a directed graph with the following properties:

  • Each edge (u,v) \in E has a nonnegative capacity c(u,v) \geq 0.
  • If E contains an edge (u,v) then there is no edge (v,u) in the reverse direction.
  • No self-loops.
  • If (u,v) \notin E) then we define =c(u,v) = 0.
  • Two distinguished vertices: a source s and a sink t, which has a path for which each other vertex lies.

The point of such a network is to model flow from s to t. A such flow in G is a real-valued function f : V \times V \rightarrow R that satisfies the following two properties:

  • Capacity constraint: For all u,v \in V, we require 0 \leq f(u,v) \leq c(u,v).
  • Flow conservation: For all u \in V - {s,t}, we require

The value |f| of a flow f is defined as

Alterations

Anti-parallel edges

If we have an edge that violates the property that if (v_1, v_2) \in E then (v_2, v_1) \notin E then we call the two edges (v_1, v_2) and (v_2, v1) antiparallel. We can rewrite such edges to attain an equivalent network that conforms to our properties of a flow network. This is done by choosing one of the antiparallel edges, in this case (v_1, v_2), and splitting it by adding a new vertex v' and replacing edge (v_1, v_2) with the pair of edges (v_1, v') and (v', v2). Finally we set the capacities of the new edges equal to the replaced edge c(v_1, v_2) = c(v_1, v') = (v', v2).

Multiple sources and sinks

We can convert networks with multiple sources {s_1, s_2, ..., s_m} and sinks {t_1, t_2, ..., t_n} to a flow network only a single source and sink. This is done by adding a supersource s and a directed edge (s, s_i) with capacity c(s, s_i) = \infty for each i = 1,2,...,m. We also add a supersink t and a directed edge (t_i, t) with capacity c(t_i, t) = \infty for each i = 1,2,...,n. An illustration can be seen in examples.

Examples

Flow network with notated f(u,v)/c(u,v)

Altering a multiple-source multiple-sink network (a) to an ordinary flow network (b)

Graph View

Backlinks