Un prof de maths qui te répond·30 €/mois

Découvrir
MathLvlMon espace
20 exercices corrigés · Maths expertes

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 A, et les puissances Aⁿ comptent les chemins de longueur n. Quand on circule au hasard sur un graphe, on obtient une marche aléatoire, décrite par une matrice de transition P : la répartition après n étapes vaut π₀Pⁿ, et elle se stabilise souvent vers un état stable π tel que π 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

aᵢⱼ=1 s'il y a une arête de i vers j, 0 sinon. Graphe non orienté : matrice symétrique.

Chemins

Le coefficient (i,j) de Aⁿ est le nombre de chemins de longueur n de i à j.

Marche aléatoire

πₙ₊₁=πₙP ; état stable : π P=π, avec la somme des coefficients de π égale à 1.

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 A, B, C, D et pour arêtes AB, AC, BC, CD. Donner son ordre et le degré de chaque sommet.
Voir la correction
  1. 1.
    On compte les arêtes qui touchent chaque sommet.
Réponse : Ordre 4 ; degrés A:2, B:2, C:3, D:1.
2

La somme des degrés

Niveau 1 · Application directe
Vérifier, sur ce graphe, que la somme des degrés vaut le double du nombre d'arêtes.
Voir la correction
  1. 1.
    2+2+3+1=8 et il y a 4 arêtes.
Réponse : 8=2×4
3

Connexe ?

Niveau 1 · Application directe
Ce graphe est-il connexe ?
Voir la correction
  1. 1.
    On peut aller de tout sommet à tout autre : D est relié à C, lui-même relié à A et B.
Réponse : Oui.
4

Une matrice de transition

Niveau 1 · Application directe
Pourquoi la somme de chaque ligne d'une matrice de transition vaut-elle 1 ?
Voir la correction
  1. 1.
    La ligne i donne les probabilités d'aller vers chaque sommet depuis i : ces événements forment une partition.
Réponse : Parce que, depuis un sommet, on va forcément quelque part.
5

Le degré maximal

Niveau 1 · Application directe
Dans un graphe simple d'ordre n, quel est le degré maximal d'un sommet ?
Voir la correction
  1. 1.
    Un sommet peut être relié au plus aux n-1 autres.
Réponse : n-1
6

Un graphe impossible

Niveau 2 · Méthode complète
Existe-t-il un graphe à 5 sommets de degrés 3, 3, 2, 2, 1 ?
Voir la correction
  1. 1.
    La somme vaut 11, qui est impaire ; or elle doit valoir le double du nombre d'arêtes.
Réponse : Non.
7

Le graphe complet

Niveau 2 · Méthode complète
Combien d'arêtes possède le graphe complet à 5 sommets ?
Voir la correction
  1. 1.
    Chaque sommet est de degré 4 : somme 20, soit 10 arêtes.
Réponse : 10 arêtes.
8

Des poignées de mains

Niveau 2 · Méthode complète
Six personnes se réunissent ; chacune serre la main d'exactement trois autres. Combien de poignées de mains ont lieu ?
Voir la correction
  1. 1.
    Somme des degrés 6×3=18, donc 9 arêtes.
Réponse : 9
9

La matrice d'adjacence

Niveau 2 · Méthode complète
Écrire la matrice d'adjacence du graphe de l'exercice 1 (ordre A, B, C, D).
Voir la correction
  1. 1.
    On met 1 pour chaque arête, dans les deux sens.
Réponse : 0 1 1 0 ; 1 0 1 0 ; 1 1 0 1 ; 0 0 1 0
10

Graphe orienté

Niveau 2 · Méthode complète
La matrice d'adjacence d'un graphe orienté est-elle forcément symétrique ?
Voir la correction
  1. 1.
    Un arc de i vers j n'implique pas d'arc de j vers i.
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) de A² ?
Voir la correction
  1. 1.
    Il compte les chemins de longueur 2 de i à i : aller vers un voisin et revenir.
Réponse : Le degré du sommet i.
12

Un pas de marche aléatoire

Niveau 2 · Méthode complète
Un graphe probabiliste à deux états 1 et 2 a pour matrice P= 0,8 0,2 ; 0,3 0,7. On part de l'état 1. Donner la répartition après une étape.
Voir la correction
  1. 1.
    π₀=(1 0), donc π₁=π₀P est la première ligne de P.
Réponse : (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.
Voir la correction
  1. 1.
    π₂=π₁P=(0,8×0,8+0,2×0,3 0,8×0,2+0,2×0,7).
Réponse : (0,70 0,30)
14

Interpréter l'état stable

Niveau 2 · Méthode complète
Les états 1 et 2 représentent « client de la marque » et « client d'une autre marque ». Interpréter l'état stable (0,6 0,4).
Voir la correction
  1. 1.
    À long terme, la répartition se stabilise.
Réponse : À long terme, environ 60 % des clients achètent la marque.
15

Chemins de longueur 2

Niveau 3 · Type contrôle
Dans le graphe de l'exercice 1, combien y a-t-il de chemins de longueur 2 de A à D ?
Voir la correction
  1. 1.
    Il faut un sommet relié à A et à D : seul C convient.
Réponse : 1 (le chemin A→ C→ D).
16

Le triangle

Niveau 3 · Type contrôle
Pour le graphe triangle K₃, calculer A² et A³. Combien y a-t-il de chemins de longueur 3 d'un sommet à lui-même ?
Voir la correction
  1. 1.
    A²= 2 1 1 ; 1 2 1 ; 1 1 2, A³= 2 3 3 ; 3 2 3 ; 3 3 2.
Réponse : 2 (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 π=(a b) de la marche précédente.
Voir la correction
  1. 1.
    π P=π donne 0,8a+0,3b=a, soit 0,2a=0,3b. Avec a+b=1 : 0,2a=0,3(1-a)⇔0,5a=0,3.
Réponse : π=(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,9 ; s'il pleut, il fait beau le lendemain avec la probabilité 0,5. Déterminer l'état stable.
Voir la correction
  1. 1.
    P= 0,9 0,1 ; 0,5 0,5. 0,1a=0,5b et a+b=1 : 0,1a=0,5(1-a)⇔0,6a=0,5.
Réponse : π=(5/6 1/6) : il fait beau 5 jours sur 6 en moyenne.
19

Marche sur un triangle

Niveau 3 · Type contrôle
Un pion part du sommet A d'un triangle ABC. À chaque étape, il va vers l'un des deux autres sommets, au hasard. Quelle est la probabilité qu'il soit en A après deux étapes ?
Voir la correction
  1. 1.
    Après une étape, il est en B ou en C ; de là, il revient en A avec la probabilité 1/2.
Réponse : 1/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. 1.
    La somme de tous les degrés est paire (elle vaut deux fois le nombre d'arêtes).
  2. 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 1 à la ligne i, colonne j, s'il existe une arête de i vers j, et 0 sinon.
Comment compter les chemins de longueur n ?
On calcule Aⁿ : son coefficient (i,j) donne le nombre de chemins de longueur n de i à j.
Qu'est-ce qu'un état stable ?
Une répartition π qui ne change plus d'une étape à l'autre : π P=π. On la trouve en résolvant ce système avec la condition que la somme des coefficients vaut 1.
Les graphes sont-ils au programme de Terminale ?
Oui, dans l'option maths expertes, avec les marches aléatoires et les matrices.

Besoin de revoir le cours avant de t'entraîner ?

Tout sur matrices et graphes en maths expertes

Opérations sur les matrices, inverse, applications aux suites, graphes et marches aléatoires.