Graphe cycle

Graphe cycle
$C_{8}$

Notation	$C_{n}$
Nombre de sommets	$n$
Nombre d'arêtes	$n$
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
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[modifier | modifier le code]

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[modifier | modifier le code]

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 cycle 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 de $C_{n}$ est isomorphe à $C_{n}$ .

Aspects algébriques[modifier | modifier le code]

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'automorphismes 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} }}}

et

S=\{1,n-1\}

Le polynôme caractéristique de la matrice d'adjacence du graphe cycle $C_{n}$ est $\prod _{k=0}^{n-1}(x-2\cos(2k\pi /n))$ (dont toutes les racines sont doubles sauf 2 et éventuellement -2).

Cas particuliers[modifier | modifier le code]

$C_{3}$ est le graphe triangle.
$C_{4}$ est le graphe carré, il est isomorphe à l'hypercube $Q_{3}$ ou a la grille G(2,2).
$C_{6}$ est isomorphe au graphe de Kneser $KG_{3,1}$ .

Galerie[modifier | modifier le code]

$C_{3}$
$C_{4}$
$C_{5}$
$C_{6}$

Références[modifier | modifier le code]

↑ (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

[1] (en) Eric W. Weisstein, « Cycle Graph », sur 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

[1]

[2]

[3]