Circuit (graphe)
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
Un graphique avec une boucle sur le sommet 1.
Un graphique avec une boucle sur le sommet 1.

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é (Le mot degré a plusieurs significations, il est notamment employé dans les domaines suivants :) des sommets est deux.

Dans les graphes pondérés, le poids (Le poids est la force de pesanteur, d'origine gravitationnelle et inertielle, exercée par la Terre sur un corps massique en raison uniquement du voisinage de la Terre. Elle est égale à l'opposé de...) 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.

Page générée en 0.031 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique