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.
Définitions 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 .
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 .
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 .
Déterminer si un sous-graphe d'un graphe donné est homéomorphe à un graphe donné est un problème NP-complet..
Homéomorphisme et graphes planaires 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 . Par exemple, est formé des deux graphes interdits ou à pour les surfaces de genre . est appelé ensemble d'obstruction.
Notes et références
Voir aussi Crédit d'auteurs
Article connexe Mineur (théorie des graphes)
Catégorie:Concept en théorie des graphes