Stable (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir stable.
L'ensemble des sommets en bleu dans ce graphe est un stable maximal du graphe.

En théorie des graphes, un stable – appelé aussi ensemble indépendant ou independent set en anglais – est un ensemble de sommets deux à deux non adjacents. La taille d'un stable est égale au nombre de sommets qu'il contient.

Propriétés combinatoires[modifier | modifier le code]

La taille maximum d'un stable d'un graphe, noté I(G), est un invariant#En théorie des graphes du graphe. Il peut être relié à d'autres invariants, par exemple à la taille de l'ensemble dominant maximum, noté dom(G). On appelle carré d'un graphe G le graphe G' utilisant les mêmes sommets et ayant une arêtes entre deux sommets u et v si et seulement si il existe un chemin de longueur au plus 2 entre u et v dans G. Alors I(G') est inférieure ou égale à dom(G)[1].

Problème algorithmique[modifier | modifier le code]

La recherche d'un stable de taille maximum dans un graphe est un problème classique de la théorie de la complexité.

NP-complétude[modifier | modifier le code]

Le problème de décider si un stable de taille supérieur à N existe dans un graphe G revient au problème de décider si une clique de taille supérieure à N existe dans le graphe complémentaire de G, qui est le graphe obtenu en retirant les arêtes présentes dans le graphe d'origine et en ajoutant les arêtes absentes dans le graphe d'origine. Ce problème est NP-complet.

Notes et références[modifier | modifier le code]

  1. (en) Vijay Vazirani, Approximation algorithms, Springer Verlag,‎ 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 5 (« k-center »)