Vocabulaire des graphes orientés et pondérés

Terminale générale Spé · Option Mathématiques Expertes

À retenir

• Graphe orienté : des sommets et des arcs fléchés ; une boucle relie un sommet à lui-même. • Graphe pondéré : chaque arc porte un poids, nombre réel positif. • Matrice d'adjacence : a_i,j = nombre d'arcs (ou poids) de i vers j, 0 sinon ; ligne = départ, colonne = arrivée. • Le coefficient (i, j) de A^n compte les chemins de longueur n de i vers j.

Le cours

1. Graphe orienté Un graphe orienté est formé de sommets et d'arcs : un arc va d'un sommet de départ vers un sommet d'arrivée (flèche). Un arc qui part d'un sommet et y revient est une boucle. L'ordre du graphe est son nombre de sommets. Un chemin de longueur n est une suite de n arcs consécutifs, chacun partant du sommet d'arrivée du précédent ; un chemin qui revient à son point de départ est un circuit. 2. Graphe pondéré et matrice d'adjacence Un graphe est pondéré lorsque chaque arc porte un nombre réel positif, son poids (distance, coût, probabilité…). Les sommets étant numérotés de 1 à k, la matrice d'adjacence est la matrice carrée A = (a_i,j) d'ordre k où a_i,j est le nombre d'arcs (ou le poids de l'arc) allant de i vers j, et 0 s'il n'y en a pas. La ligne i décrit les départs de i, la colonne j les arrivées en j. nombre de chemins de longueur n de i vers j = coefficient (i, j) de A^n 3. Méthode : lire ou écrire la matrice 1. Fixer l'ordre des sommets, le même pour les lignes et les colonnes. 2. Pour chaque sommet i, remplir la ligne i avec les arcs qui en partent (boucle sur la diagonale). 3. Contrôler : le nombre de coefficients non nuls est le nombre d'arcs (graphe sans arcs multiples). 4. Attention Dans un graphe orienté, la matrice d'adjacence n'est en général pas symétrique : un arc de 1 vers 2 n'entraîne pas d'arc de 2 vers 1. Dans un graphe non orienté, au contraire, a_i,j = a_j,i.

Dans ce chapitre