Homéomorphisme de graphes

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur les redirections Cet article concerne l'homéomorphisme en théorie des graphes. Pour l'homéomorphisme en topologie, voir Homéomorphisme.
Page d'aide sur l'homonymie Ne doit pas être confondu avec homomorphisme de graphes.

En théorie des graphes, une branche des mathématiques, deux graphes G et G' sont homéomorphes si l'on peut obtenir un même graphe en subdivisant certaines de leurs arêtes[1].

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[modifier | modifier le code]

Subdivision
La subdivision d'une arête uv conduit à un graphe contenant un nouveau sommet w et où l'on a remplacé l'arête uv par deux nouvelles arêtes, uw et wv.
Une subdivision d'un graphe G (parfois appelée expansion de graphe[2]) est le graphe résultant de la subdivision d'arêtes de G.
Lissage
L'opération inverse, le lissage (smoothing en anglais) d'un sommet w par rapport aux arêtes uw et wv arrivant en w consiste à supprimer w et à remplacer uw et wv par uv.
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 G et H sont homéomorphes s'il existe un isomorphisme entre une certaine subdivision de G et une certaine subdivision de H.
Déterminer si un sous-graphe d'un graphe G donné est homéomorphe à un graphe H donné est un problème NP-complet.[réf. nécessaire]

Homéomorphisme et graphes planaires[modifier | modifier le code]

Il est évident que la subdivision préserve le fait d'être planaire pour un graphe.

Le théorème de Kuratowski affirme :

Théorème — Un graphe fini est planaire si et seulement si il ne contient pas de sous-graphe homéomorphe au graphe complet à 5 sommets K_5 ni au Graphe biparti complet à 6 sommets K_{3,3}.

De fait, un graphe homéomorphe à K_5 ou à K_{3,3} 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 g, il y a un ensemble de graphes « interdits » L(g) = \{G_{i}^{(g)}\} tels qu'un graphe H peut être plongé dans une surface de genre g si et seulement si H ne contient pas de copie homéomorphe à l'un des graphes G_{i}^{(g)}. Par exemple, L(0) = \{K_{5}, K_{3,3}\} est formé des deux graphes interdits K_5 ou à K_{3,3} pour les surfaces de genre 0. L(g) est appelé ensemble d'obstruction.

Notes et références[modifier | modifier le code]

  1. (en) Jay Yellen et Jonathan L. Gross, Graph Theory and Its Applications, Boca Raton, Chapman & Hall/CRC,‎ 2005 (ISBN 978-1-58488-505-4)
  2. (en) Richard J. Trudeau, Introduction to Graph Theory, New York, Dover Pub.,‎ 1993, 76 p. (ISBN 978-0-486-67870-2, lire en ligne), Definition 20. If some new vertices of degree 2 are added to some of the edges of a graph G, the resulting graph H is called an expansion of G.

Voir aussi[modifier | modifier le code]

Crédit d'auteurs[modifier | modifier le code]

Article connexe[modifier | modifier le code]