Mineur (théorie des graphes)

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. Soit un graphe non orienté fini. Un graphe est un mineur de 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. On trouve des définitions différentes, mais équivalentes, dans la littérature. GraphMinorExampleB.png|Un graphe G. GraphMinorExampleA.png|Un mineur H de G. GraphMinorExampleC.svg|Passage de G à H. 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). 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 notion de mineur permet également d'exprimer simplement certains théorèmes ou conjectures, comme la conjecture de Hadwiger selon laquelle tout graphe dont le graphe complet à sommets n'est pas un mineur est colorable avec couleurs.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (1)

Concepts associés (69)

Cours associés (27)

Séances de cours associées (220)

MATH-101(g): Analysis I

Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles d'une variable.

MATH-467: Probabilistic methods in combinatorics

We develop a sophisticated framework for solving problems in discrete mathematics through the use of randomness (i.e., coin flipping). This includes constructing mathematical structures with unexpecte

CS-450: Advanced algorithms

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Akash Kumar

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have

IEEE COMPUTER SOC2022

Homéomorphisme de graphes

En théorie des graphes, une branche des mathématiques, deux graphes et sont homéomorphes si l'on peut obtenir un même graphe en subdivisant certaines de leurs arêtes. Deux graphes sont homéomorphes si et seulement si leurs représentations graphiques usuelles (avec des segments de droites reliant les sommets entre eux) sont homéomorphes au sens que ce mot a en topologie. Subdivision La subdivision d'une arête conduit à un graphe contenant un nouveau sommet et où l'on a remplacé l'arête par deux nouvelles arêtes, et .

Mineur (théorie des graphes)

Coloration de graphe

thumb|Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune.

Couvre les transformations linéaires, les matrices, les noyaux et les propriétés des matrices inversible.

Explore les contre-factuals dans les SEM et D-Separation dans les modèles graphiques.

Couvre l'analyse des fonctions, de la composition et de l'induction mathématique.