ULUMINE · Mathématiques expertes · Terminale
Graphes et matrices d’adjacence
Un graphe modélise un réseau ; sa matrice d’adjacence A permet de compter les chaînes de longueur n grâce à Aⁿ.
Vocabulaire
- Ordre : nombre de sommets ; degré : nombre d’arêtes issues d’un sommet.
- Somme des degrés = 2 × nombre d’arêtes.
- Complet d’ordre n : arêtes.
Chaînes
- Longueur : nombre d’arêtes.
- Cycle : chaîne fermée à arêtes distinctes.
- Connexe : tout couple de sommets relié par une chaîne.
Matrice d’adjacence
- aij : nombre d’arêtes de i à j ; symétrique si non orienté.
- Coefficient (i, j) de Aⁿ : chaînes de longueur n de i à j.
Pièges à éviter
- La longueur d’une chaîne compte les arêtes, pas les sommets.
- Dans un graphe orienté, la matrice n’est pas symétrique : respecter le sens ligne → colonne.
- Fixer l’ordre des sommets avant d’écrire la matrice.