Transformation

La transformation se fait comme suit :

• $\mathcal{V} = A \cup B \cup \{s, t\}$;
• $\mathcal{E}^{\prime} = E \cup \{ (s, i) \mid i \in A\} \cup \{ (i, t) \mid i \in B\}$;
• $c(i, j) =$ $\left \lbrace \begin{array}{l} +\infty \quad si (i, j) \in E \\ v(j) \quad si\ i = s\\ v(i) \quad si\ j = t\\ \end{array} \right.$

Cela signifie que l'on conserve les mêmes sommets, mais :

• que l'on ajoute une source $s$ et un puits $t$;
• que l'on ajoute des arcs entre $s$ et $A$, et entre $B$ et $t$;
• que l'on définit comme capacité sur les arêtes ajoutées entre $s$ et $A$, et entre $B$ et $t$ les poids des sommets de $A \cup B$.

Un algorithme de flots va définir une coupe $C \subset \mathcal{V}$ à partir de laquelle nous allons récupérer la couverture de la façon suivante : soit $\mathcal{C}$ une coupe dans $G$, on a

$$\mathcal{C} = \{s\} \cup (A \cap \mathcal{C}) \cup (B \cap \mathcal{C})$$

On note $\overline{\mathcal{C}}$ le complémentaire de $\mathcal{C}$ définit ainsi :

$$\overline{\mathcal{C}} = \mathcal{V} \backslash \mathcal{C}$$

Une couverture $\Gamma$ peut se déduire de la coupe de la façon suivante :

$$\Gamma = (A \cap \overline{\mathcal{C}}) \cup (B \cap \mathcal{C})$$

La capacité de la coupe est égale au poids de la couverture[5]. Par conséquent, trouver la coupe minimale permet de trouver dans un deuxième temps une couverture de poids minimal.