Exemple

Le graphe 3.25 est associé à l'instance ci-dessous.

$\left\lbrace\begin{array}{l} \mathcal{T} = \{T_{1}, T_{2}\}\\ \mathcal{B} = \{... ...edge ((\Delta(b_{2}) \geq 2) \vee (\Delta(b_{1}) \geq 4))\\ \end{array}\right.$

Figure 3.25: Instance du problème de la couverture de poids minimal d'un graphe biparti

En pratique, on parcours toutes les clauses, et on y trace les arêtes associées. Par exemple, la clause $(\Delta (b_{1}) \geq 4) \vee (\Delta (b_{2}) \geq 3)$ nous donne le graphe partiel de la figure 3.26.

Figure 3.26: Graphe partiel associé à $(\Delta (b_{1}) \geq 4) \vee (\Delta (b_{2}) \geq 3)$