Mineur (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie 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 ef et en contractant l'arête bc.

La notion de mineur d'un graphe est un concept de théorie des graphes. Il a été défini et étudié 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.

Définition[modifier | modifier le code]

Un graphe H est un mineur du graphe fini et non orienté G s'il peut être obtenu en contractant des arêtes d'un sous-graphe 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 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).

Cette définition est celle qui est donnée par László Lovász[1]. On trouve des définitions différentes, mais équivalentes, dans la littérature.

Dans l'exemple ci-dessus, on passe d'un graphe à son mineur en supprimant trois arêtes (en pointillés), en supprimant un sommet isolé et en contractant une arête (en gris).

Utilité[modifier | modifier le code]

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 théorie des mineurs de graphes est aussi liée au concept de décomposition arborescente.

Notes[modifier | modifier le code]

  1. Lovász 2005  ; cette définition se trouve page 2 du document en ligne.

Références[modifier | modifier le code]

  • (en) László Lovász, « Graph Minor Theory », Bull. Amer. Math. Soc. (New Series), vol. 43, no 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, no 1,‎ 1983, p. 39–61 (lien DOI?).
    Le premier des vingt-trois articles de la série Graph Minors, intitulé Mineurs : exclusion d'une forêt.

Articles connexes[modifier | modifier le code]