Stable (theorie des graphes)


Stable (theorie des graphes)

Stable (théorie des graphes)

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.

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

La recherche d'un stable de taille maximum dans un graphe 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é – 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.

Ce document provient de « Stable (th%C3%A9orie des graphes) ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Stable (theorie des graphes) de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Stable (théorie des graphes) — 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 …   Wikipédia en Français

  • Clique (Théorie Des Graphes) — Pour les articles homonymes, voir clique. Exemple de graphe avec une 3 clique (en rouge) …   Wikipédia en Français

  • Clique (theorie des graphes) — Clique (théorie des graphes) Pour les articles homonymes, voir clique. Exemple de graphe avec une 3 clique (en rouge) …   Wikipédia en Français

  • Clique (théorie des graphes) — Pour les articles homonymes, voir clique. Exemple de graphe avec une 3 clique (en rouge) …   Wikipédia en Français

  • Lexique De La Théorie Des Graphes — Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Lexique de la theorie des graphes — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Lexique en théorie des graphes — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Lexique de la théorie des graphes — Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A Acyclique (grap …   Wikipédia en Français

  • Théorie spectrale des graphes — La théorie spectrale des graphes s intéresse aux rapports entre le spectre d un graphe et ses propriétés, et fait partie de la théorie algébrique des graphes. Un graphe peut être représenté par plusieurs matrices, et les valeurs propres d une… …   Wikipédia en Français

  • Theorie des jeux — Théorie des jeux Le dilemme du prisonnier est une célèbre illustration en théorie des jeux d un jeu à somme non nulle. La théorie des jeux constitue une approche mathématique de problèmes de stratégie tels qu’on en trouve en recherche… …   Wikipédia en Français