Mineur (théorie des graphes)
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche à compléter concernant les mathématiques, vous pouvez partager vos connaissances en le modifiant. |
Le mineur d'un graphe est un concept défini par Robertson et Seymour dans une série d'articles en théorie des graphes.
[modifier] 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
- 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.
[modifier] 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 triangulé est un graphe qui ne contient pas comme mineur un cycle sans corde de longueur quatre. Autre 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.
