Lesson 4

We will call a network a directed graph \(G = (V,E)\) with a distinguished source \(s\) and sink \(t\), and each edge \((u,v)\in E\) having a capacity \(c(u,v) > 0\). We assume that no edge enters \(s\) and no edge leaves \(t\).

We want to pump oil from \(s\) to \(t\) without exceeding the edge capacities. A supply scheme is called a flow: to specify it, for each edge \((u,v)\) we indicate a number \(f(u,v)\) (how much oil goes through it). Constraints:

1. Edge capacities must not be exceeded: \(0 \le f(u,v) \le c(u,v)\) for all \((u,v)\in E\).
2. For any vertex \(u\), except \(s\) and \(t\), incoming flow equals outgoing: \[\sum_{(w,u) \in E}f(w,u) = \sum_{(u,z)\in E}f(u,z).\]

   This property is usually called flow conservation.

Flow conservation guarantees that all oil leaving \(s\) reaches \(t\); its amount is called the value of the flow: \[\operatorname{size}(f) = \sum_{(s,u)\in E}f(s,u) = \sum_{(u,t) \in E}f(u,t).\]

Although the capacity and flow functions are defined only on the edges of the original network, it will be convenient to extend them to all pairs of distinct vertices and assume they are zero elsewhere.