Graphe planaire
Dans lathéorie des graphes,ungraphe planaireest ungraphequi a la particularité de pouvoir se représenter sur unplansans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peutplongerdans le plan, ou encore les graphes dont lenombre de croisementsest nul.
Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisonset d'autres plus difficiles comme lethéorème des quatre couleurs.
Exemples et contre-exemples
[modifier|modifier le code]- Ce graphe est clairement planaire, car il n'existe pas d'intersection entre deux arêtes.
- C'est ungraphe completà quatre sommets (K4). Il est planaire: si on déplace le sommet4dans le triangle1 2 3,on constate qu'il n'y a plus d'intersection d'arêtes.
- C'est un graphe complet à 5 sommets (K5). Il n'est pas planaire.
- C'est ungraphe biparti completK3,3à 6 sommets, 3 d'entre eux se connectant aux trois autres. Il n'est pas planaire.
En fait,K5etK3,3sont les plus petits graphes non planaires, ce qui découle de la caractérisation ci-dessous.
Caractérisation de Kuratowski et de Wagner
[modifier|modifier le code]![](https://upload.wikimedia.org/wikipedia/commons/thumb/e/e1/K5_Eurasie.svg/220px-K5_Eurasie.svg.png)
LemathématicienpolonaisKazimierz Kuratowskia établi en 1930 la caractérisation suivante des graphes planaires:
- Un graphe fini est planaire si et seulement s'il ne contient pas desous-graphepartiel qui est uneexpansiondeK5(le graphe complet à 5 sommets) ouK3,3(le graphe complet biparti à 3+3 sommets).
L'expansion(ousubdivision) d'un graphe est le résultat de l'ajout d'un ou plusieurs sommets sur une ou plusieurs arêtes (par exemple, transformation de l'arête •——• en •—•—•).
Quelques années plus tard le mathématicienallemandKlaus Wagneren donna une caractérisation semblable:
- Un graphe fini est planaire si et seulement s'il ne compte pasK5ouK3,3parmi sesmineurs.
Unmineurd'un graphe est le résultat de lacontraction d'arêtes(fusionnant les extrémités), la suppression d'arêtes (sans fusionner les extrémités), et la suppression de sommets (et des arêtes adjacentes).
La différence entre ces deux caractérisations est minuscule, mais Wagner fit la conjecture[1]que ce dernier admettrait une généralisation que celle de Kuratowski n'admettait pas. Il supposait qu'il y aurait, pour chaque classe de graphes finis close par mineur, unensemble finidemineurs interditsqui la caractériserait. Une classe est diteclose par mineursi elle comprend tous les mineurs de chaque graphe qu'elle comprend; un graphe planaire, par exemple, est toujours planaire après la contraction ou suppression d'arêtes et de sommets, et pour cette classe les deux seuls mineurs interdits sontK5etK3,3.Mais aussi notamment il existerait un nombre fini de mineurs interdits pour la classe des graphes qui peuvent se plonger sur untore,ou sur une surface quelconque, et pour la classe de graphes qui peuvent se plonger dans l'espace à trois dimensions sans nœud, entre autres. Cetteconjecturefut enfin prouvée en 2004 par Robertson et Seymour, mais de façon non-constructive: par exemple, on ne connaît toujours pas tous les mineurs interdits pour le plongement de graphe sur un tore. Pour plus d'informations, voir l'articlethéorème de Robertson-Seymour.
Propriétés
[modifier|modifier le code]![](https://upload.wikimedia.org/wikipedia/commons/thumb/5/54/LineGraphExampleA.svg/220px-LineGraphExampleA.svg.png)
Dans toute la suite du paragraphe, nous utiliserons les notations suivantes:
- désigne un graphe planaire,
- son nombre de nœuds,
- son nombre d'arêtes (ou de liens),
- son nombre de faces.
Une face est unecomposante connexedu complémentaire du graphe dans le plan. Le degré d'une faceest la longueur de son cycle frontière, on considère uncheminle plus court possible d'origine confondue avec son extrémité, le nombre d'arêtes (avec leur multiplicité) est le degré de la face.Il est noté.On obtient une première formule presque évidente[2]:
En effet, chaque arête élément d'un cycle borde deux faces, une arête partagée par aucun cycle est parcourue deux fois par le chemin frontière de la composante non bornée du complémentaire du graphe.
Formule d'Euler et conséquences
[modifier|modifier le code]Laformule d'Eulerpour un graphe planaire connexe est[3]:
Une méthode simple pour la démontrer est de l'établir pour un graphe sans cycle (à une face), puis par récurrence d'ajouter les arêtes qui engendrent des cycles. Cette formule permet de démontrer que tout graphe simple planaire connexe, ayant au moins trois sommets, vérifie la majoration suivante[4].
Ungraphe simpleest un graphe sans boucle (une boucle est une arête qui possède une origine et une extrémité confondues) et sans arête multiple (des arêtes multiples sont des arêtes ayant même origine et même extrémité). Cette formule se démontre simplement: toute face est de degré au moins égal à 3, car le graphe comporte au moins trois nœuds et est simple. On en déduit, par la formule (1), que 3fest inférieur ou égal à 2a.La formule d'Euler permet de conclure.
Cette formule implique que les graphes planaires sont desgraphes creux.De plus, leurarboricitéest bornée par 3.
Cette majoration est à l'origine d'une démonstration du fait queK5n'est pas planaire. En effet,K5dispose de 10 arêtes, et 5 nœuds, ce résultat est incompatible avec la majoration (2). Si, avec les hypothèses de la majoration (2), le graphe estsans triangle,on dispose alors de la majoration:
Le raisonnement est le même, mais cette fois-ci le degré d'une face est au moins égal à 4. On en déduit queK3,3n'est pas planaire[4].Les détails sont donnés dans l'article «Énigme des trois maisons».
Dessin de graphe
[modifier|modifier le code]Laconjecture de Scheinerman,maintenant démontrée, énonce que tout graphe planaire est legraphe d'intersectionde segments dans le plan.
Intérêt et applications
[modifier|modifier le code]![](https://upload.wikimedia.org/wikipedia/commons/3/33/Graphe_de_mouvement_du_cavalier_3x4.png)
Un exemple simple pour illustrer l'intérêt des graphes planaires est une énigme, ditedes trois maisonsinitialement posée sous forme mathématique par H. E. Dudeney en1917[7].Elle prend la forme suivante: « Un lotissement de trois maisons doit être équipé d'eau, de gaz et d'électricité. La règlementation interdit de croiser les canalisations pour des raisons de sécurité. Comment faut-il faire[8]?»
Cependant, l'intérêt pour les graphes planaires est plus ancien, il remonte authéorème des quatre couleurs.Depuis, de nombreux problèmes difficiles du point de vue algorithmique (NP-complet) se sont avérés faciles dans cette classe particulière; toutefois pour la plupart de ces problèmes seule l'interdiction dumineurK5est nécessaire.
La propriété de planarité est à l'origine des questions plus générales de plongement de graphe sur des surfaces (graph embedding): peut-on plonger un graphe donné sur une surface donnée?
La propriété de planarité d'un graphe le rend plus abordable aucerveauhumain[réf. nécessaire]comme en témoigne l'exemple du problème ducavalierauxéchecsci-dessous:
- Sur un échiquier, on dispose un cavalier. Le but est de le faire passer par toutes les cases, une seule fois par case, en respectant le mouvement classique de la pièce aux échecs. Pour illustrer le problème, on utilise ici un plateau de quatre cases sur trois rangées. Le problème est représenté par un graphe de mouvement; les sommets du graphe correspondent aux cases de l’échiquier; les arcs figurent les mouvements possibles. Ainsi, à partir de lacase 1,il est possible de se rendre à lacase 8ou à lacase 6car celles-ci sont liées à la première sur le graphe.
- Présenté de cette manière, le problème reste complexe. Toutefois, le graphe est planaire et on peut le représenter de façon plus intuitive. On peut facilement extraire de cette nouvelle représentation une solution (tracée en vert) partant de lacase 3et arrivant à lacase 10.
De façon plus terre à terre, il était plus facile de concevoir les tout premierscircuits imprimésà transistors quand le graphe du circuit était planaire: on évitait alors de devoir recourir au procédé bicouche ou à des «straps» fragiles pour s'échapper du plan du circuit imprimé.
Aspects algorithmiques
[modifier|modifier le code]Reconnaissance
[modifier|modifier le code]Le problème qui consiste, étant donné un graphe à savoir si c'est un graphe planaire est appelétest de planarité.Plusieurs algorithmes ont été proposés pour ce problème. Les meilleurs atteignent unecomplexité en temps linéaire,ce qui est optimal asymptotiquement. Le premier tel algorithme date de 1974, et est dû àRobert TarjanetJohn Hopcroft[9]. Robert Cori a décrit l'historique et les principes de cet algorithme dans un article paru dans leBulletin de la société informatique de France[10].
Problèmes restreints à la classe
[modifier|modifier le code]Certainsproblèmes algorithmiquessont plus faciles à résoudre si on se restreint aux graphes planaires, par exemple leproblème de l'isomorphisme de graphespeut être résolu en temps linéaire[11],ce qui a priori n'est pas du tout le cas pour l'ensemble des graphes. De même pour l'approximation,par exemple le problèmek-centrene peut pas être approché avec un meilleur ratio que 2 dans le cas général, sauf siP=NP[12],alors qu'il existe unschéma d'approximation en temps polynomialpour le cas planaire[13].
Ce n'est pas le cas de tous les problèmes, par exemple leproblème de couverture par sommetsresteNP-complet,c'est-à-dire difficile à résoudre a priori, même si l'on se restreint à des graphes planaires dedegréau plus 3[14].
Références
[modifier|modifier le code]- Plus précisément, Wagner montra que cette formulation permettait d'énoncer ce qui est à présent connu sous le nom dethéorème des mineurs,mais a toujours affirmé qu'il pensait qu'elle serait sans doute réfutée.
- T. Chomette, «Graphes planaires», surCultureMath, Département de mathématiques appliquées de l'École normale supérieure,p.1.
- T. Chomette,p.4.
- (en)WilfriedImrichetSandi Klavžar(sl),Product Graphs: Structure and recognition,John Wiley & Sons,coll.« Wiley-Interscience Series in Discrete Mathematics and Optimization »,.
- La proposition ainsi qu'une démonstration est disponible dansT. Chomette,p.3.
- Cette démonstration provient deT. Chomette,p.4.
- (en)MartinGardner,The Sixth Book of Mathematical Games from Scientific American,University of Chicago Press,(ISBN0-226-28250-3),p.92-94
- On la trouve sous le nom de« Problème des trois villas et des trois usines »dansClaudeBerge,Graphes,Gauthier-Villars,,3eéd.(ISBN978-2-04-015555-1),p.17
- JohnHopcroftetRobert E.Tarjan,«Efficient planarity testing»,Journal of the ACM,vol.21,no4,,p.549–568(DOI10.1145/321850.321852).
- Robert Cori, «L'algorithme de test de planarité de R. E. Tarjan»,1024– Bulletin de la société informatique de France,no4,,p.55-65(ISSN2270-1419,lire en ligne,consulté le).
- John E.Hopcroftet Jin-KueWong,« Linear time algorithm for isomorphism of planar graphs »,dansProceedings of the Sixth Annual ACMSymposium on Theory of Computing,(DOI10.1145/800119.803896),p.172–184.
- Wen-Lian Hsu et George L. Nemhauser, «Easy and hard bottleneck location problems»,Discrete Applied Mathematics,Elsevier,vol.1,no3,,p.209-215
- David Eisenstat, Philip N. Klein et Claire Mathieu,« Approximatingk-center in planar graphs »,dansProceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014,,p.617-627
- (en)Michael GareyetDavid S.Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness,W.H. Freeman,(ISBN0-7167-1045-5)
Voir aussi
[modifier|modifier le code]Articles connexes
[modifier|modifier le code]- Graphe dual
- Théorème de Battle-Harary-Kodama
- Critère de planarité de Whitney
- Critère de planarité de Fraysseix-Rosenstiehl
- Critère de planarité de Mac Lane
- Critère de planarité de Colin de Verdière
- k-arbre
- Théorème du séparateur planaire
Liens externes
[modifier|modifier le code]- Bibliothèque d'algorithmes et éditeur de graphes— bibliothèque d'algorithmes sur les graphes en GPL, parmi lesquels un test de planarité, une représentation planaire, une exhibition de sous-graphes de Kuratowski en temps linéaire
- BGraphe— pour jouer avec les graphes planaires