Graphe polyédrique
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b1/Dodecahedron_schlegel.svg/220px-Dodecahedron_schlegel.svg.png)
En théorie des graphes, une branche des mathématiques, un graphe polyédrique est un graphe non orienté défini en termes géométriques : il représente les sommets et les arêtes d'un polyèdre convexe.
On peut aussi définir un graphe polyédrique en termes purement issus de la théorie des graphes : c'est un graphe planaire 3 sommet-connexe.
Caractérisation
[modifier | modifier le code]Le diagramme de Schlegel d'un polyèdre convexe représente ses sommets et ses arêtes par des points et des segments de droite dans le plan euclidien. La figure résultante est un polygone convexe subdivisé en polygones plus petits. On peut associer à cette figure un graphe. Cette figure n'a pas de croisements, de telle sorte qu'un graphe polyédrique est un graphe planaire. De plus, le théorème de Balinski (en) affirme que c'est un graphe 3 sommet-connexe, c'est-à-dire qu'il faut en retirer trois sommets avant qu'ils ne soient plus connexes.
En sens inverse, d'après le théorème de Steinitz (en), un graphe planaire 3 sommet-connexe caractérise complètement un polyèdre. Plus précisément, quand un graphe est à la fois planaire et 3-connexe, il existe un polyèdre dont les sommets et les arêtes forment un graphe isomorphe au graphe de départ[1],[2].
Cycles hamiltoniens et exposant de réduction
[modifier | modifier le code]![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Herschel_graph_no_col.svg/220px-Herschel_graph_no_col.svg.png)
Selon la conjecture de Tait, tout graphe polyédrique cubique (c'est-à-dire tout graphe polyédrique où chaque sommet voit arriver exactement trois arêtes) posséderait un cycle hamiltonien. Cette conjecture a été infirmée par un contre-exemple de William Tutte, le graphe de Tutte, qui est polyédrique et cubique, mais pas hamiltonien.
Si l'on ne demande plus au graphe d'être cubique, il y a des graphes polyédriques non hamiltoniens bien plus petits. Celui avec le moins de sommets et d'arêtes est le graphe de Herschel à 11 sommets et à 18 arêtes[3]. Il existe également un graphe polyédrique non hamiltonien à 11 sommets dont toutes les faces sont des triangles, le graphe de Goldner-Harary[4].
Un résultat plus fort est qu'il existe une constante strictement inférieure à , l'exposant de réduction (shortness exponent en anglais), ainsi qu'une famille infinie de graphes polyédriques tels que la longueur de la plus longue chaîne simple d'un graphe à sommets de la famille est d'ordre [5],[6].
Dénombrement des graphes polyédriques
[modifier | modifier le code]Duijvestijn a donné un décompte des graphes polyédriques jusqu'à 26 arêtes[7]. Le nombre de ces graphes avec 6, 7, 8, … arêtes est :
- 1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, …
C'est la suite A002840 de l'OEIS.
On peut aussi énumérer (en) les graphes polyédriques en fonction de leur nombre de sommets. Le nombre de ces graphes avec 4, 5, 6, … sommets est
- 1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, …
C'est la suite A000944 de l'OEIS.
Cas particuliers
[modifier | modifier le code]Un graphe polyédrique est le graphe d'un polyèdre simple (en) s'il est cubique (si chaque sommet est de degré 3). C'est le graphe d'un polyèdre simplicial (en) si c'est un graphe maximal planaire (en).
Les graphes de Halin, des graphes formés à partir d'un arbre représenté dans un plan où l'on a relié toutes les feuilles de l'arbre, forment une autre famille importante de graphes polyédriques.
Notes et références
[modifier | modifier le code]- (en) Günter M. Ziegler, Lectures on Polytopes, (ISBN 0-387-94365-X), chapitre 4, Steinitz' Theorem for 3-Polytopes, page 103.
- (en) Branko Grünbaum, Convex Polytopes, vol. 221, Springer-Verlag, , 2e éd., 466 p. (ISBN 978-0-387-40409-7, lire en ligne).
- (en) Eric W. Weisstein, « Herschel Graph », sur MathWorld.
- (en) Eric W. Weisstein, « Goldner-Harary Graph », sur MathWorld.
- (en) Eric W. Weisstein, « Shortness Exponent », sur MathWorld.
- (en) Branko Grünbaum et T. S. Motzkin, « Longest simple paths in polyhedral graphs », Journal of the London Mathematical Society, vol. s1-37, no 1, , p. 152–160 (DOI 10.1112/jlms/s1-37.1.152).
- (en) A. J. W. Duijvestijn, « The number of polyhedral (3-connected planar) graphs », Mathematics of Computation, vol. 65, , p. 1289–1293 (DOI 10.1090/S0025-5718-96-00749-1).
Lien externe
[modifier | modifier le code](en) Eric W. Weisstein, « Polyhedral Graph », sur MathWorld