Cage (théorie des graphes)
Pour les articles homonymes, voir Cage.
Cet article est une ébauche concernant la théorie des graphes.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
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 connues[modifier | modifier le code]
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 :
- (3,5)-cage : Graphe de Petersen, 10 sommets ;
- (3,6)-cage : Graphe de Heawood, 14 sommets ;
- (3,8)-cage : Graphe de Tutte–Coxeter, 30 sommets ;
- (3,10)-cage : 10-cage de Balaban, 70 sommets ;
- (3,11)-cage : 11-cage de Balaban, 112 sommets ;
- (3,12)-cage : 12-cage de Tutte, 126 sommets ;
- (4,5)-cage : Graphe de Robertson, 19 sommets ;
- (7,5)-cage : Graphe de Hoffman-Singleton, 50 sommets ;
- lorsque r − 1 est une puissance première, les cages (r,6) sont les graphes d'incidence des plans projectifs ;
- lorsque r − 1 est une puissance première, les cages (r,8) et (r,12) sont des polygones généralisés (en).
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 |
