Loading AI tools
De Wikipédia, l'encyclopédie libre
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.
Étant donné un graphe non orienté G=(V,E), un coupe-cycles C est un sous-ensemble de V, tel que le graphe G restreint à V privé de C est acyclique, c'est-à-dire est une forêt[2].
On peut associer à chaque sommet s de G un poids w(s). On peut aussi considérer un graphe orienté, il s'agit alors de couper tous les cycles orientés.
Le théorème d'Erdős-Pósa dit qu'il existe une fonction f, tel que pour tout entier k, tout graphe possède ou bien k cycles disjoints (par leurs sommets) ou bien un coupe-cycles de taille f(k). De plus, f(k) = O(k log k)[3].
Pour tout entier k, la famille des graphes dont le coupe-cycles minimum est bornée par k, est une famille close par mineur[4].
Le problème algorithmique pour le cas non orienté, et sans poids est le suivant :
Les cas orientés et avec poids se déduisent facilement.
Le problème dans sa version décisionnelle est NP-complet, et fait partie des 21 problèmes NP-complets de Karp[5].
Il existe un algorithme d'approximation de ratio 2, pour le problème non orienté, avec poids[6]. Le problème est APX-complet par réduction au problème de couverture par sommets.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.