Cycle (graphe)

Un article de Wikipédia, l'encyclopédie libre.

Dans un graphe non orienté, on appelle cycle 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 d'arêtes on l'appelle naturellement un cycle impair. Cette notion joue un rôle fondamental.

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.

La notion correspondante dans les graphes orientés est celle de circuit.