MATHS EXPERTES
Les graphes
Vocabulaire, chaînes eulériennes, matrice d’adjacence, plus court chemin et graphes probabilistes.
NOTION
Vocabulaire des graphes
Un graphe est formé de sommets reliés par des arêtes (ou des arcs s’il est orienté). Son ordre est le nombre de sommets.
Le degré d’un sommet est le nombre d’arêtes qui y arrivent.
$\displaystyle\sum_{\text{sommets}}\deg(s)=2\times(\text{nombre d’arêtes})$
💡 Chaque arête compte deux fois : une pour chacune de ses extrémités. Donc le nombre de sommets de degré impair est toujours pair.
NOTION
Chaînes, connexité, distance
Une chaîne de longueur $k$ relie deux sommets en passant par $k$ arêtes. Un cycle est une chaîne fermée.
Un graphe est connexe si deux sommets quelconques sont reliés par une chaîne.
La distance entre deux sommets est la longueur de la plus courte chaîne ; le diamètre est la plus grande distance.
THÉORÈME
Chaînes eulériennes
Une chaîne eulérienne passe une fois et une seule par chaque arête. Pour un graphe connexe (théorème d’Euler) :
0 sommet de degré impair $\iff$ il existe un cycle eulérien.
2 sommets de degré impair $\iff$ il existe une chaîne eulérienne (non fermée), qui relie ces deux sommets.
⚠️ Au-delà, impossible : c’est le problème des sept ponts de Königsberg (quatre sommets de degrés impairs $3,3,3,5$).
NOTION
Matrice d’adjacence
Pour un graphe d’ordre $n$, la matrice d’adjacence $M$ est $n\times n$ : $m_{ij}$ est le nombre d’arêtes (ou d’arcs) de $i$ vers $j$.
Graphe non orienté : $M$ est symétrique, et la somme d’une ligne est le degré du sommet.
Triangle $ABC$ : $M=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}$.
ANIMATION
Un graphe et sa matrice
Choisissez deux sommets et une longueur $k$ : le coefficient de $M^k$ compte les chaînes. Le bouton retire l’arête B–C : que dit alors le théorème d’Euler ?
THÉORÈME
Compter les chaînes avec $M^k$
Le coefficient $(i\,;j)$ de $M^k$ est le nombre de chaînes de longueur $k$ allant de $i$ à $j$.
Triangle : $M^2=\begin{pmatrix}2&1&1\\1&2&1\\1&1&2\end{pmatrix}$.
$2$ chaînes de longueur $2$ de $A$ à $A$ : $A\!-\!B\!-\!A$ et $A\!-\!C\!-\!A$. Et $1$ de $A$ à $B$ : $A\!-\!C\!-\!B$.
MÉTHODE
Plus court chemin : algorithme de Dijkstra
Graphe pondéré : $A\!-\!B:4$, $A\!-\!C:2$, $C\!-\!B:1$, $B\!-\!D:5$, $C\!-\!D:8$. Plus court chemin de $A$ à $D$ ?
Départ : $A=0$. Voisins : $B=4$, $C=2$. On fixe le plus petit : $C\,(2)$.
Depuis $C$ : $B=\min(4\,;2+1)=3$ et $D=2+8=10$. On fixe $B\,(3)$.
Depuis $B$ : $D=\min(10\,;3+5)=8$. On fixe $D\,(8)$.
✅ Plus court chemin : $A\to C\to B\to D$, de poids $2+1+5=8$.
NOTION
Graphes probabilistes
Un graphe probabiliste décrit un système qui passe d’un état à un autre avec des probabilités (somme des arcs sortants $=1$).
$P=\begin{pmatrix}0{,}9&0{,}1\\0{,}3&0{,}7\end{pmatrix}\qquad\pi_{n+1}=\pi_n\,P$
$\pi_n=\pi_0\,P^n$ : la probabilité d’être dans chaque état à l’étape $n$.
SIMULATION
Vers un état stable
Deux états $A$ et $B$ : modifiez les probabilités de passage et la situation de départ.
THÉORÈME
État stable
Un état $\pi$ est stable si $\pi P=\pi$ (et la somme de ses coefficients vaut $1$).
Avec $P=\begin{pmatrix}0{,}9&0{,}1\\0{,}3&0{,}7\end{pmatrix}$ et $\pi=(x\,;1-x)$ : $0{,}9x+0{,}3(1-x)=x\iff0{,}3=0{,}4x$, soit $x=0{,}75$.
$\pi=(0{,}75\ ;\ 0{,}25)$
💡 Pour deux états avec $A\to B$ de probabilité $p$ et $B\to A$ de probabilité $q$ : $\pi=\left(\dfrac q{p+q}\ ;\ \dfrac p{p+q}\right)$. La suite $\pi_n$ converge vers $\pi$.
QUESTION FLASH
Somme des degrés
Un graphe a $7$ arêtes. Quelle est la somme des degrés de ses sommets ?
Chaque arête compte pour $2$ dans la somme des degrés : $2\times7=14$.
QUESTION FLASH
Théorème d’Euler
Un graphe connexe a exactement $2$ sommets de degré impair. Que peut-on affirmer ?
Avec exactement deux sommets de degré impair, il existe une chaîne eulérienne reliant ces deux sommets. Un cycle exigerait $0$ sommet de degré impair.
QUESTION FLASH
Que compte $M^3$ ?
Que représente le coefficient $(i\,;j)$ de la matrice $M^3$ ?
Le coefficient $(i\,;j)$ de $M^k$ est le nombre de chaînes de longueur $k$ de $i$ à $j$.
DÉFI
Nombre d’arêtes
Un graphe a $5$ sommets de degrés $3,3,2,2,2$. Combien a-t-il d’arêtes ?
💡 Additionnez les degrés, puis divisez par $2$.
$3+3+2+2+2=12$ et $12\div2=6$ arêtes.
DÉFI
Un état stable
On considère $P=\begin{pmatrix}0{,}8&0{,}2\\0{,}3&0{,}7\end{pmatrix}$. Quelle est la première coordonnée de l’état stable $\pi=(x\ ;\ 1-x)$ ? (écrire un décimal)
💡 Résolvez $0{,}8x+0{,}3(1-x)=x$.
$0{,}8x+0{,}3-0{,}3x=x\iff0{,}3=0{,}5x\iff x=0{,}6$. (Formule : $\dfrac q{p+q}=\dfrac{0{,}3}{0{,}5}$.)
✓
Chapitre terminé
Vous avez revu le vocabulaire des graphes, le théorème d’Euler, les matrices d’adjacence, Dijkstra et les graphes probabilistes.
Score : 0 / 0
📊 Mon bilan ⚡ Réviser ce chapitre ← Tous les chapitres Accueil MathsMDE