Mineur (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

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.

[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$
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.

[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 planaire ne contient comme mineur ni $K 5$ (graphe complet d'ordre 5), ni $K 3,3$ (graphe biparti complet d'ordre 3).

La théorie des mineurs de graphes est aussi liée au concept de décomposition arborescente.