Graphe cycle

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

Graphe cycle
${\displaystyle C_{8}}$
Notation	${\displaystyle C_{n}}$
Nombre de sommets	${\displaystyle n}$
Nombre d'arêtes	${\displaystyle 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

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 un problème car il s'oppose normalement à graphe acyclique.

Propriétés fondamentales

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

Aspects algébriques

Le graphe cycle ${\displaystyle 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 ${\displaystyle C_{n}}$. De là découlent l'arête-transitivité et la sommet-transitivité. ${\displaystyle 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 ${\displaystyle C_{n}}$. Le groupe d'automorphismes du graphe cycle ${\displaystyle C_{n}}$ est donc isomorphe à celui des isométries du polygone régulier à n sommets, à savoir le groupe diédral ${\displaystyle D_{n}}$, groupe d'ordre 2n^[2].

Le graphe cycle ${\displaystyle C_{n}}$ est un graphe de Cayley^[3] avec :

${\displaystyle G={\frac {\mathbb {Z} }{n{\mathbb {Z} }}}}$ et ${\displaystyle S=\{1,n-1\}}$

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

Cas particuliers

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

Galerie

• 
  ${\displaystyle C_{3}}$
• 
  ${\displaystyle C_{4}}$
• 
  ${\displaystyle C_{5}}$
• 
  ${\displaystyle C_{6}}$

Références

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

• Portail des mathématiques
• Portail de l'informatique théorique