Coupe-cycles de sommets
De Wikipedia, l'encyclopédie encyclopedia
En théorie des graphes, un coupe-cycles de sommets, ou feedback vertex set en anglais[1], est un ensemble de sommets d'un graphe, tel que le retrait de ces nœuds laisse le graphe acyclique. Autrement dit, c'est un ensemble de nœuds ayant une intersection non nulle avec chaque cycle.
Le problème du coupe-cycle de sommets, est un problème algorithmique d'optimisation combinatoire, qui consiste à trouver un coupe-cycles de sommets de taille minimum.