Dans un graphe orienté, on appelle circuit une suite d'arcs consécutifs (chemin) dont les deux sommets extrémités sont identiques. Si le chemin est élémentaire, c'est-à-dire ne passe pas deux fois par un même sommet, on parle de circuit élémentaire. Un circuit élémentaire ne contient pas d'autre circuit. Dans un circuit élémentaire, le degré des sommets est deux.
Dans les graphes pondérés, le poids d'un circuit est la somme des poids des arcs qu'il contient. Si ce poids est négatif, on parle de circuit absorbant.
La notion correspondante dans les graphes non orientés est celle de cycle.
Cet article écrit par ces auteurs est issu de Wikipédia et est conforme aux termes de la GFDL.
Catégorie : Graphe
Page imprimée jeudi 17 mai 2012 à partir de l'url :
« http://www.science-et-vie.net/definition-circuit-graphe-177.html »
Site déclaré à la Commission Nationale de l'Informatique et des Libertés (CNIL) sous le n°871314
© 2002-2012 www.science-et-vie.net
