Exercice Une couverture par sommet d’un graphe $G=(S,A)$ non orienté est un sous ensemble $W \subseteq S$ tel que pour chaque arrête $(u,v) \in A$ on a $u \in W$ ou $v \in W$. Le problème de décision de la couverture par sommet, appelé en anglais vertex cover et désigné par la suite par VC, […]