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.

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.

