Graphes, matrices d'adjacence et marches aléatoires — exercices corrigés
Un graphe est formé de sommets reliés par des arêtes. Il modélise des réseaux : amis sur un réseau social, villes reliées par des routes, pages web reliées par des liens. Son ordre est le nombre de sommets, et le degré d'un sommet est le nombre d'arêtes qui en partent ; la somme des degrés vaut toujours le double du nombre d'arêtes. On code un graphe par sa matrice d'adjacence AA, et les puissances AnAⁿ comptent les chemins de longueur nn. Quand on circule au hasard sur un graphe, on obtient une marche aléatoire, décrite par une matrice de transition PP : la répartition après nn étapes vaut π0Pnπ₀Pⁿ, et elle se stabilise souvent vers un état stable ππ tel que πP=ππ P=π.
Mis à jour le
À connaître avant de commencer
Degrés
La somme des degrés d'un graphe non orienté vaut deux fois le nombre d'arêtes.
Matrice d'adjacence
aij=1aᵢⱼ=1 s'il y a une arête de ii vers jj, 00 sinon. Graphe non orienté : matrice symétrique.
Chemins
Le coefficient (i,j)(i,j) de AnAⁿ est le nombre de chemins de longueur nn de ii à jj.
Marche aléatoire
πn+1=πnPπₙ₊₁=πₙP ; état stable : πP=ππ P=π, avec la somme des coefficients de ππ égale à 11.
Les exercices, du plus simple au plus difficile
Cherche d'abord, puis clique sur « Voir la correction » : chaque étape est détaillée.
1
Ordre et degrés
Niveau 1 · Application directe
Un graphe a pour sommets AA, BB, CC, DD et pour arêtes ABAB, ACAC, BCBC, CDCD. Donner son ordre et le degré de chaque sommet.
La matrice d'adjacence d'un graphe orienté est-elle forcément symétrique ?
✓Voir la correction+
1.
Un arc de ii vers jj n'implique pas d'arc de jj vers ii.
Réponse : Non.
11
Le terme diagonal de A²
Niveau 2 · Méthode complète
Dans un graphe non orienté sans boucle, que vaut le coefficient (i,i)(i,i) de A2A² ?
✓Voir la correction+
1.
Il compte les chemins de longueur 22 de ii à ii : aller vers un voisin et revenir.
Réponse : Le degré du sommet ii.
12
Un pas de marche aléatoire
Niveau 2 · Méthode complète
Un graphe probabiliste à deux états 11 et 22 a pour matrice P=(0,80,30,20,7)P= 0,8 0,2 ; 0,3 0,7. On part de l'état 11. Donner la répartition après une étape.
✓Voir la correction+
1.
π0=(10)π₀=(1 0), donc π1=π0Pπ₁=π₀P est la première ligne de PP.
Réponse : (0,80,2)(0,8 0,2)
13
Deux étapes
Niveau 2 · Méthode complète
Avec la même matrice, calculer la répartition après deux étapes.
Réponse : 22 (faire le tour du triangle dans un sens ou dans l'autre).
17
L'état stable
Niveau 3 · Type contrôle
Déterminer l'état stable π=(ab)π=(a b) de la marche précédente.
✓Voir la correction+
1.
πP=ππ P=π donne 0,8a+0,3b=a0,8a+0,3b=a, soit 0,2a=0,3b0,2a=0,3b. Avec a+b=1a+b=1 : 0,2a=0,3(1−a)⟺0,5a=0,30,2a=0,3(1-a)⇔0,5a=0,3.
Réponse : π=(0,60,4)π=(0,6 0,4)
18
La météo
Niveau 3 · Type contrôle
S'il fait beau, il fait beau le lendemain avec la probabilité 0,90,9 ; s'il pleut, il fait beau le lendemain avec la probabilité 0,50,5. Déterminer l'état stable.
Réponse : π=(6561)π=(5/6 1/6) : il fait beau 55 jours sur 66 en moyenne.
19
Marche sur un triangle
Niveau 3 · Type contrôle
Un pion part du sommet AA d'un triangle ABCABC. À chaque étape, il va vers l'un des deux autres sommets, au hasard. Quelle est la probabilité qu'il soit en AA après deux étapes ?
✓Voir la correction+
1.
Après une étape, il est en BB ou en CC ; de là, il revient en AA avec la probabilité 211/2.
Réponse : 211/2
20
Les sommets de degré impair
Niveau 4 · Type brevet/bac
Démontrer que, dans tout graphe, le nombre de sommets de degré impair est pair.
✓Voir la correction+
1.
La somme de tous les degrés est paire (elle vaut deux fois le nombre d'arêtes).
2.
La somme des degrés pairs est paire ; donc la somme des degrés impairs l'est aussi, ce qui exige un nombre pair de termes impairs.
Réponse : Le nombre de sommets de degré impair est pair.
Questions fréquentes
Qu'est-ce que le degré d'un sommet ?+
Le nombre d'arêtes qui partent de ce sommet. La somme des degrés vaut deux fois le nombre d'arêtes.
Comment écrire la matrice d'adjacence d'un graphe ?+
On numérote les sommets, puis on écrit 11 à la ligne ii, colonne jj, s'il existe une arête de ii vers jj, et 00 sinon.
Comment compter les chemins de longueur n ?+
On calcule AnAⁿ : son coefficient (i,j)(i,j) donne le nombre de chemins de longueur nn de ii à jj.
Qu'est-ce qu'un état stable ?+
Une répartition ππ qui ne change plus d'une étape à l'autre : πP=ππ P=π. On la trouve en résolvant ce système avec la condition que la somme des coefficients vaut 11.
Les graphes sont-ils au programme de Terminale ?+
Oui, dans l'option maths expertes, avec les marches aléatoires et les matrices.