Cycle (Graphe)

Cycle (graphe)

Pour les articles homonymes, voir Cycle.

Dans un graphe non-orienté, un cycle est une suite d'arêtes consécutives (chaîne) dont les deux sommets extrémités sont identiques. Si la chaîne est élémentaire, c'est-à-dire ne passe pas deux fois par un même sommet, alors on parle de cycle élémentaire. Un cycle élémentaire ne contient pas d'autre cycle. Dans un cycle élémentaire, le degré des sommets est deux.

Lorsque que le cycle contient un nombre impair (respectivement pair) d'arêtes on l'appelle un cycle impair (respectivement cycle pair).

Dans les graphes pondérés, le poids d'un cycle est la somme des poids des arêtes qu'il contient. Si ce poids est négatif, on parle de cycle absorbant.

Dans les graphes orientés, la notion équivalente est celle de circuit.

Le graphe cycle

Le terme de cycle désigne parfois le graphe cycle C_n constitué d'un cycle élémentaire de longueur n.

Ce document provient de « Cycle (graphe) ».