OffresSe connecter
Terminale › Graphes et matrices › Compter des chemins avec une matrice

Compter des chemins avec une matrice : méthode (Maths expertes)

Méthode

Compter des chemins avec une matrice

  1. Numéroter les sommets et écrire la matrice d'adjacence $M$ (ligne = départ, colonne = arrivée).
  2. Calculer $M^n$, à la main pour $n=2$ ou $3$, à la calculatrice au-delà.
  3. Lire le coefficient ligne « départ », colonne « arrivée ».
  4. Attention : la longueur est le nombre d'arcs, pas le nombre de sommets. Un chemin passant par $5$ sommets (en comptant le départ et l'arrivée) a pour longueur $4$.
Remarque

Connexité et matrice d'adjacence

Dans un graphe non orienté d'ordre $m$, deux sommets distincts reliés par une chaîne le sont par une chaîne de longueur au plus $m-1$. Ainsi, le graphe est connexe si et seulement si tous les coefficients hors diagonale de $M+M^2+\cdots+M^{m-1}$ sont strictement positifs. Ce critère s'utilise en exercice guidé ; il n'est pas exigible.

S’entraîner

Dans le cours

Graphes et matrices : Compter des chemins avec une matrice