Maths expertes · Terminale · Graphes et matrices
Graphes et matrices
Une puissance compte des chemins.
En bref
Un graphe se range dans une matrice — et cette traduction met un outil de calcul au service d’une question de parcours.
Le vocabulaire
| Terme | Sa définition |
|---|---|
| Graphe | Des sommets reliés par des arêtes (non orienté) ou des arcs (orienté) |
| Pondéré | Chaque lien porte un nombre |
| Connexe | Deux sommets quelconques sont reliés par une chaîne |
| Degré | Le nombre d’arêtes d’un sommet |
La matrice d’adjacence
Pour un graphe à n sommets numérotés, le coefficient (i ; j) de M vaut 1 s’il existe une arête de i vers j, 0 sinon.
| Le graphe est… | La matrice est… |
|---|---|
| Non orienté | Symétrique |
| Orienté | En général non symétrique |
Le résultat central
Le coefficient (i ; j) de Mᵏ donne le nombre de chemins de longueur exactement k allant de i à j.
C’est le théorème du chapitre : il transforme un dénombrement de parcours en un calcul de puissance.
| La question | Le calcul |
|---|---|
| Chemins de longueur exactement k | Le coefficient de Mᵏ |
| Chemins de longueur au plus k | La somme M + M² + … + Mᵏ |
| Le graphe est-il connexe ? | La somme I + M + … + Mⁿ⁻¹ n’a aucun coefficient nul |
Chaînes eulériennes et hamiltoniennes
| Eulérienne | Hamiltonienne | |
|---|---|---|
| Elle emprunte une fois | Chaque arête | Chaque sommet |
| Le critère | Graphe connexe et 0 ou 2 sommets de degré impair (théorème d’Euler) | Aucun critère simple |
| Si 0 sommet impair | Il existe même un cycle eulérien | — |
L’absence de critère hamiltonien est ce qui rend le problème du voyageur de commerce difficile.
La coloration
Le nombre chromatique est le plus petit nombre de couleurs permettant de colorer les sommets sans que deux sommets adjacents partagent une couleur.
| Encadrement | Sa valeur |
|---|---|
| Majorant | Le degré maximal, plus 1 |
| Minorant | La taille du plus grand sous-graphe complet |
Applications : planning d’examens sans conflit, allocation de fréquences, coloriage de cartes.
Les usages
Réseaux de transport, réseaux sociaux, ordonnancement de tâches, circuits, moteurs de recherche — l’algorithme originel de Google classe les pages par une puissance itérée de matrice.
Une puissance de matrice compte des chemins. C’est le seul résultat à retenir, et presque toujours celui que l’énoncé demande d’appliquer.
Teste-toi
6 questions pour vérifier
Touche une réponse : la correction s’affiche tout de suite.
1.Que représente le coefficient (i ; j) de Mᵏ, M étant la matrice d’adjacence ?
2.Pour un graphe non orienté, la matrice d’adjacence est…
3.À quelle condition un graphe connexe possède-t-il une chaîne eulérienne ?
4.Qu’est-ce qu’une chaîne hamiltonienne ?
5.Comment compte-t-on les chemins de longueur au plus k ?
6.Qu’est-ce que le nombre chromatique d’un graphe ?
0 / 6 questions
Dans l’app, ce chapitre a son quiz complet, chronométré, et tes erreurs reviennent au bon moment pour ne plus les refaire.
La fiche de révision, sur une page
Tout « Graphes et matrices » sur une seule page A4 illustrée : l’essentiel, les pièges et un mini-test. Elle se débloque dans l’app avec des gemmes — et ton compte gratuit en offre assez pour tes trois premières fiches.
