Mineur (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques
Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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 et en contractant l'arête .

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 est un mineur du graphe fini et non orienté s'il peut être obtenu en contractant des arêtes d'un sous-graphe de . En d'autres termes, peut être obtenu à partir de en effectuant un nombre quelconque d'opérations parmi les suivantes :

  • Suppression d'un sommet isolé  : le sommet est supprimé du graphe ;
  • Suppression d'une arête  : on supprime l'arête , mais ses extrémités restent inchangées ;
  • Contraction d'une arête  : on supprime l'arête , les deux sommets et sont fusionnés en un sommet . Toute arête ou est remplacée par une nouvelle arête . 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 (graphe complet d'ordre 5), ni (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,‎ , 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,‎ , 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[modifier | modifier le code]