Stable (théorie des graphes)
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
Dans la théorie des graphes, un stable (ou ensemble indépendant) est un ensemble de sommets deux-à-deux non adjacents. La taille d'un stable est égal au nombre de sommet qu'il contient.
La recherche dans un graphe d'un stable de taille maximum est un problème classique de la théorie de la complexité.
Le problème de décider si un stable d'une taille particulière existe dans un graphe revient aussi au problème de décider si une clique d'une certaine taille existe dans le graphe inversé (on enlève les arêtes du graphe et on rajoute celles qui n'y étaient pas). Ce problème est NP Complet.
