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 .
Image:Graph subdivision step1.svg|Avant subdivision
Image:Graph subdivision step2.svg|Après subdivision
Une subdivision d'un graphe (parfois appelée expansion de graphe) est le graphe résultant de la subdivision d'arêtes de .
Lissage
L'opération inverse, le lissage (smoothing en anglais) d'un sommet par rapport aux arêtes et arrivant en consiste à supprimer et à remplacer et par .
Image:Graph subdivision step2.svg|Avant lissage
Image:Graph subdivision step1.svg|Après lissage
Seuls les sommets de degré 2 peuvent être lissés.
Subdivision barycentrique
La subdivision barycentrique subdivise toutes les arêtes du graphe. Ce cas particulier de subdivision donne toujours un graphe biparti.
Homéomorphisme
Deux graphes et sont homéomorphes s'il existe un isomorphisme entre une certaine subdivision de et une certaine subdivision de .
Image:Graph homeomorphism example 1.svg|Graphe G
Image:Graph homeomorphism example 2.svg|Graphe H
Image:Graph homeomorphism example 3.svg|G' et H', subdivisions de G et de H
Déterminer si un sous-graphe d'un graphe donné est homéomorphe à un graphe donné est un problème NP-complet.
Il est évident que la subdivision préserve le fait d'être planaire pour un graphe.
Le théorème de Kuratowski affirme :
De fait, un graphe homéomorphe à ou à est appelé un sous-graphe de Kuratowski.
Une généralisation qui découle du théorème de Robertson-Seymour affirme que pour tout nombre entier , il y a un ensemble de graphes « interdits » tels qu'un graphe peut être plongé dans une surface de genre si et seulement si ne contient pas de copie homéomorphe à l'un des graphes .
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.
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 .
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 .
In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices). This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem.
Explore les intégrales de surface, en mettant l'accent sur l'interprétation physique et les calculs mathématiques dans les champs et domaines vectoriels.