Processing math: 100%

$\newcommand{\eps}{\varepsilon} \newcommand{\RR}{\mathbb{R}} \newcommand{\rd}{\operatorname{d}} \newcommand{\set}[1]{\left\{#1\right\}}$

Étiquette : vertex cover

Le problème de la couverture par sommet

Auteur de la publication Par Xavier BADIN de MONTJOYE
Date de publication 26 décembre 2021
Catégories Dans Complexité, Exercices
Aucun commentaire sur Le problème de la couverture par sommet

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, […]