Circuit (théorie des graphes)
Pour les articles homonymes, voir Circuit.
Cet article est une ébauche concernant les mathématiques et l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Dans un graphe orienté, on appelle circuit une suite d'arcs consécutifs (chemin) dont les deux sommets extrémités sont identiques. La notion correspondante dans les graphes non orientés est celle de cycle. On parle parfois de cycle orienté.
Un circuit constitué d'un seul arc est une boucle.
Circuits élémentaires et absorbants
[modifier | modifier le code]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. 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.
