Exemple

Figure 3.27: Problème de flot

Comme la coupe contient les sommets

$$\begin{eqnarray*} \mathcal{C} & = & \{s\} \cup (A \cap \mathcal{C}) \cup (B \cap... ...{C} & = & \{(b_{2}, 1), (b_{2}, 2), (b_{2}, 3), (b_{2}, 4)\} \\ \end{eqnarray*}$$

Alors

$$\begin{eqnarray*} A \cap \overline{\mathcal{C}} & = & \emptyset \\ B \cap \math... ...emptyset \cup \{(b_{2}, 1), (b_{2}, 2), (b_{2}, 3), (b_{2}, 4)\} \end{eqnarray*}$$

On en déduit que

$$\{(b_{2}, 1), (b_{2}, 2), (b_{2}, 3), (b_{2}, 4)\}$$

est une couverture de poids minimal de $X$. Les valeurs à attribuer aux buffers dans ce cas sont :

$$\Delta(b_{1}) = \Delta^{0}(b_{1}) = 1\ et\ \Delta(b_{2}) = \Delta^{4}(b_{2}) = 5$$