Ensemble indépendant
- Ensemble indépendant
-
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.
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.
Catégorie : Concept en théorie des graphes
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Ensemble indépendant de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
indépendant — indépendant, ante [ ɛ̃depɑ̃dɑ̃, ɑ̃t ] adj. • 1584; de 1. in et dépendant I ♦ Qui est libre. 1 ♦ (Personnes) Indépendant de... : qui ne dépend pas (de qqn, qqch.). Être indépendant des autres. « Ses généraux, trop indépendants les uns des autres » … Encyclopédie Universelle
Ensemble Transitif — En mathématique, un ensemble transitif est un ensemble E composé d éléments, qui sont aussi des ensembles, et dont les éléments appartiennent aussi à l ensemble initial E. Sommaire 1 Définition 2 Exemples 3 Notes … Wikipédia en Français
Ensemble vocal — Chœur (musique) Pour les articles homonymes, voir Chœur. Du grec ancien Χορος, choros, il s agissait dans la haute Antiquité grecque de danse de cérémonial ou de danseur cérémonieux. Puis, ce fut un petit groupe d hommes masqués et chargés de… … Wikipédia en Français
Ensemble instrumental national du Mali — L’Ensemble instrumental national du Mali Créé au lendemain de l’Indépendance du Mali en 1961, l’Ensemble instrumental national est un groupe de musique traditionnelle et chorale. Il a pour mission de prospecter, répertorier et mettre en valeur… … Wikipédia en Français
L’Ensemble Instrumental National — Ensemble instrumental national du Mali Créé au lendemain de l’Indépendance du Mali en 1961, l’Ensemble instrumental national est un groupe de musique traditionnelle et chorale. Il a pour mission de prospecter, répertorier et mettre en valeur… … Wikipédia en Français
Campagnes De L'État Indépendant Du Congo Contre Les Arabo-Swahilis — Le Kivu Informations générales Date 1892 1894 Lieu … Wikipédia en Français
Campagnes de l'Etat independant du Congo contre les Arabo-Swahilis — Campagnes de l État indépendant du Congo contre les Arabo Swahilis Campagnes de l État indépendant du Congo contre les Arabo Swahilis Le Kivu Informations générales Date 1892 1894 Lieu … Wikipédia en Français
Campagnes de l'État indépendant du Congo contre les Arabo-Swahilis — Le Kivu Informations générales Date 1892 1894 Lieu Kivu, province Orientale, Kasai … Wikipédia en Français
Campagnes de l'État indépendant du Congo contre les arabo-swahilis — Le Kivu Informations générales Date 1892 1894 Lieu … Wikipédia en Français
Campagnes de l'état indépendant du congo contre les arabo-swahilis — Le Kivu Informations générales Date 1892 1894 Lieu … Wikipédia en Français
