Problème de couverture des sommets
- Problème de couverture des sommets
-
Problème de couverture de sommets
En Théorie des graphes, le problème de couverture de sommets est un problème NP-complet et c'est l'un des 21 problèmes NP-complets de Karp. Il est souvent utilisé en théorie de la complexité pour prouver que d'autres problèmes plus compliqués sont NP complets.
Définition
Une couverture de sommet d'un Graphe G = (V,E) est un sous ensemble de sommets 
tel que pour chaque arête (u,v) de G on a 
ou 
.
Le problème de couverture de sommets est un Problème de décision qui consiste à savoir s'il existe une couverture de sommets qui comporte au plus k sommets.
Le problème d'optimisation associé est de trouver la plus petite couverture de sommet.
Un ensemble de sommets S est une couverture de sommet si son complément 
est un ensemble indépendant. Donc un graphe avec n sommets a une couverture de sommet de taille k si et seulement si le graphes a un ensemble indépendant de taille n-k.
Portail des mathématiques
Catégories : Théorie des graphes | Algorithmique | Problème NP-complet
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Problème de couverture des sommets de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Problème de couverture de sommets — En théorie des graphes, le problème de couverture minimum de sommets (ou problème du transversal minimum) est un problème NP complet faisant partie des 21 problèmes NP complets de Karp. Il est souvent utilisé en théorie de la complexité pour… … Wikipédia en Français
Probleme de l'ensemble dominant — Problème de l ensemble dominant Le problème d ensemble dominant est un problème NP complet de la théorie des graphes. Sommaire 1 Définition 2 Exemple 3 NP complétude 3.1 Preuve … Wikipédia en Français
Problème de l'ensemble dominant — Le problème d ensemble dominant est un problème NP complet de la théorie des graphes. Sommaire 1 Définition 2 Exemple 3 NP complétude 3.1 Preuve … Wikipédia en Français
Problème NP-complet — En théorie de la complexité, un problème NP complet est un problème de décision vérifiant les propriétés suivantes : Il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette… … Wikipédia en Français
Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants … Wikipédia en Français
Complexité des algorithmes — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation … Wikipédia en Français
Complexité des classes P et NP — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation … 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 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
