↩ Chapitre : Graphes et chaînes de Markov (ECG)
Introduction
Douze exercices corrigés sur les graphes (ECG1) et les chaînes de Markov (ECG2), chapitres propres aux maths appliquées, de difficulté croissante : degrés et formule d’Euler, matrice d’adjacence, nombre de chemins de longueur donnée, connexité, matrice de transition, évolution de la loi et loi invariante.
Avant de commencer
Revoir la formule d’Euler (la somme des degrés vaut deux fois le nombre d’arêtes), l’interprétation du coefficient
de
comme nombre de chemins de longueur
de
à
, et, pour les chaînes de Markov, la relation
où
est la loi de
écrite en ligne.
Exercices
Exercice 1 · Degrés et formule d’Euler ★★★
On considère le graphe non orienté
de sommets
et d’arêtes
,
,
,
,
,
.
- Donner le degré de chaque sommet.
- Vérifier la formule d’Euler.
- Le graphe est-il connexe ?
Corrigé
,
,
,
,
.- La somme des degrés vaut
, et le graphe a
arêtes : on a bien
. Chaque arête est comptée deux fois, une fois à chacune de ses extrémités. - La chaîne
complétée par l’arête
relie tous les sommets : il existe une chaîne entre deux sommets quelconques, le graphe est connexe.
Exercice 2 · Conséquences de la formule d’Euler ★★★
- Montrer que dans un graphe non orienté, le nombre de sommets de degré impair est pair.
- Sept personnes peuvent-elles se serrer la main de sorte que chacune serre exactement trois mains ?
- Combien d’arêtes possède le graphe complet
à
sommets ?
Corrigé
est pair. La somme des degrés pairs est paire, donc la somme des degrés impairs est paire : il y a un nombre pair de termes impairs.- On modélise par un graphe : les personnes sont les sommets, les poignées de main les arêtes. On aurait
sommets de degré
, impair, en nombre impair : c’est impossible. - Dans
, chaque sommet est de degré
, donc
et
.
Exercice 3 · Matrice d’adjacence d’un graphe ★★★
Écrire la matrice d’adjacence
du graphe
de l’exercice 1. Quelles propriétés a-t-elle ? Comment lire les degrés sur
?
Corrigé
Avec
si
est une arête,
sinon :
.
Le graphe étant non orienté,
est symétrique ; il n’a pas de boucle, donc la diagonale est nulle. La somme des coefficients de la ligne
est le nombre de voisins de
, c’est-à-dire
: on retrouve
.
Exercice 4 · Graphe défini par sa matrice ★★★
Soit
.
- Justifier que
est la matrice d’adjacence d’un graphe non orienté sans boucle, et le décrire. - Donner le nombre d’arêtes et le degré de chaque sommet. Le graphe est-il connexe ?
Corrigé
est symétrique, à coefficients dans
et de diagonale nulle. Les arêtes sont
,
,
,
et
: c’est un cycle
.- Chaque ligne contient deux
: tous les sommets sont de degré
, et
arêtes. Le cycle passe par tous les sommets : le graphe est connexe.
Exercice 5 · Compter des chemins avec les puissances de A ★★★
Soit
le graphe de sommets
et d’arêtes
,
,
,
, de matrice d’adjacence
.
- Écrire
et calculer
et
. - Combien y a-t-il de chaînes de longueur
de
à
? Les écrire. - Interpréter la diagonale de
.
Corrigé
,
,
.- Le coefficient
de
vaut
: il y a
chaînes de longueur
de
à
. Ce sont les chaînes
,
,
et
.
compte les chaînes
, une par voisin
de
: c’est
. On lit bien
.
Exercice 6 · Traces de A² et A³ ★★★
Soit
un graphe non orienté sans boucle à
sommets et
arêtes, de matrice d’adjacence
.
- Montrer que
. - Montrer que
vaut six fois le nombre de triangles de
. - Vérifier sur le graphe de l’exercice 5.
Corrigé
, donc
par la formule d’Euler.
compte les chaînes fermées
de longueur
. Sans boucle,
,
,
sont distincts et forment un triangle. Un triangle
fournit
telles chaînes partant de chacun de ses
sommets (deux sens de parcours), soit
au total dans la trace.
et
: un seul triangle,
.
Exercice 7 · Connexité et matrice d’adjacence ★★★
Soit
un graphe à
sommets, de matrice d’adjacence
.
- Montrer que s’il existe une chaîne entre deux sommets distincts
et
, il en existe une de longueur au plus
. - En déduire que
est connexe si et seulement si tous les coefficients de
sont strictement positifs. - Application :
a pour sommets
et pour arêtes
et
.
Corrigé
- Prenons une chaîne de longueur minimale de
à
. Si elle passait deux fois par le même sommet, on pourrait supprimer la boucle intermédiaire et obtenir une chaîne plus courte. Ses sommets sont donc distincts : elle en a au plus
, donc au plus
arêtes.
est le nombre de chaînes de longueur
de
à
, et
. Le coefficient
de la somme est strictement positif si et seulement s’il existe une chaîne de longueur au plus
de
à
, c’est-à-dire, par la question 1, une chaîne quelconque. D’où l’équivalence.- On trouve
: le coefficient
est nul, aucune chaîne ne relie
à
, le graphe n’est pas connexe.
Exercice 8 · Chemins dans un graphe orienté ★★★
On considère le graphe orienté de sommets
dont les arcs sont
,
et
.
- Écrire sa matrice d’adjacence
. Est-elle symétrique ? - Calculer
et
. - Pour
, combien y a-t-il de chemins de longueur
de
à
?
Corrigé
. Elle n’est pas symétrique : il y a un arc de
vers
mais pas de
vers
.
et
.- Par division euclidienne
, on a
. Le coefficient
de
vaut
si
et
sinon : il y a exactement un chemin (le tour du cycle, répété
fois) lorsque
est multiple de
, aucun sinon.
Exercice 9 · Chaîne de Markov à deux états ★★★
Chaque jour, le temps est beau (état
) ou pluvieux (état
). S’il fait beau, il fait beau le lendemain avec probabilité
; s’il pleut, il pleut le lendemain avec probabilité
. On note
la probabilité qu’il fasse beau le jour
.
- Écrire la matrice de transition
(états dans l’ordre
,
). - Montrer que
. - En déduire
en fonction de
, puis la limite de
. - Vérifier que
est une loi invariante :
.
Corrigé
: chaque ligne est une loi de probabilité.- Par la formule des probabilités totales sur le temps du jour
:
. - Le point fixe
vérifie
, soit
. La suite
est géométrique de raison
:
. Comme
,
, quelle que soit la situation initiale.
.
Exercice 10 · Loi invariante d’une chaîne à trois états ★★★
Une chaîne de Markov
sur les états
a pour matrice de transition
, avec
.
- Dessiner le graphe probabiliste associé.
- Déterminer la loi de
et celle de
. - Déterminer les lois invariantes
, c’est-à-dire telles que
et
.
Corrigé
- Sommets
; boucles de poids
sur chaque sommet ; arcs
de poids
,
et
de poids
,
de poids
.
,
, puis
.
s’écrit
,
et
, soit
et
(la deuxième équation est alors automatique). Avec
:
, d’où l’unique loi invariante
.
Exercice 11 · Puissances d’une matrice de transition ★★★
Soient
et
. On pose
et
.
- Vérifier que
,
,
,
et
. - En déduire
pour tout
. - Déterminer la limite de
et l’interpréter.
Corrigé
, puis
. Le calcul direct donne
, d’où
; de même
, et les produits
et
sont nuls.- Par récurrence,
: c’est vrai pour
car
, et si c’est vrai au rang
,
. - Comme
,
, donc
et
. Les deux lignes de
sont égales à
: quelle que soit la loi initiale, la loi de
converge vers cette loi, qui est l’unique loi invariante de la chaîne. Avec
et
, on retrouve
de l’exercice 9.
Exercice 12 · Marche aléatoire sur un graphe ★★★
Soit
un graphe non orienté connexe, sans boucle, à
sommets et
arêtes. Un marcheur se déplace sur les sommets : à chaque étape, il quitte le sommet
pour l’un des
voisins de
, choisi au hasard de façon équiprobable.
- Écrire le coefficient
de la matrice de transition
. - Montrer que
est une loi invariante. - Application au graphe de l’exercice 1.
Corrigé
si
est une arête, et
sinon. Le graphe étant connexe, chaque sommet a au moins un voisin, donc
.- Les
sont positifs et de somme
par la formule d’Euler :
est une loi. Pour tout sommet
,
. - Degrés
et
:
. À long terme, le marcheur passe plus de temps sur les sommets les plus reliés : c’est une première mesure de centralité.
Pour aller plus loin
Besoin d’aide sur ce chapitre ?
Un blocage sur une notion, une méthode de rédaction à acquérir, un devoir ou un concours à préparer : Pr. Elakili, agrégé de mathématiques depuis 1991, plus de 20 ans d’enseignement en classes préparatoires, propose des cours particuliers, en présentiel à Casablanca ou en ligne.

,
,
.
: le coefficient
. Elle n’est pas symétrique : il y a un arc de
et