Lesson 3

This problem can be solved using flows as follows. We convert the graph \(G(V,E)\) into a network \(G'\).

1. Add a source \(s\) and a sink \(t\).
2. For each pixel \(i\), add an edge \((s,i)\) with capacity \(f_{i}\) and an edge \((i,t)\) with capacity \(b_{i}\).
3. Replace each edge \(\{i,j\}\) with a pair of directed edges \((i,j)\) and \((j,i)\) with capacity \(p_{ij}\).