Homéomorphisme 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

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$ .

Avant subdivision
Après subdivision

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$ .

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

Graphe G
Graphe H
G' et H',
subdivisions de G et 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^[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 $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

↑ (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)
↑ (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.
↑ 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)

Portail des mathématiques

[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).

[1]

[2]

[3]