Terminale · Mathématiques

Comprendre la matrice d'adjacence : lire, écrire et interpréter un réseau orienté

Écrire la matrice d'adjacence d'un graphe orienté à partir de son dessin, relire un graphe depuis sa matrice, et interpréter le coefficient de A^k comme un nombre de chemins de longueur k.

Aperçu gratuit
Illustration de la fiche « Comprendre la matrice d'adjacence : lire, écrire et interpréter un réseau orienté »

Les points essentiels

  • Un graphe orienté est un couple formé de sommets et d'arcs : un arc relie un sommet de départ à un sommet d'arrivée, et le sens compte.
  • La matrice d'adjacence A est carrée d'ordre n, avec n le nombre de sommets, une fois fixé un ordre des sommets (par exemple alphabétique).

Les mots à connaître

Matrice d'adjacence
Pour un graphe orienté dont les sommets sont ordonnés 1, 2, ..., n, c'est la matrice carrée A de taille n×n dont le coefficient a_ij est le nombre d'arcs allant du sommet i au sommet j (0 ou 1 s'il n'y a pas d'arcs multiples).
Chemin de longueur k
Dans un graphe orienté, suite de k arcs consécutifs : le premier arc part du sommet de départ, chaque arc suivant part de l'arrivée du précédent, et le dernier arrive au sommet d'arrivée. Le nombre d'arcs parcourus est la longueur.

Un exemple pour comprendre

Un graphe orienté a trois sommets A, B, C et les arcs A→B, A→C, B→C, C→A. Écrire sa matrice d'adjacence (ordre A, B, C) puis donner le nombre d'arcs sortants de chaque sommet.

Ligne A : arcs vers B et C, donc (0 1 1). Ligne B : arc vers C seulement, donc (0 0 1). Ligne C : arc vers A seulement, donc (1 0 0). La matrice est A = [[0,1,1],[0,0,1],[1,0,0]]. Les sommes de lignes donnent les arcs sortants : A en a 2, B en a 1, C en a 1, soit 4 arcs au total, ce qui correspond bien aux quatre arcs de l'énoncé. Les sommes de colonnes donnent les arcs entrants : A 1, B 1, C 2.

Première page de l’Essentiel : Comprendre la matrice d'adjacence : lire, écrire et interpréter un réseau orienté
Ketty