Fiche de cours Logimaths | Terminale maths expertes
Fiche de cours : Graphes
Des points et des liens : le vocabulaire, la matrice, puis les marches aléatoires
I. Le vocabulaire des graphes
Sommets, arêtes, degré
Un graphe est un ensemble de sommets reliés par des arêtes (réseau social, plan de métro, molécule…).
Le degré d'un sommet est le nombre d'arêtes qui en partent. Deux sommets reliés sont adjacents. Un graphe est complet si tous les sommets sont deux à deux adjacents, connexe si on peut relier n'importe quels sommets par une chaîne.
Version orientée : les liens deviennent des flèches (sens unique).
Le degré d'un sommet est le nombre d'arêtes qui en partent. Deux sommets reliés sont adjacents. Un graphe est complet si tous les sommets sont deux à deux adjacents, connexe si on peut relier n'importe quels sommets par une chaîne.
Version orientée : les liens deviennent des flèches (sens unique).
Le lemme des poignées de main
La somme des degrés de tous les sommets vaut 2 × (nombre d'arêtes) (chaque arête est comptée à ses deux extrémités).
Conséquence élégante : le nombre de sommets de degré impair est toujours pair : impossible de dessiner un graphe avec exactement trois sommets de degré 3.
Conséquence élégante : le nombre de sommets de degré impair est toujours pair : impossible de dessiner un graphe avec exactement trois sommets de degré 3.
🎮 Entraîne-toi : les poignées de main
Somme des degrés = 2 × nombre d'arêtes, dans les deux sens.
🎮 Entraîne-toi : lire un graphe
Compte les arêtes qui touchent le sommet demandé.
II. La matrice d'adjacence
Du dessin au tableau
La matrice d'adjacence M d'un graphe à n sommets numérotés est la matrice n × n où m_{ij} = 1 si une arête relie i à j (0 sinon) ; pour un graphe orienté, m_{ij} = 1 signifie une flèche de i vers j.
Un graphe non orienté donne une matrice symétrique, avec des 0 sur la diagonale (pas de boucle) ; le degré d'un sommet est la somme de sa ligne.
Un graphe non orienté donne une matrice symétrique, avec des 0 sur la diagonale (pas de boucle) ; le degré d'un sommet est la somme de sa ligne.
Compter les chemins avec les puissances
Le coefficient (i ; j) de M^k donne le nombre de chemins de longueur k allant de i à j.
Idée de la preuve pour k = 2 : le coefficient (i ; j) de M² additionne m_{i1}m_{1j} + m_{i2}m_{2j} + \dots : chaque terme vaut 1 exactement quand le sommet intermédiaire correspondant fait passer de i à j en deux étapes.
Idée de la preuve pour k = 2 : le coefficient (i ; j) de M² additionne m_{i1}m_{1j} + m_{i2}m_{2j} + \dots : chaque terme vaut 1 exactement quand le sommet intermédiaire correspondant fait passer de i à j en deux étapes.
🎮 Entraîne-toi : les chemins de longueur 2
Compte les sommets-relais : i → relais → j.
III. Les marches aléatoires
Matrice de transition
Une marche aléatoire sur un graphe (2 ou 3 états au programme) est décrite par une matrice de transition dont les coefficients sont les probabilités de passage d'un état à l'autre.
L'état probabiliste à l'étape n est une matrice U_n, et U_{n+1} = U_n A (convention en ligne) ou U_{n+1} = AU_n (convention en colonne, celle qu'on utilise ici) : chaque énoncé précise la sienne, toujours vérifier que les probabilités sortantes somment à 1.
L'état probabiliste à l'étape n est une matrice U_n, et U_{n+1} = U_n A (convention en ligne) ou U_{n+1} = AU_n (convention en colonne, celle qu'on utilise ici) : chaque énoncé précise la sienne, toujours vérifier que les probabilités sortantes somment à 1.
État stable
Un état V est stable si AV = V : la répartition ne bouge plus. Sous de bonnes hypothèses (au programme : constatées sur les exemples), la suite des états U_n = A^n U_0 converge vers l'état stable, quel que soit le point de départ.
Exemple rédigé : deux enseignes
Chaque année, 80 % des clients de l'enseigne X y restent (20 % partent chez Y) et 70 % des clients de Y y restent. Matrice (convention colonne) : A = \begin{pmatrix} 0{,}8 & 0{,}3 \\ 0{,}2 & 0{,}7 \end{pmatrix}.
État stable : AV = V donne {0{,}8x + 0{,}3y = x}, soit 0{,}3y = 0{,}2x : avec x + y = 100, on trouve x = 60, y = 40 : à long terme, 60 % des clients chez X.
État stable : AV = V donne {0{,}8x + 0{,}3y = x}, soit 0{,}3y = 0{,}2x : avec x + y = 100, on trouve x = 60, y = 40 : à long terme, 60 % des clients chez X.
🎮 Entraîne-toi : l'étape suivante
Nouveau contenu de 1 = (part qui reste dans 1) + (part qui arrive de 2).
IV. Les pièges et les réflexes
⚠️ Ligne ou colonne : la convention change tout
Selon les manuels, la matrice de transition se lit « ligne = départ » (et alors U_{n+1} = U_n A avec U en ligne) ou « colonne = départ » (U_{n+1} = AU_n avec U en colonne). Le test qui sauve : les probabilités qui partent d'un même état somment à 1 : repère si c'est vrai sur les lignes ou sur les colonnes.
Les trois réflexes du chapitre
- compter des arêtes ou vérifier un dessin : poignées de main ;
- compter des chemins en k étapes : puissance k de la matrice d'adjacence ;
- comportement à long terme d'une marche aléatoire : état stable AV = V avec la contrainte x + y (+ z) = 1 (ou 100 %).
👆 ▶ À toi : un graphe a des sommets de degrés 3, 3, 2, 2, 2. Combien d'arêtes ? Vérifie
Somme des degrés = 12, donc 12 : 2 = 6 arêtes (et le nombre de sommets impairs, ici 2, est bien pair).