- 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 Cn constitué d'un cycle élémentaire de longueur n.
Catégorie : Concept en théorie des graphes
Wikimedia Foundation. 2010.