Retour à la table des matières

Département de mathématiques de l'Université de La Rochelle

 

Chapitre 5 - Graphes planaires

 

Nous avons eu l'occasion de relier au problème du coloriage des cartes de géographie une question analogue sur les sommets d'un graphe associé à la carte, son graphe de voisinage, dont les sommets sont les pays, deux d'entre eux étant reliés par une arête chaque fois que les pays correspondants partagent une frontière commune non réduite à un point (phénomène qui se produit, par exemple, dans la carte représentant les états des USA). Nous avons alors souligné que la propriété la plus importante de ce graphe était qu'il s'agit d'un graphe planaire. Nous étudions dans cette leçon divers exemples de graphes, planaires ou non, établissons l'identité d'Euler reliant le nombre de sommets, d'arêtes et de faces dans un tel graphe, et démontrons en partie un théorème célèbre, dû à Kuratowski, qui caractérise les graphes planaires.

A - Plongements des graphes. Graphes planaires

Définition - Un graphe G est dit spatial s'il est possible de le dessiner dans l'espace 3 sans que deux arêtes ne se coupent (sauf en un sommet commun). Il est dit planaire s'il est possible de faire ceci dans le plan 2.

Remarque de terminologie : dans le premier cas, on dit que le graphe peut être plongé dans 3, dans le second qu'il peut être plongé dans 2. On peut bien sûr imaginer de plonger des graphes dans d'autres espaces (en particulier, nous allons voir ci-dessous que l'existence d'un plongement de G dans le plan équivaut à celle d'un plongement de G sur la sphère).

Remarque -  Si G est un graphe planaire, tout sous-graphe de G (obtenu en effaçant dans G certains sommets et certaines arêtes) l'est aussi.

Une telle définition peut sembler restrictive (pourquoi ne pas définir des graphes quadri-dimensionnels qu'il serait possible de dessiner dans 4, etc). En réalité, il n'en est rien car tout graphe peut être plongé dans l'espace 3, de sorte qu'il n'est jamais nécessaire de faire intervenir dans ces questions des espaces de dimension supérieure à 3.

Théorème -  (a) Tout graphe G est spatial.
(b) Un graphe G est planaire si et seulement si il est plongeable dans la sphère de l'espace 3.

Démonstration - Rappelons que, par convention, les graphes étudiés sont toujours finis.

(a) Soit donc G un graphe, {s1, , sn} l'ensemble de ses sommets et {a1, , ar} l'ensemble de ses arêtes (éventuellement multiples, avec éventuellement des boucles - la seule restriction est qu'elles soient en nombre fini).

Représentons les sommets de G dans l'espace par des points régulièrement échelonnés le long de l'axe (Oz) : on place le sommet sk en (0, 0, k). Considérons par ailleurs un demi-plan vertical contenant l'axe (Oz), par exemple le demi-plan (xOz), et faisons lui subir r rotations d'axe (Oz) et d'angle 2p/r. Nous obtenons r demi-plans verticaux P1, , Pr se coupant deux à deux le long de l'axe (Oz). Sur le demi-plan Pk, dessinons un arc de cercle entre les deux sommets ai et aj que relie l'arête ak (cf. le dessin). On a bien ainsi une représentation spatiale de notre graphe, telle que deux arêtes distinctes se trouvent toujours dans des demi-plans distincts, et ne se rencontrent donc éventuellement que sur l'axe (Oz), ceci ne se produisant en outre que si ces arêtes ont un ou deux sommets communs, qui seront leurs points de rencontre.

(b) Soit G un graphe plongé dans le plan. Considérons 2 comme le plan équatorial de la sphère. On peut associer à tout point M de 2 un point p(M) de la sphère par la correspondance suivante (appelée projection stéréographique) : on trace la droite qui relie M au pôle nord N de la sphère. Cette droite recoupe la sphère en un point unique : c'est p(M) (voir la figure ci-dessous).

Il est donc possible, en utilisant cette correspondance, de ``remonter'' une figure plane sur la sphère. Si nous faisons cette opération pour notre graphe plongé, nous dessinons bien un graphe sur la sphère. Il reste à montrer que l'on obtient bien un plongement de G dans la sphère, c'est-à-dire que dans la nouvelle figure, deux arêtes ne se coupent qu'en un éventuel sommet commun. Si ce n'était pas le cas, leur point d'intersection serait la projection d'un point du plan lui-même à l'intersection de deux arêtes sans toutefois être un sommet, en contradiction avec l'hypothèse de plongement faite (le seul détail à vérifier est qu'il est impossible que deux points distincts du plan ne se projettent en un même point de la sphère, ce qui ruinerait évidemment l'argument ci-dessus).

Réciproquement, si G est un graphe plongé sur une sphère, il est toujours possible de faire pivoter celle-ci de sorte qu'aucune des arêtes ne passe par le pôle nord. Il suffit alors d'inverser la procédure ci-dessus (en projetant, cette fois, de la sphère vers le plan) pour obtenir un plongement de G dans le plan.

Remarque -  On notera que, dans la démonstration des points (a) et (b) ci-dessus, les plongements de G construits dans l'espace ou dans le plan font intervenir des arêtes qui ne sont pas rectilignes. On peut néanmoins montrer, en choisissant avec davantage de précautions les points où l'on place les sommets, que tout graphe simple (sans boucle ni arête multiple : une telle restriction est évidemment inévitable) se plonge dans l'espace avec des arêtes rectilignes (voir [ref.a.completer]). Dans le cas des graphes planaires, le résultat est vrai aussi, mais la démonstration est moins facile. On se convaincra cependant, en choisissant des exemples assez simples, que l'on arrive toujours à obtenir une telle représentation.

Remarque -  Il résulte de la partie (b) du théorème ci-dessus que le graphe d'incidence de n'importe quel polyèdre régulier est un graphe planaire puisque ces polyèdres peuvent être plongés dans une sphère. On pourra, en exercice, représenter à plat et avec des arêtes rectilignes un cube ou un tétraèdre.