Graphe polyédrique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Le diagramme de Schlegel d'un dodécaèdre régulier est un graphe polyédrique.

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 comme des points et des segments de droite dans le plan euclidien. La figure résultante est un polygone convexe subdivisé en de plus petits polygones. 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, 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]

Le graphe de Herschel, polyédrique mais non hamiltonien. On peut se rendre compte qu'il est planaire en déplaçant le sommet central à l'extérieur.

Selon la conjecture de Tait (en), 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édraux 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 \alpha strictement inférieure à 1, l'exposant de réduction (shortness exponent en anglais), ainsi qu'une famille infinie de graphes polyédraux tels que la longueur de la plus longue chaîne simple d'un graphe à n sommets de la famille est d'ordre O(n^\alpha)[5],[6].

Dénombrement des graphes polyédraux[modifier | modifier le code]

Duijvestijn a donné un décompte des graphes polyédraux 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édraux 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édraux.

Notes et références[modifier | modifier le code]

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

  1. (en) Günter M. Ziegler, Lectures on Polytopes,‎ 1995 (ISBN 0-387-94365-X), chapitre 4, Steinitz' Theorem for 3-Polytopes, page 103.
  2. (en) Branko Grünbaum, Convex Polytopes, vol. 221, Springer-Verlag,‎ 2003 (ISBN 978-0-387-40409-7).
  3. (en) Eric W. Weisstein, « Herschel Graph », MathWorld.
  4. (en) Eric W. Weisstein, « Goldner-Harary Graph », MathWorld.
  5. (en) Eric W. Weisstein, « Shortness Exponent », MathWorld.
  6. (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,‎ 1962, p. 152–160 (DOI 10.1112/jlms/s1-37.1.152).
  7. (en) A. J. W. Duijvestijn, « The number of polyhedral (3-connected planar) graphs », Mathematics of Computation, vol. 65,‎ 1996, p. 1289–1293 (DOI 10.1090/S0025-5718-96-00749-1).

Lien externe[modifier | modifier le code]

(en) Eric W. Weisstein, « Polyhedral Graph », MathWorld