Cage (théorie des graphes)

graphe régulier minimal pour une maille donnée
(Redirigé depuis Cage (graphe))

En théorie des graphes, une cage est un graphe régulier minimal pour une maille donnée. Plus précisément, une (r,g)-cage est un graphe régulier minimal de degré r et de maille g.

Quand le terme de g-cage est employé, il s'agit en fait d'une cage cubique, c'est-à-dire d'une (3,g)-cage.

Cages connuesModifier

Un graphe degré-un n'a pas de cycle, et un graphe degré-deux connexe a une circonférence égale à son nombre de sommets, donc les cages ne présentent un intérêt que pour r ≥ 3. La (r,3)-cage est un graphe complet Kr+1 sur r+1 sommets, et la (r,4)-cage est un graphe biparti complet Kr,r sur 2r sommets.

D'autres cages notables incluent les graphiques de Moore :

Le nombre de sommets dans les cages connues (r,g), pour les valeurs de r > 2 et g > 2, autres que les plans projectifs et les polygones généralisés, sont :

g
r
3 4 5 6 7 8 9 10 11 12
3 4 6 10 14 24 30 58 70 112 126
4 5 8 19 26 67 80 728
5 6 10 30 42 170 2730
6 7 12 40 62 312 7812
7 8 14 50 90

Notes et référencesModifier

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