Lessons and exercises follow the school system and stay in its language.Les leçons et les exercices suivent le système scolaire et restent dans sa langue.Lektionen und Übungen folgen dem Schulsystem und bleiben in seiner Sprache.
Tu es hors ligne : les chapitres enregistrés fonctionnent toujours.
Toutes les leçons du thème, de la première année à la dernière, prêtes pour le papier. Les séries d'exercices sont notées A, B, C… et corrigées à la fin.
Pour obtenir un PDF, choisis « Enregistrer au format PDF » dans la fenêtre d'impression.
Nombres et calculs
Graphes et chaînes de Markov
PseudoDate
Scanne pour ouvrir en ligneenglish.sedifier.com/fr/branch/n/grf/print/
1. Graphes : sommets, arêtes, degré, chaînes
Découvrir
Un graphe a 4 sommets, tous reliés deux à deux. Combien a-t-il d'arêtes ?
6
4
L'idée clé
Un graphe modélise des relations.
Figure non à l'échelle
Un graphe est formé de sommets reliés par des arêtes. Son ordre est son nombre de sommets. Le degré d'un sommet est le nombre d'arêtes qui en partent.
Une chaîne est une suite d'arêtes consécutives ; sa longueur est son nombre d'arêtes. Un graphe est connexe si deux sommets sont toujours reliés par une chaîne. La somme des degrés est le double du nombre d'arêtes.
Exemple corrigé
Un graphe a les degrés 3, 3, 2, 2. Combien a-t-il d'arêtes ?
3+3+2+2=10
Somme des degrés.
5 arêtes
Double du nombre d'arêtes.
À toi, guidé
À toi : combien d'arêtes a le graphe complet à 3 sommets ?
3
3 × 2 / 2.
Entraînement ★
Combien d'arêtes le graphe complet d'ordre 3 a-t-il ?
Combien d'arêtes le graphe complet d'ordre 23 a-t-il ?
Combien d'arêtes le graphe complet d'ordre 5 a-t-il ?
Attention !
Entraînement ★★
Un graphe a 3 arêtes. Quelle est la somme des degrés de ses sommets ?
Un graphe a 73 arêtes. Quelle est la somme des degrés de ses sommets ?
Dans un graphe complet d'ordre 5, quel est le degré de chaque sommet ?
La somme des degrés d'un graphe vaut 8. Combien a-t-il d'arêtes ?
Bilan
Trois questions pour vérifier que c'est acquis.
Combien d'arêtes le graphe complet d'ordre 3 a-t-il ?
Combien d'arêtes le graphe complet d'ordre 23 a-t-il ?
Combien d'arêtes le graphe complet d'ordre 5 a-t-il ?
Fiche résumé
Graphes
Ordre : nombre de sommets.
Somme des degrés = 2 × nombre d'arêtes.
Attention : une chaîne se mesure en arêtes.
Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.
Défi ★★★
Un graphe a 6 sommets, tous de degré 3. Combien a-t-il d'arêtes ?
2. Matrice d'adjacence et nombre de chemins
Échauffement
Trois questions rapides sur des leçons déjà vues.
Combien d'arêtes le graphe complet d'ordre 3 a-t-il ?
Un graphe a 3 arêtes. Quelle est la somme des degrés de ses sommets ?
Dans un graphe complet d'ordre 5, quel est le degré de chaque sommet ?
Découvrir
A est la matrice d'adjacence d'un graphe. Que signifie aij=1 ?
Il y a une arête de i vers j
Le sommet i a pour degré 1
L'idée clé
Les puissances de A comptent les chemins.
La matrice d'adjacenceA a pour coefficient aij=1 s'il existe une arête de i vers j, 0 sinon.
Le coefficient (i;j) de An est le nombre de chemins de longueur n reliant i à j.
Exemple corrigé
A=(0111). Combien de chemins de longueur 2 vont de 2 à 2 ?
A2=(1112)
Calcul de A².
2 chemins
Coefficient (2 ; 2).
À toi, guidé
À toi : avec le même A2, combien de chemins de longueur 2 vont de 1 à 1 ?
1
Coefficient (1 ; 1).
Entraînement ★
Pour un graphe, A3=(5629). Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?
Pour un graphe, A3=(3151). Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?
Pour un graphe, A3=(7529). Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?
Attention !
Entraînement ★★
A=(0110). Que vaut le coefficient (1;1) de A2 ?
A=(0210). Que vaut le coefficient (1;1) de A2 ?
A=(0130) compte les arêtes de chaque sommet vers chaque sommet. Combien d'arêtes vont du sommet 1 au sommet 2 ?
La matrice d'adjacence d'un graphe non orienté est toujours :
Symétrique
Diagonale
Inversible
Bilan
Trois questions pour vérifier que c'est acquis.
Pour un graphe, A3=(5629). Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?
Pour un graphe, A3=(3151). Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?
Pour un graphe, A3=(7529). Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?
Fiche résumé
Chemins
Coefficient (i;j) de An : chemins de longueur n de i à j.
Graphe non orienté : A est symétrique.
Attention : la puissance est la longueur.
Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.
Défi ★★★
Un graphe est un triangle (3 sommets, tous reliés). Combien de chemins de longueur 2 partent du sommet 1 et y reviennent ?
3. Chaînes de Markov
Échauffement
Trois questions rapides sur des leçons déjà vues.
Calcule ad−bc pour (3263).
Avec D=(3001), que vaut le coefficient en haut à gauche de D2 ?
La matrice (3162) est-elle inversible ?
Non : son déterminant est nul
Oui : ses coefficients sont non nuls
Oui : toute matrice carrée l'est
Découvrir
Il pleut aujourd'hui. Il pleut demain avec la probabilité 0,6. Quelle est la probabilité qu'il ne pleuve pas demain ?
0,4
0,6
L'idée clé
La probabilité de l'état suivant ne dépend que de l'état présent.
Figure non à l'échelle
La matrice de transitionP a pour coefficient pij la probabilité de passer de i à j. Chaque ligne a pour somme 1.
La distribution après n transitions est πn=π0Pn. Le coefficient (i;j) de Pn est la probabilité d'aller de i à j en n transitions.
Exemple corrigé
P=(0,90,50,10,5) et π0=(10). Calcule π1.
π1=π0P
Ligne × matrice.
π1=(0,90,1)
On lit la première ligne.
À toi, guidé
À toi : dans la même chaîne, que vaut la probabilité d'être dans l'état 2 après une étape, en partant de l'état 2 ?
0,5
Coefficient (2 ; 2).
Entraînement ★
Dans une chaîne à deux états, p11=108. Que vaut p12 ?
Dans une chaîne à deux états, p11=106. Que vaut p12 ?
Dans une chaîne à deux états, p11=107. Que vaut p12 ?
Attention !
Entraînement ★★
P=1051061−1051−106 et π0=(2121). Calcule la première coordonnée de π1.
P=1071041−1071−104 et π0=(2121). Calcule la première coordonnée de π1.
Dans une matrice de transition à deux états, la première ligne est (108;p). Que vaut p ?
Une chaîne reste dans l'état 1 avec la probabilité 105 à chaque pas. Partant de l'état 1, quelle est la probabilité d'y rester deux fois de suite ?
Bilan
Trois questions pour vérifier que c'est acquis.
Dans une chaîne à deux états, p11=108. Que vaut p12 ?
Dans une chaîne à deux états, p11=106. Que vaut p12 ?
Dans une chaîne à deux états, p11=107. Que vaut p12 ?
Fiche résumé
Chaînes de Markov
πn=π0Pn.
Lignes de P : somme 1.
Attention : lis pij de i vers j.
Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.
Défi ★★★
P=1−1091021091−102. On part de l'état 1. Quelle est la probabilité d'être dans l'état 2 après deux étapes ?
4. Distributions invariantes
Échauffement
Trois questions rapides sur des leçons déjà vues.
Dans une chaîne à deux états, p11=108. Que vaut p12 ?
P=1051061−1051−106 et π0=(2121). Calcule la première coordonnée de π1.
Dans une matrice de transition à deux états, la première ligne est (108;p). Que vaut p ?
Découvrir
Une distribution π vérifie πP=π. Que se passe-t-il à l'étape suivante ?
La distribution ne change pas
Elle double
L'idée clé
On cherche π en résolvant un système.
π est invariante si πP=π et si ses coefficients ont pour somme 1.
Exemple corrigé
P=(0,90,50,10,5). Trouve π=(ab).
0,9a+0,5b=a, donc 0,5b=0,1a
Première coordonnée de πP = π.
a=5b, donc 6b=1
a + b = 1.
π=(6561)
Solution.
À toi, guidé
À toi : si a=3b et a+b=1, que vaut b ?
41
4b = 1.
Entraînement ★
On trouve a=3b et a+b=1. Que vaut b ?
On trouve a=29b et a+b=1. Que vaut b ?
On trouve a=2b et a+b=1. Que vaut b ?
Attention !
Entraînement ★★
P=1−1091061091−106. Trouve la première coordonnée a de la distribution invariante.
P=1−1051071051−107. Trouve la première coordonnée a de la distribution invariante.
Comment vérifier qu'une distribution π est invariante pour la matrice de transition P ?
On vérifie que πP=π
On vérifie que Pπ=P
On vérifie que π=1
Une distribution sur deux états s'écrit (106;b). Que vaut b ?
Bilan
Trois questions pour vérifier que c'est acquis.
On trouve a=3b et a+b=1. Que vaut b ?
On trouve a=29b et a+b=1. Que vaut b ?
On trouve a=2b et a+b=1. Que vaut b ?
Fiche résumé
Distribution invariante
πP=π.
Somme des coefficients : 1.
Attention : n'oublie pas la condition de somme.
Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.
Défi ★★★
Dans une chaîne à deux états, p12=51 et p21=91. Quelle est la seconde coordonnée de la distribution invariante ?
5. La distribution invariante d'une chaîne à deux états
Découvrir
Un chat est soit endormi (E), soit éveillé (V). S'il dort, il reste endormi avec probabilité 0,8 ; s'il est éveillé, il s'endort avec probabilité 0,4. À long terme, quelle part du temps dort-il ?
32
0,8
L'idée clé
La distribution invariante d'une chaîne à deux états.
Chaîne à deux états A et B : P(A→B)=p, P(B→A)=q (avec p+q>0). La distribution invariante est
πA=p+qq, πB=p+qp.
Exemple corrigé
p=0,1, q=0,3.
πA=0,40,3
Formule.
πA=0,75, πB=0,25
On calcule.
À toi, guidé
À toi : p=0,5, q=0,5 : πA ?
0,5
10,5.
Entraînement ★
Chaîne à deux états : P(A→B)=0,8 et P(B→A)=0,8. Calcule πA pour la distribution invariante.
Chaîne à deux états : P(A→B)=0,6 et P(B→A)=0,3. Calcule πA pour la distribution invariante.
Chaîne à deux états : P(A→B)=0,1 et P(B→A)=0,8. Calcule πA pour la distribution invariante.
Entraînement ★★
Même chaîne (p=0,8, q=0,2), départ en A. Calcule la probabilité d'être en A après deux pas.
Même chaîne (p=0,5, q=0,2), départ en A. Calcule la probabilité d'être en A après deux pas.
Bilan
Deux questions pour vérifier.
Chaîne à deux états : P(A→B)=0,8 et P(B→A)=0,8. Calcule πA pour la distribution invariante.
Chaîne à deux états : P(A→B)=0,6 et P(B→A)=0,3. Calcule πA pour la distribution invariante.
Fiche résumé
État stable
πA=p+qq.
Ne dépend pas de l'état de départ.
Les algorithmes de classement des pages web utilisent la distribution invariante d'une immense chaîne de Markov.
6. Histoire des graphes : Euler et Markov
Découvrir
La ville de Königsberg avait sept ponts. Peut-on faire une promenade qui traverse chaque pont exactement une fois ? En 1736, Euler répond.
Non, c'est impossible
Oui, en partant du bon endroit
L'idée clé
Des ponts de Königsberg aux chaînes de Markov.
Étape 1Leonhard Euler1707–1783Jakob Emanuel Handmann, 1753. Domaine public1736 : Euler démontre qu'on ne peut pas traverser les sept ponts une seule fois chacun.
Étape 2Andreï Markov1856–1922Auteur inconnu, 1886. Domaine publicMarkov (1856–1922) : chaînes où le futur ne dépend que du présent ; voyelles et consonnes.
En 1736, Euler résout le problème des ponts de Königsberg : un graphe a un chemin passant une fois par chaque arête seulement s'il a 0 ou 2 sommets de degré impair. Andreï Markov (1856–1922) étudie les chaînes qui portent son nom, où le futur ne dépend que du présent ; il les applique aux voyelles et consonnes d'un texte littéraire.
Source
À Königsberg, en Prusse, il y a une île, entourée par deux bras de la rivière, et sept ponts. On demande si quelqu'un peut organiser sa promenade de façon à passer une fois et une seule sur chacun des ponts.
Leonhard Euler, Solutio problematis ad geometriam situs pertinentis, 1736 : le problème qu'il pose, résumé avec nos mots
Qu'est-ce qui compte vraiment pour répondre ?
Quelles rives et îles chaque pont relie, pas les distances
La longueur de chaque pont
Exemple corrigé
Königsberg : quatre zones reliées par sept ponts ; les degrés sont 5, 3, 3 et 3.
4
Sommets de degré impair.
promenade impossible
Plus de 2.
Entraînement ★
À quoi Markov a-t-il appliqué ses chaînes ?
Aux voyelles et consonnes d'un texte littéraire
Aux ponts de Königsberg
Aux moteurs de recherche
Un graphe a 11 sommets, tous de degré 4. Combien a-t-il d'arêtes ?
Un graphe a 8 sommets, tous de degré 4. Combien a-t-il d'arêtes ?
Dans tout graphe, la somme des degrés vaut le double du nombre d'arêtes (c'est pourquoi les sommets impairs vont par paires, comme chez Euler). Un graphe a 15 arêtes : quelle est la somme des degrés ?
Fiche résumé
Les graphes aujourd'hui
GPS et livraisons : plus courts chemins dans un réseau routier.
Réseaux sociaux : qui est relié à qui.
Prédiction de texte : le mot suivant dépend des mots précédents, comme chez Markov.
Sources : article de MacTutor sur l'histoire de la topologie ; biographie de Markov (voir « Sources et crédits »).
Corrigé: Graphes et chaînes de Markov
1. Graphes : sommets, arêtes, degré, chaînes
A
3
253
10
B
6
146
C
4
D
4
E
3
253
10
F
9
2. Matrice d'adjacence et nombre de chemins
A
3
6
4
B
2
5
2
C
1
2
D
3
E
Symétrique
F
2
5
2
G
2
3. Chaînes de Markov
A
−3
9
Non : son déterminant est nul
B
0,2
0,4
0,3
C
0,55
0,55
D
0,2
E
0,25
F
0,2
0,4
0,3
G
0,81
4. Distributions invariantes
A
0,2
0,55
0,2
B
0,25
301
31
C
0,4
127
D
On vérifie que πP=π
E
0,4
F
0,25
301
31
G
149
5. La distribution invariante d'une chaîne à deux états