Mineur (theorie des graphes)
- Mineur (theorie des graphes)
-
Mineur (théorie des graphes)
Pour les articles homonymes, voir
Mineur.
Un exemple de deux graphes, dont l'un (celui du dessous) est un mineur de l'autre. Le mineur a été obtenu en supprimant l'arête [e,f] et en contractant l'arête [b,c]
La notion de mineurs d'un graphe est un concept défini par Robertson et Seymour dans une série d'articles en théorie des graphes.
Définition
Un graphe H est un mineur du graphe G s'il peut être obtenu en contractant les arêtes d'un sous-graphe induit de G. En d'autres termes, H peut être obtenu à partir de G en effectuant un nombre quelconque d'opérations parmi les suivantes :
- suppression d'un sommet x : le sommet x est supprimé du graphe, ainsi que toutes les arêtes adjacentes à x
- suppression d'une arête [x,y]: on supprime l'arête [x,y], mais ses extrémités restent inchangées.
- contraction d'une arête [x,y] : on supprime l'arête [x,y], les deux sommets x et y sont fusionnés en un sommet z. Toute arête [t,x],[x,t],[t,y] ou [y,t] est respectivement remplacée par une nouvelle arête [t,z],[z,t],[t,z], ou [z,t]. Une arête n'est pas ajoutée deux fois.
Utilité
Une des utilités du concept de mineur est la caractérisation de classes de graphes particulières comme ayant (ou n'ayant pas) un certain graphe comme mineur. Par exemple, un graphe planaire ne contient comme mineur ni K5 (graphe complet d'ordre 5), ni K3,3 (graphe biparti complet d'ordre 3).
La théorie des mineurs de graphes est aussi liée au concept de décomposition arborescente.
Catégorie : Concept en théorie des graphes
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Mineur (theorie des graphes) de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Mineur (théorie des graphes) — Pour les articles homonymes, voir Mineur. Un exemple de deux graphes, dont l un (celui du dessous) est un mineur de l autre. Le mineur a été obtenu en supprimant l arête [e,f] et en contractant l arête [b,c] La notion de mineur d un graphe est un … 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
Mineur — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Mineur », sur le Wiktionnaire (dictionnaire universel) Le mot mineur (du latin minor) peut avoir… … Wikipédia en Français
Problème des quatre couleurs — Théorème des quatre couleurs Carte administrative de la Russie colorée avec quatre couleurs Le théorème des quatre couleurs affirme qu il est possible, en n utilisant que quatre couleurs différentes, de colorer[1] … Wikipédia en Français
Theoreme des quatre couleurs — Théorème des quatre couleurs Carte administrative de la Russie colorée avec quatre couleurs Le théorème des quatre couleurs affirme qu il est possible, en n utilisant que quatre couleurs différentes, de colorer[1] … Wikipédia en Français
Théorème des quatre couleurs — Vitrail coloré avec quatre couleurs Le théorème des quatre couleurs indique qu il est possible, en n utilisant que quatre couleurs différentes, de colorer[1] n importe quelle carte découpée en régions connexes, de sorte que deux régions… … 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
