Terminale · Mathématiques

Graphes, matrice d’adjacence et chemins

Savoir modéliser une situation par un graphe, écrire sa matrice d’adjacence, puis utiliser les puissances de cette matrice pour compter des chemins de longueur donnée.

Aperçu gratuit
Illustration de la fiche « Graphes, matrice d’adjacence et chemins »

Les points essentiels

  • Modéliser une situation par un graphe, c’est représenter des objets par des sommets et des liens par des arcs, en tenant compte du sens de parcours si le graphe est orienté.
  • La matrice d’adjacence A d’un graphe orienté à n sommets est une matrice carrée n×n. Son coefficient de ligne i et de colonne j vaut 1 s’il existe un arc du sommet i vers le sommet j, et 0 sinon.

Les mots à connaître

sommet
Élément modélisé par un point du graphe : une ville, une personne, une étape.
arc
Lien orienté allant d’un sommet vers un autre. Dans un graphe non orienté, on parle d’arête.

Un exemple pour comprendre

Un graphe orienté a trois sommets A, B et C. Les arcs sont A→B, B→C et C→A. Écris la matrice d’adjacence A, puis déduis-en le nombre de chemins de longueur 2 allant de A à C.

On numérote les sommets : A = 1, B = 2, C = 3. On place un 1 à chaque arc : A→B donne ligne 1 colonne 2, B→C donne ligne 2 colonne 3, C→A donne ligne 3 colonne 1. Tous les autres coefficients valent 0. A = [0 1 0 ; 0 0 1 ; 1 0 0]. Pour compter les chemins de longueur 2, on calcule A² = A × A. A² = [0 0 1 ; 1 0 0 ; 0 1 0]. On lit le coefficient de la ligne 1 et de la colonne 3 : il vaut 1. Il existe donc exactement un chemin de longueur 2 allant de A vers C : c’est A→B→C.

Première page de l’Essentiel : Graphes, matrice d’adjacence et chemins
Ketty