Graphe cycle

 Ne doit pas être confondu avec Graphe des cycles ni Cycle (théorie des graphes).

Graphe cycle
C8
Notation	Cn
Nombre de sommets	n
Nombre d'arêtes	n
Distribution des degrés	2-régulier
Diamètre	n / 2
Propriétés	Hamiltonien Eulérien Planaire Distance-unité Symétrique Graphe de Cayley
modifier

Les graphes cycles, ou n-cycles, forment une famille de graphes. Le graphe cycle C_n est constitué d'un unique cycle élémentaire de longueur n (pour $n \geq 3$). 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].

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 C_n est égal à 3 si n est impair, à 2 sinon. En d'autres termes, C_n est biparti si et seulement si n est pair.
• Connexité. Par construction C_n 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 C_n est un cycle hamiltonien. Le graphe est donc hamiltonien.
• Planarité. C_n est un graphe planaire.
• Eulérien. Étant 2-régulier, le cycle C_n est eulérien par le théorème d'Euler-Hierholzer.
• Line graph. Le line graph (en) de C_n est isomorphe à C_n.

Aspects algébriques

Le graphe cycle C_n peut être dessiné comme un polygone régulier à n sommets. Les isométries de ce polygone s'avèrent alors êtres des automorphismes de C_n. De là découlent l'arête-transitivité et la sommet-transitivité. C_n 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 C_n. Le groupe d'automorphisme du graphe cycle C_n est donc isomorphe à celui des isométries du polygone régulier à n sommets, à savoir le groupe diédral D_n, groupe d'ordre 2n^[2].

Le graphe cycle C_n est un graphe de Cayley^[3] avec :

$G = {\frac {\mathbb Z}{n {\mathbb Z}}}$

S = {1,n − 1}

Cas particuliers

• C₃ est le graphe triangle.
• C₄ est le graphe carré, il est isomorphe à l'hypercube Q₃ ou a la grille G(2,2).
• C₆ est isomorphe au graphe de Kneser KG_3,1.

Galerie

• 

  C₃

• 

  C₄

• 

  C₅

• 

  C₆

Références

1. ↑ Eric W. Weisstein, Cycle Graph at MathWorld.
2. ↑ Kenneth H. Rosen, John G. Michaels. Handbook of Discrete and Combinatorial Mathematics. CRC Press, 2000.
3. ↑ In theory: Characters and Expansion by Luca Trevisan