Graphe cycle
Les graphes cycles, ou n-cycles, forment une famille de graphes. Le graphe cycle est constituĂ© d'un unique cycle Ă©lĂ©mentaire de longueur n (pour ). C'est un graphe connexe non-orientĂ© d'ordre n Ă n arĂȘtes. Il est 2-rĂ©gulier, c'est-Ă -dire que chacun de ses sommets est de degrĂ© 2[1].
Graphe cycle | |
![]() | |
Notation | |
---|---|
Nombre de sommets | |
Nombre d'arĂȘtes | |
Distribution des degrés | 2-régulier |
DiamĂštre | n/2 si n pair (n â 1)/2 sinon |
Propriétés | Hamiltonien Eulérien Planaire Distance-unité Symétrique Graphe de Cayley |
Terminologie
Beaucoup de termes sont employés pour désigner le graphe cycle : n-cycle, polygone et n-gone. Le terme de graphe cyclique est parfois employé, mais il pose problÚme car il s'oppose normalement à graphe acyclique.
Propriétés fondamentales
- Nombre chromatique. Le nombre chromatique du cycle est Ă©gal Ă 3 si n est impair, Ă 2 sinon. En d'autres termes, est biparti si et seulement si n est pair.
- ConnexitĂ©. Par construction est connexe. Il est facile de constater qu'il est 2-sommet-connexe (c'est-Ă -dire qu'il cesse d'ĂȘtre connexe uniquement quand on lui supprime 2 sommets). Il est Ă©galement 2-arĂȘte-connexe.
- Hamiltonicité. L'unique cycle contenu dans est un cycle hamiltonien. Le graphe cycle est donc hamiltonien.
- Planarité. est un graphe planaire.
- EulĂ©rien. Ătant 2-rĂ©gulier, le cycle est eulĂ©rien par le thĂ©orĂšme d'Euler-Hierholzer.
- Line graph. Le line graph de est isomorphe Ă .
Aspects algébriques
Le graphe cycle peut ĂȘtre dessinĂ© comme un polygone rĂ©gulier Ă n sommets. Les isomĂ©tries de ce polygone s'avĂšrent alors ĂȘtres des automorphismes de . De lĂ dĂ©coulent l'arĂȘte-transitivitĂ© et la sommet-transitivitĂ©. est donc un graphe symĂ©trique. Tous ses sommets et toutes ses arĂȘtes jouent le mĂȘme rĂŽle en termes d'isomorphisme de graphe.
Il est facile de constater que seules les isométries de ce polygone sont des automorphismes valides de . Le groupe d'automorphismes du graphe cycle est donc isomorphe à celui des isométries du polygone régulier à n sommets, à savoir le groupe diédral , groupe d'ordre 2n[2].
Le graphe cycle est un graphe de Cayley[3] avec :
- et
Le polynÎme caractéristique de la matrice d'adjacence du graphe cycle est (dont toutes les racines sont doubles sauf 2 et éventuellement -2).
Cas particuliers
- est le graphe triangle.
- est le graphe carré, il est isomorphe à l'hypercube ou a la grille G(2,2).
- est isomorphe au graphe de Kneser .
Galerie
Références
- (en) Eric W. Weisstein, « Cycle Graph », sur MathWorld
- Kenneth H. Rosen, John G. Michaels. Handbook of Discrete and Combinatorial Mathematics. CRC Press, 2000.
- In theory: Characters and Expansion by Luca Trevisan