Cours Graphes
Vocabulaire des graphes orientés
Lancer le programme
Accède gratuitement à cette vidéo pendant 7 jours Profite de ce cours et de tout le programme de ta classe avec l'essai gratuit de 7 jours !

Fiche de cours

Vocabulaire des graphes orientés

 

On considère dans la suite le graphe orienté suivant :

 

graphe_orienté_1

 

Vocabulaire

 

Un graphe orienté est un graphe dans lequel chaque arête a un sens. 

Une arête s'appelle alors un arc.

Une boucle est un arc pour lequel l'événement de départ et l'événement d'arrivée sont identiques : on part de l'événement et on revient sur lui même. 

Un chemin est une chaîne formée d'arcs, en respectant le sens des flèches, comme par exemple $ABED$. Un chemin peut être fermé, comme par exemple $ADCA$. 

Un circuit est un chemin fermé pour lequel chaque arc est utilisé exactement une fois : on ne passe pas deux fois au même endroit et tous les arcs sont différents.

 

Matrice associée

 

On peut également représenter le graphe sous forme d'une matrice.

On voyage des lignes vers les colonnes et on indique par un 1 si il existe un arc liant les deux sommets et par un

Il reste 70% de cette fiche de cours à lire
Cette fiche de cours est réservée uniquement à nos abonnés. N'attends pas pour en profiter, abonne-toi sur lesbonsprofs.com. Tu pourras en plus accéder à l'intégralité des rappels de cours en vidéo ainsi qu'à des QCM et des exercices d'entraînement avec corrigé en texte et en vidéo.