Mathématiques expertes (option) · Terminale · Graphes et matrices

Matrice d'adjacence et chemins

• La matrice d'adjacence d'un graphe d'ordre $n$ est un tableau carré $n \times n$ : le coefficient $a_{ij}$ compte les arêtes (ou arcs) de $i$ vers $j$ ; la diagonale compte les boucles.
• Le tableau dépend de l'ordre choisi pour les sommets ; une fois l'ordre fixé, il est unique. Un graphe simple non orienté donne une matrice binaire, symétrique, à diagonale nulle.
• Théorème : le coefficient $(i,j)$ de $A^k$ est le nombre de chemins de longueur $k$ de $i$ à $j$.
• Méthode : numéroter les sommets, écrire $A$, calculer $A^k$ ligne par ligne, lire le coefficient demandé. La somme des coefficients de $A^k$ donne tous les chemins de longueur $k$.