Graphes
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteObjectifs du chapitre
- Algorithme de Dijkstra - Étape par étape
- Construire la matrice d'adjacence d'un graphe
- Compter les chaînes d'un graphe avec les puissances de la matrice d'adjacence
- Appliquer le théorème d'Euler à un graphe
- Déterminer le nombre chromatique d'un graphe
- Determiner et utiliser la matrice de transition d'une chaine de Markov
- Determiner l'etat stable d'une chaine de Markov
1. Vocabulaire
Définition
Un graphe est composé de sommets et d'arêtes (ou arcs) reliant certains de ces sommets.
Exemple
Le diagramme ci-dessous représente un graphe comportant 4 sommets et 5 arêtes.
Définition
- L'ordre d'un graphe est le nombre de sommets de ce graphe.
- Le degré d'un sommet est le nombre d'arêtes dont ce sommet est une extrémité.
- Deux sommets reliés par une arête sont adjacents.
Exemple
- Le graphe représenté ci-dessus est d'ordre 4.
- Le degré du sommet B est 3. Celui de C est 4 (la boucle compte 2 fois).
- A et B sont adjacents. A et D ne le sont pas.
Définition
Une chaîne (ou un chemin) est une suite de sommets telle que chaque sommet est relié au suivant par une arête.
La longueur d'une chaîne est le nombre d'arêtes composant cette chaîne.
Exemple
(A; B; C; D) est une chaîne de longueur 3.
Définition
Un cycle est une chaîne fermée (c'est à dire dont l'origine et l'extrémité sont identiques) dont toutes les arêtes sont distinctes.
Exemple
(B; C; C; D; B) est un cycle.
Définition
On dit qu'un graphe est connexe si deux sommets quelconques peuvent être reliés par une chaîne.
Remarque
Intuitivement, cela signifie que le graphe comporte un seul « morceau ».
Exemple
Graphe connexe.
Graphe non connexe.
Définition
Un graphe est complet lorsque deux sommets quelconques distincts sont toujours reliés par une arête (autrement dit : tous les sommets sont deux à deux adjacents).
2. Chaînes et cycles eulériens
Définition
Une chaîne eulérienne est une chaîne qui contient une fois et une seule chacune des arêtes du graphe.
Si cette chaîne est un cycle, on parle de cycle eulérien.
Exemple
(A; B; C; C; D; B) est une chaîne eulérienne.
Ce graphe ne contient aucun cycle eulérien.
Remarque
- Un graphe connexe contient une chaîne eulérienne si et seulement si on peut le tracer « sans lever le crayon ». Le théorème d'Euler (ci-dessous) permet de déterminer facilement ce type de graphe.
- On ne peut jamais tracer un graphe non connexe sans lever le crayon.
Théorème
Théorème d'Euler. Un graphe connexe contient une chaîne eulérienne si et seulement s'il possède 0 ou 2 sommets de degré impair.
Un graphe connexe contient un cycle eulérien si et seulement s'il ne possède aucun sommet de degré impair (autrement dit, tous ses sommets sont de degré pair).
Exemple
Exemple 1
Dans l'exemple 1, il y a deux sommets de degré impair (A:1 et B:3). Le graphe contient une chaîne eulérienne, par exemple (A; B; C; C; D; B) mais pas de cycle eulérien.
Exemple 2
Dans l'exemple 2, il y a deux sommets de degré impair (A:3 et E:3). Le graphe contient une chaîne eulérienne, par exemple (A; F; D; B; F; E; D; C; B; A; E) mais pas de cycle eulérien.
Exemple 3
Dans l'exemple 3, il y a 4 sommets de degré impair (A:3, B:3, D:3 et E:3). Le graphe ne contient pas de chaîne eulérienne.
Exemple 4
Dans l'exemple 4, tous les sommets sont de degré pair . Le graphe contient un cycle eulérien, par exemple: (G; A; H; F; I; C; J; D; K; B; L; E; G; H; I; J; K; L; G).
3. Matrice d'adjacence
Définition
Soit un graphe (orienté ou non) dont les sommets sont numérotés de $1$ à $n$. La matrice d'adjacence $M$ associée à ce graphe est la matrice carrée d'ordre $n$ dont le coefficient situé à la $i$-ème ligne et à la $j$-ème colonne est égal au nombre d'arêtes (ou d'arcs) reliant directement le sommet $i$ au sommet $j$.
Remarque
Pour un graphe non orienté sans boucle ni arête multiple, la matrice d'adjacence ne contient que des $0$ et des $1$ et elle est symétrique : $M_{i,j} = M_{j,i}$.
Une boucle sur un sommet est comptée 2 fois dans le coefficient diagonal correspondant pour un graphe non orienté.
Exemple
Pour le graphe ci-dessous, en classant les sommets dans l'ordre A, B, C, D :
la matrice d'adjacence est :
(la valeur $2$ sur la diagonale provient de la boucle sur le sommet C).
Théorème
Soit $M$ la matrice d'adjacence d'un graphe dont les sommets sont numérotés de $1$ à $n$ et soit $k$ un entier naturel non nul. Alors le coefficient situé à la $i$-ème ligne et à la $j$-ème colonne de la matrice $M^k$ donne le nombre de chaînes de longueur $k$ reliant le sommet $i$ au sommet $j$.
Remarque
Démonstration (par récurrence sur $k$).
Initialisation. Pour $k = 1$, le coefficient $M_{i,j}$ est par définition le nombre d'arêtes reliant directement $i$ à $j$, c'est-à-dire le nombre de chaînes de longueur $1$ entre ces deux sommets. La propriété est vraie au rang $1$.
Hérédité. Supposons que, pour un entier $k \geqslant 1$, le coefficient $\left(M^k\right)_{i,j}$ donne le nombre de chaînes de longueur $k$ reliant $i$ à $j$. Une chaîne de longueur $k+1$ allant de $i$ à $j$ se décompose de façon unique en une chaîne de longueur $k$ allant de $i$ vers un sommet intermédiaire $\ell$, suivie d'une arête reliant $\ell$ à $j$. Pour un sommet $\ell$ fixé, le nombre de telles chaînes est donc le produit $\left(M^k\right)_{i,\ell} \times M_{\ell,j}$. En sommant sur tous les sommets intermédiaires possibles, le nombre total de chaînes de longueur $k+1$ entre $i$ et $j$ vaut :
On reconnaît la formule du produit matriciel : la propriété est donc vraie au rang $k+1$.
Conclusion. D'après le principe de récurrence, pour tout entier $k \geqslant 1$, le coefficient $\left(M^k\right)_{i,j}$ donne le nombre de chaînes de longueur $k$ reliant $i$ à $j$.
Exemple
Avec la matrice $M$ précédente, le coefficient $(M^2)_{2,4}$ donne le nombre de chaînes de longueur $2$ reliant B à D. Sur le graphe, cette chaîne est B-C-D : il y en a une seule.
Pour déterminer le nombre de chaînes de longueur au plus $k$ entre deux sommets, on additionne les coefficients correspondants des matrices $M$, $M^2$, ..., $M^k$.
4. Coloration d'un graphe
Remarque
Notion de culture, hors programme de l'option Mathématiques expertes. Cette section est proposée à titre de complément.
Définition
Colorier un graphe, c'est associer à tout sommet une couleur telle que deux sommets adjacents n'aient pas la même couleur.
Le plus petit nombre de couleurs nécessaire pour colorier un graphe s'appelle le nombre chromatique du graphe.
Exemple
Le graphe ci-dessus a été colorié à l'aide de 3 couleurs différentes. Il n'est pas possible de le colorier avec seulement 2 couleurs. Le nombre chromatique du graphe est donc 3.
Théorème
Le nombre chromatique d'un graphe est inférieur ou égal à $d_{\max}+1$, où $d_{\max}$ est le plus grand degré des sommets.
Le nombre chromatique d'un graphe est supérieur ou égal à l'ordre de tout sous-graphe complet qu'il contient.
Exemple
Dans l'exemple précédent, le plus grand degré est 4. Le nombre chromatique du graphe est donc inférieur ou égal à 5 (on a vu qu'il est en fait égal à 3).
5. Chaînes de Markov
Remarque
Ne pas confondre la matrice d'adjacence (section 3 : ses coefficients sont des entiers comptant des arêtes ou des chemins) et la matrice de transition introduite ci-dessous (ses coefficients sont des probabilités et chaque ligne a pour somme $1$). Ce sont deux objets distincts associés à deux types de graphes différents.
Définition
Une chaîne de Markov à $n$ états est décrite par un graphe probabiliste pondéré : les sommets sont les états possibles et chaque arc, orienté du sommet $i$ vers le sommet $j$, est pondéré par la probabilité de transition de l'état $i$ vers l'état $j$ à chaque étape. Pour chaque sommet, la somme des poids des arcs qui en partent (boucle comprise) est égale à $1$.
Exemple
On étudie l'abonnement à un service de streaming, observé chaque mois. Un client peut être dans l'état $A$ (abonné) ou dans l'état $B$ (non abonné). D'un mois sur l'autre :
- un abonné le reste avec la probabilité $0{,}9$ et se désabonne avec la probabilité $0{,}1$ ;
- un non-abonné s'abonne avec la probabilité $0{,}3$ et le reste avec la probabilité $0{,}7$.
Définition
En numérotant les états de $1$ à $n$, la matrice de transition $P$ de la chaîne est la matrice carrée d'ordre $n$ dont le coefficient $P_{i,j}$ est la probabilité de passer de l'état $i$ à l'état $j$ en une étape.
C'est une matrice stochastique : tous ses coefficients sont compris entre $0$ et $1$ et la somme des coefficients de chaque ligne est égale à $1$.
Exemple
Pour la situation précédente, en classant les états dans l'ordre $A$, $B$ :
La première ligne décrit le devenir d'un abonné ($0{,}9 + 0{,}1 = 1$), la seconde celui d'un non-abonné ($0{,}3 + 0{,}7 = 1$).
Définition
La distribution initiale est le vecteur ligne $\pi_0 = \begin{pmatrix} p_1 & p_2 & \dots & p_n \end{pmatrix}$ donnant la probabilité de se trouver dans chacun des $n$ états au départ (la somme de ses composantes vaut $1$).
La distribution à l'étape $n$ est le vecteur ligne $\pi_n$ donnant la répartition des probabilités entre les états après $n$ étapes.
Théorème
Avec les notations précédentes, pour tout entier naturel $n$ :
Exemple
On suppose qu'au mois $0$ le client est abonné : $\pi_0 = \begin{pmatrix} 1 & 0 \end{pmatrix}$.
Après un mois :
Après deux mois :
en effet $0{,}9 \times 0{,}9 + 0{,}1 \times 0{,}3 = 0{,}84$ et $0{,}9 \times 0{,}1 + 0{,}1 \times 0{,}7 = 0{,}16$. La probabilité que le client soit encore abonné au bout de deux mois est donc $0{,}84$.
Définition
Une distribution invariante (ou état stable) est un vecteur ligne $\pi$ dont les composantes sont positives, de somme égale à $1$, et qui vérifie :
Une telle distribution n'est plus modifiée par une étape de plus : elle décrit le comportement de la chaîne sur le long terme.
Exemple
On cherche la distribution invariante $\pi = \begin{pmatrix} x & y \end{pmatrix}$ de la chaîne précédente. Elle vérifie $\pi = \pi \times P$ et $x + y = 1$.
L'égalité $\begin{pmatrix} x & y \end{pmatrix} = \begin{pmatrix} x & y \end{pmatrix} \begin{pmatrix} 0{,}9 & 0{,}1 \\ 0{,}3 & 0{,}7 \end{pmatrix}$ donne le système :
La première équation s'écrit $0{,}1\,x = 0{,}3\,y$, soit $x = 3y$. En reportant dans $x + y = 1$, on obtient $3y + y = 1$, donc $y = 0{,}25$ puis $x = 0{,}75$.
La distribution invariante est $\mathbf{\pi = \begin{pmatrix} 0{,}75 & 0{,}25 \end{pmatrix}}$ : à long terme, $75\,\%$ des clients sont abonnés et $25\,\%$ ne le sont pas.
Remarque
La deuxième équation du système est toujours redondante avec la première (les lignes de $P$ sommant à $1$). C'est la condition $x + y = 1$ qui permet de conclure : il ne faut jamais l'oublier.
6. Algorithme de Dijkstra
Remarque
Notion de culture, hors programme de l'option Mathématiques expertes. Cette section est proposée à titre de complément.
L'algorithme de Dijkstra (prononcer approximativement « Dextra ») permet de trouver le plus court chemin entre deux sommets d'un graphe pondéré (orienté ou non orienté) dont tous les poids sont positifs.
Le fonctionnement de l'algorithme est généralement présenté sous forme d'un tableau dans lequel chaque ligne représente une étape : on choisit à chaque étape le sommet de plus petite distance non encore traité, puis on met à jour les distances des sommets voisins.
La construction détaillée d'un tel tableau est exposée dans la fiche méthode : Algorithme de Dijkstra - Étape par étape.
Les questions essentielles
1. Comment construire la matrice d'adjacence d'un graphe ?
On numérote les sommets, on crée une matrice carrée d'ordre $n$, et le coefficient $M_{i,j}$ vaut le nombre d'arêtes (ou d'arcs) reliant directement le sommet $i$ au sommet $j$. Pour un graphe non orienté, la matrice est symétrique et une boucle compte $2$ sur la diagonale.
Voir la fiche méthode : Construire la matrice d'adjacence d'un graphe
2. Comment compter le nombre de chaînes de longueur $k$ entre deux sommets ?
On calcule la puissance $M^k$ de la matrice d'adjacence : le coefficient $(M^k)_{i,j}$ donne le nombre de chaînes de longueur exactement $k$ reliant $i$ à $j$. Pour les chaînes de longueur au plus $k$, on additionne les coefficients de $M, M^2, \dots, M^k$.
Voir la fiche méthode : Compter les chaînes d'un graphe avec les puissances de la matrice d'adjacence
3. Comment déterminer l'état stable d'une chaîne de Markov ?
On résout le système formé par l'égalité $\pi = \pi \times P$ (où $P$ est la matrice de transition) à laquelle on adjoint la condition « somme des composantes égale à $1$ ». L'une des équations issues de $\pi = \pi P$ est redondante : c'est la condition de somme qui permet de conclure. À ne pas confondre avec la matrice d'adjacence, dont les coefficients comptent des chemins.
4. Comment savoir si un graphe admet une chaîne ou un cycle eulérien ?
On vérifie d'abord la connexité, puis on compte les sommets de degré impair. S'il y en a $0$, le graphe admet un cycle eulérien ; s'il y en a exactement $2$, il admet une chaîne eulérienne entre ces deux sommets ; sinon, ni l'un ni l'autre.
Voir la fiche méthode : Appliquer le théorème d'Euler à un graphe
5. Comment déterminer le nombre chromatique d'un graphe ?
On l'encadre en utilisant deux résultats : $\chi \leqslant d_{\max} + 1$ (degré maximal) et $\chi \geqslant p$ (ordre du plus grand sous-graphe complet). On cherche ensuite un coloriage explicite atteignant la borne inférieure.
Voir la fiche méthode : Déterminer le nombre chromatique d'un graphe
6. Comment trouver le plus court chemin entre deux sommets d'un graphe pondéré ?
On applique l'algorithme de Dijkstra : on construit un tableau dont chaque ligne correspond à une étape, on sélectionne à chaque étape le sommet de plus petite distance non encore traité, puis on met à jour les distances des sommets voisins.
Voir la fiche méthode : Algorithme de Dijkstra - Étape par étape
7. Comment déterminer et utiliser la matrice de transition d'une chaîne de Markov ?
On reporte dans une matrice carrée les probabilités de passage d'un état à un autre, chaque ligne correspondant à un état de départ et chaque coefficient à la probabilité d'aller vers l'état de la colonne. La somme des coefficients de chaque ligne vaut $1$, et l'on obtient l'état au rang $n$ en multipliant l'état initial par la puissance $n$-ième de cette matrice.
Voir la fiche méthode : Déterminer et utiliser la matrice de transition d'une chaîne de Markov
8. Comment déterminer l'état stable d'une chaîne de Markov ?
On cherche l'état $\pi$ qui ne change plus d'un rang au suivant : il vérifie l'égalité $\pi = \pi \times P$, à laquelle on adjoint la condition « somme des composantes égale à $1$ » pour lever l'indétermination et conclure.
Voir la fiche méthode : Déterminer l'état stable d'une chaîne de Markov