Homéomorphisme de graphes

En théorie des graphes, une branche des mathématiques, deux graphes ${\displaystyle G}$ et ${\displaystyle 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

Subdivision

La subdivision d'une arête ${\displaystyle uv}$ conduit à un graphe contenant un nouveau sommet ${\displaystyle w}$ et où l'on a remplacé l'arête ${\displaystyle uv}$ par deux nouvelles arêtes, ${\displaystyle uw}$ et ${\displaystyle wv}$.

• 
  Avant subdivision
• 
  Après subdivision

Une subdivision d'un graphe ${\displaystyle G}$ (parfois appelée expansion de graphe[2]) est le graphe résultant de la subdivision d'arêtes de ${\displaystyle G}$.

Lissage

L'opération inverse, le lissage (smoothing en anglais) d'un sommet ${\displaystyle w}$ par rapport aux arêtes ${\displaystyle uw}$ et ${\displaystyle wv}$ arrivant en ${\displaystyle w}$ consiste à supprimer ${\displaystyle w}$ et à remplacer ${\displaystyle uw}$ et ${\displaystyle wv}$ par ${\displaystyle uv}$.

• 
  Avant lissage
• 
  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 ${\displaystyle G}$ et ${\displaystyle H}$ sont homéomorphes s'il existe un isomorphisme entre une certaine subdivision de ${\displaystyle G}$ et une certaine subdivision de ${\displaystyle H}$.

• 
  Graphe G
• 
  Graphe H
• 
  G' et H',
  subdivisions de G et de H

Déterminer si un sous-graphe d'un graphe ${\displaystyle G}$ donné est homéomorphe à un graphe ${\displaystyle H}$ donné est un problème NP-complet[3].

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 :

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 ${\displaystyle K_{5}}$ ni au graphe biparti complet à 6 sommets ${\displaystyle K_{3,3}}$.

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

Notes et références

1. (en) Jay Yellen et Jonathan L. Gross, Graph Theory and Its Applications, Boca Raton, Chapman & Hall/CRC, 2005, 2nd éd., 800 p. (ISBN 978-1-58488-505-4, lire en ligne)
2. (en) Richard J. Trudeau, Introduction to Graph Theory, New York, Dover Pub., 1993, 76 p., édition corrigée et étendue (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.
3. Andrea S. LaPaugh et Ronald L. Rivest, « The subgraph homeomorphism problem », Journal of Computer and System Sciences, vol. 20, n^o 2,‎ 1980, p. 133–149 (DOI 10.1016/0022-0000(80)90057-4, MR 574589).

Voir aussi

Crédit d'auteurs

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Homeomorphism (graph theory) » (voir la liste des auteurs).

Article connexe

• Mineur (théorie des graphes)