Au programme de ce chapitre
- I. Vocabulaire des graphes
- II. Matrice d'adjacence
- III. Puissances de la matrice d'adjacence et chemins
- Savoir-faire
- Exercices types corrigés
- Teste-toi — vrai ou faux ?
- Pièges fréquents et astuces
- À retenir
La définition à retenir
Définition Un graphe est constitué d'un ensemble de sommets et d'un ensemble d'arêtes reliant certains sommets entre eux. Un graphe est non orienté si les arêtes n'ont pas de sens privilégié, orienté sinon (on parle alors d'arcs). Le degré d'un sommet, dans un graphe non orienté, est le nombre d'arêtes qui lui sont incidentes. Un graphe est pondéré si chaque arête porte un nombre appelé poids.
🔒 Infographie récapitulative du chapitreIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
Un exemple corrigé
Exemple Considérons un graphe à quatre sommets A, B, C, D avec les arêtes AB, AC, BC, BD, CD (donc pas d'arête AD). Dans l'ordre A, B, C, D, sa matrice d'adjacence est M = [[0,1,1,0],[1,0,1,1],[1,1,0,1],[0,1,1,0]]. Les degrés des sommets sont 2 (A), 3 (B), 3 (C), 2 (D), et la somme des degrés vaut 10, soit deux fois le nombre d'arêtes (5).
Les erreurs fréquentes à éviter
Piège. Dans un graphe orienté, la matrice d'adjacence n'est pas forcément symétrique (arc i→j ≠ j→i).
L'astuce du prof
Astuce. Les puissances M^k comptent les chemins de longueur k : un outil puissant pour analyser un graphe.
Exercices corrigés
Cherche d'abord seul, puis ouvre la correction.
Exercice 1
Que vaut M[i][j] dans une matrice d'adjacence ?
Voir la correction
1 si les sommets i et j sont reliés par une arête, 0 sinon.
Exercice 2
À quoi sert M² (le carré de la matrice d'adjacence) ?
Voir la correction
Son coefficient (i,j) donne le nombre de chemins de longueur 2 entre i et j.