Mineur (théorie des graphes)

En théorie des graphes, un mineur d'un graphe non orienté $G$ est un graphe obtenable à partir de $G$ en lui supprimant des arêtes, des sommets et en contractant des arêtes. La notion de mineur a été définie et étudiée par Robertson et Seymour dans une série d'articles intitulée Graph minors (I à XXIII), publiée dans le Journal of Combinatorial Theory entre 1983 et 2011.

Le graphe du dessous est un mineur du graphe du dessus. Il a été obtenu en supprimant l'arête $ef$ et en contractant l'arête $bc$.

Définition

Donnonsla définition de László Lovász. Soit $G$ un graphe non orienté fini. Un graphe $H$ est un mineur de $G$ si $H$ peut être obtenu à partir de $G$ en effectuant un nombre quelconque d'opérations parmi les suivantes :

• suppression d'un sommet isolé $x$ : le sommet $x$ est supprimé du graphe ;
• suppression d'une arête $xy$ : on supprime l'arête $xy$, mais ses extrémités restent inchangées ;
• contraction d'une arête $xy$ : on supprime l'arête $xy$, les deux sommets $x$ et $y$ sont fusionnés en un sommet $z$. Toute arête $tx$ ou $ty$ est remplacée par une nouvelle arête $tz$. Une même arête n'est pas ajoutée deux fois (on ne crée pas d'arêtes parallèles).

On trouve des définitions différentes, mais équivalentes, dans la littérature. Une autre définition est la suivante. Un graphe $H$ est un mineur de $G$ s'il peut être obtenu en contractant des arêtes d'un sous-graphe de $G$.

Exemple

Dans cet exemple, le graphe $H$ est un mineur de $G$ :

$H$ :

$G$ :

Pour le voir, considérons le diagramme suivant qui montre les opérations à effectuer sur $G$ pour arriver à $H$ :

• on supprime les arêtes en pointillé
• on supprime le sommet isolé (tout à droite)
• on contracte l'arête en gris.

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). Le théorème de Robertson-Seymour montre que l'on peut caractériser ainsi tous les graphes qui peuvent être tracés sur une surface donnée, en fonction d'un ensemble de mineurs exclus. La notion de mineur permet également d'exprimer simplement certains théorèmes ou conjectures, comme la conjecture de Hadwiger selon laquelle tout graphe $G$ dont le graphe complet à $k$ sommets n'est pas un mineur est colorable avec $k-1$ couleurs.

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

Références

• (en) László Lovász, « Graph Minor Theory », Bull. Amer. Math. Soc. (New Series), vol. 43, n^o 1,‎ 2005, p. 75–86 (lire en ligne) [PDF]
• (en) Neil Robertson et Paul Seymour, « Graph Minors. I. Excluding a forest », Journal of Combinatorial Theory, Series B, vol. 35, n^o 1,‎ 1983, p. 39–61 (DOI 10.1016/0095-8956(83)90079-5).
  Le premier des vingt-trois articles de la série Graph Minors, intitulé Mineurs : exclusion d'une forêt.

Articles connexes

• Théorème de Robertson-Seymour
• Théorème du snark
• Théorème du séparateur planaire