Graphe prismatique

Un article de Wikipédia, l'encyclopédie libre.

En théorie des graphes, un graphe prismatique ou graphe de prisme est un graphe qui correspond au squelette d'un prisme.

Exemples[modifier | modifier le code]

Les graphes prismatiques sont des exemples de graphes de Petersen généralisés, avec des paramètres GP( n ,1). Ils sont aussi notés . Les graphes sont nommés d'après le solide associé :


Y3 = GP(3,1)

Y4 = Q3 = GP(4,1)

Y5 = GP(5,1)

Y6 = GP(6,1)

Y7 = GP(7,1)

Y8 = GP(8,1)

Les polygones étoilés, forment géométriquement aussi les faces d'une suite de polyèdres prismatiques (auto-sécants et non convexes) ; les graphes de ces prismes étoilés sont isomorphes aux graphes prismatiques et ne forment pas une suite séparée de graphes.

Construction[modifier | modifier le code]

Les graphes prismatiques sont des exemples de graphes de Petersen généralisés, avec des paramètres GP( n ,1). Ils peuvent également être construits comme le produit cartésien d'un graphe cycle avec une seule arête[1].

Comme de nombreux graphes sommet-transitifs, les graphes prismatiques peuvent également être construits comme des graphes de Cayley. Le groupe diédral d'ordre n est le groupe de symétries d'un polygone régulier de taille n dans le plan ; le groupe agit sur le polygone par rotations et réflexions. Il peut être engendré par deux éléments, une rotation d'un angle de et une seule réflexion, et son graphe de Cayley avec cet ensemble de générateurs est le graphe prismatique. De manière abstraite, le groupe a la présentation (où r est une rotation et f est une réflexion ou un retournement) et le graphe de Cayley a r et f (ou r, r − 1 et f ) comme générateurs[1].

Les graphes de prismes polygonaux avec des valeurs impaires de n peuvent être construits comme des graphes circulants . Cette construction ne s'applique pas les valeurs paires de n[1].

Le graphe d'un prisme polygonal possède 2 n sommets et 3 n arêtes. Ce sont des graphes réguliers cubiques. Puisque le prisme a des symétries envoyant chaque sommet sur tout autre sommet, les graphes prismatiques sont des graphes sommet-transitifs. En tant que graphes polyédriques, ce sont également de graphes planaires 3-sommets-connexes. Chaque graphe prismatique possède un cycle hamiltonien[2].

Parmi tous les graphes cubiques biconnexes, les graphes prismatiques ont, à un facteur constant près, le plus grand nombre possible de 1-factorisations. Une 1-factorisation est une partition de l'ensemble des arêtes du graphe en trois couplages parfaits ou, de manière équivalente, une coloration des arêtes du graphe avec trois couleurs. Chaque graphe cubique à n sommets biconnexe possède 1-factorisations, et les graphes prismatiques ont 1-factorisations[3].

Le nombre d'arbres couvrants d'un graphe de prisme de taille n est donné par la formule[4] :

Pour n = 3, 4, 5, ... ces nombres sont

75, 384, 1805, 8100, 35287, 150528, ...( suite A006235 de l'OEIS).

Les graphes prismatiques de polygones de taille n sont des cubes partiels. Ils forment l'une des rares familles infinies connues de graphes cubiques partiels et, à l'exception de quatre exemples sporadiques, ce sont les seuls cubes partiels cubiques sommet-transitifs[5].

Le prisme pentagonal est l'un des mineur exclus pour les graphes de largeur arborescente égale à 3. Le prisme triangulaire et le graphe cubique ont une largeur d'arbre exactement égale à 3, et tous les graphes prismatiques plus grands ont une largeur d'arbre 4[6].

Graphes associés[modifier | modifier le code]

D'autres suites infinies de graphes polyédriques formés de manière similaire à partir de polyèdres avec une base de polygones réguliers sont les graphes graphes d'antiprismes, les graphes roues (graphes de pyramides). D'autres graphes polyédriques sommet-transitifs incluent les graphes d'Archimède .

Si les deux cycles d'un graphe prismatique sont ouverts par la suppression d'une seule arête à la même position dans les deux cycles, le résultat est un graphe en échelle . Si ces deux arêtes supprimées sont remplacées par deux arêtes croisées, le résultat est un graphe non planaire appelé échelle de Möbius[7].

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

  1. a b et c (en) Eric W. Weisstein, « Prism graph », sur MathWorld.
  2. Ronald C. Read et Robin J. Wilson, An Atlas of Graphs, Oxford University Press, (ISBN 9780198526506),  Chapitre 6 : Special Graphs, p. 261 et 260.
  3. David Eppstein, « The complexity of bendless three-dimensional orthogonal graph drawing », Journal of Graph Algorithms and Applications, vol. 17, no 1,‎ , p. 35–55 (DOI 10.7155/jgaa.00283, MR 3019198, arXiv 0709.4087). Eppstein attribue l'observation que les graphes prismatiques ont un nombre de 1-factorizations proche du maximum à une communication personnelle de Greg Kuperberg.
  4. A. A. Jagers, « A note on the number of spanning trees in a prism graph », International Journal of Computer Mathematics, vol. 24, no 2,‎ , p. 151–154 (DOI 10.1080/00207168808803639).
  5. Tilen Marc, « Classification of vertex-transitive cubic partial cubes », Journal of Graph Theory, vol. 86, no 4,‎ , p. 406–421 (ISSN 0364-9024, DOI 10.1002/jgt.22134, arXiv 1509.04565).
  6. Stefan Arnborg, Andrzej Proskurowski et Derek G. Corneil, « Forbidden minors characterization of partial 3-trees », Discrete Mathematics, vol. 80, no 1,‎ , p. 1–19 (DOI 10.1016/0012-365X(90)90292-P, MR 1045920).
  7. Richard K. Guy et Frank Harary, « On the Möbius ladders », Canadian Mathematical Bulletin, vol. 10,‎ , p. 493–496 (DOI 10.4153/CMB-1967-046-4, MR 0224499).