Couverture

Soit $G = (S, A)$ un graphe non orienté muni d'une pondération $p$ un sous-ensemble $K$ de $S$ est une couverture si

$$\forall a = (e, e^\prime) \in A, e \in K\ ou\ e^\prime \in K$$

Le poids de cette couverture est

$$\sum_{s \in K} p(s)$$

Le problème de la couverture minimale est défini comme suit :

• données : un graphe $G$, une pondération $p$
• question : trouver le sous-ensemble $K$ de poids minimal parmi les couvertures de $G$.

Ce problème est NP-Complet dans le cas général, polynomial si le graphe est un arbre ou est biparti.