Réseau routier, réseau social, plan de métro, liens entre pages web : tous ces réseaux se modélisent par des graphes, formés de points (sommets) reliés par des lignes (arêtes). En codant un graphe par une matrice, on peut compter les chemins d’une longueur donnée par un simple calcul de puissance.
Une question sur ce cours ?
ULU, le tuteur d’ULUMINE, t’aide à partir de ce cours.
Objectifs
- Connaître le vocabulaire des graphes (ordre, degré, graphe complet, orienté)
- Utiliser la relation entre la somme des degrés et le nombre d’arêtes
- Reconnaître une chaîne, un cycle, un graphe connexe
- Écrire la matrice d’adjacence d’un graphe et interpréter ses puissances
1. Vocabulaire
Graphe : Un graphe non orienté est formé de sommets et d’arêtes reliant deux sommets. Son ordre est le nombre de sommets. Deux sommets reliés par une arête sont adjacents.
- Le degré d’un sommet est le nombre d’arêtes qui en partent.
- Un graphe est complet si deux sommets distincts quelconques sont adjacents. Le graphe complet d’ordre n a arêtes.
- Dans un graphe orienté, les arêtes sont des arcs munis d’un sens (flèches).
2. Chaînes, cycles, connexité
- Une chaîne est une suite de sommets dans laquelle deux sommets consécutifs sont adjacents. Sa longueur est son nombre d’arêtes.
- Une chaîne fermée revient à son point de départ ; un cycle est une chaîne fermée dont les arêtes sont toutes distinctes.
- Un graphe est connexe si deux sommets quelconques peuvent être reliés par une chaîne.
- Dans un graphe orienté, on parle de chemins (on suit le sens des arcs).
3. Matrice d’adjacence
Matrice d’adjacence : Les sommets étant numérotés de 1 à n, la matrice d’adjacence A est la matrice carrée d’ordre n dont le coefficient aij est le nombre d’arêtes (ou d’arcs) reliant i à j.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 1 | 0 |
| C | 1 | 1 | 0 | 1 |
| D | 0 | 0 | 1 | 0 |
- Graphe non orienté : la matrice est symétrique.
- Sans boucle, la somme des coefficients d’une ligne est le degré du sommet.
Chaînes de longueur 2 dans le graphe ci-dessus
- Coefficient (C, C) de A² : ligne C × colonne C = 1 + 1 + 0 + 1 = 3.
- Ce sont C–A–C, C–B–C et C–D–C.
Sur la diagonale de A², on lit les degrés des sommets.
À retenir
- Somme des degrés = 2 × nombre d’arêtes.
- Graphe complet d’ordre n : arêtes, chaque sommet de degré n − 1.
- Matrice d’adjacence : aij = nombre d’arêtes entre i et j ; symétrique si non orienté.
- Le coefficient (i, j) de Aⁿ compte les chaînes de longueur n de i à j.
Et maintenant, à toi !
Vérifie que tu as compris avec les exercices, puis révise avec la fiche.