Graphes, matrices et chaînes de Markov
🟢 Facile📝 Les énoncés sont gratuits, et les 2 premiers corrigés sont offerts. Les autres corrigés détaillés sont réservés aux abonnés.
- 1
On considère le graphe non orienté d'ordre 5 dont les sommets sont A, B, C, D, E et les arêtes A−B, A−C, B−C, C−D, D−E.
a) Donner l'ordre du graphe.
b) Donner le degré de chaque sommet.
c) Ce graphe est-il connexe ?✅ Voir le corrigéoffert
a) L'ordre d'un graphe est son nombre de sommets. Ici il y a 5 sommets, donc l'ordre est 5.
b) Le degré d'un sommet est le nombre d'arêtes qui l'ont pour extrémité.
deg(A) : arêtes A−B et A−C, donc deg(A) = 2.
deg(B) : arêtes A−B et B−C, donc deg(B) = 2.
deg(C) : arêtes A−C, B−C et C−D, donc deg(C) = 3.
deg(D) : arêtes C−D et D−E, donc deg(D) = 2.
deg(E) : arête D−E, donc deg(E) = 1.
Vérification par le lemme des poignées de main : somme des degrés = 2+2+3+2+1 = 10 = 2 × 5 (le graphe a 5 arêtes). C'est cohérent.
c) Oui, le graphe est connexe : entre deux sommets quelconques il existe toujours une chaîne. Par exemple, pour aller de E à A on emprunte E−D−C−A. Tous les sommets sont ainsi reliés. - 2
Un graphe non orienté possède 6 sommets dont les degrés sont 1, 2, 2, 3, 3 et 5.
a) Combien d'arêtes possède ce graphe ?
b) Vérifier la propriété portant sur le nombre de sommets de degré impair.✅ Voir le corrigéoffert
a) D'après le lemme des poignées de main, la somme des degrés de tous les sommets est égale à deux fois le nombre d'arêtes (chaque arête est comptée à ses deux extrémités).
Somme des degrés = 1+2+2+3+3+5 = 16.
Donc le nombre d'arêtes est 16 ÷ 2 = 8.
b) Les sommets de degré impair sont ceux de degré 1, 3, 3 et 5, soit 4 sommets. Or 4 est pair : la propriété « le nombre de sommets de degré impair est toujours pair » est bien vérifiée. - 3
Peut-il exister un graphe dont les degrés des sommets sont 1, 2, 3, 4 et 5 ? Justifier de deux façons différentes.
🔒 Corrigé réservé aux abonnésS'abonner → - 4
Écrire la matrice d'adjacence M du graphe non orienté à 4 sommets numérotés 1, 2, 3, 4 dont les arêtes sont 1−2, 2−3, 3−4 et 4−1.
🔒 Corrigé réservé aux abonnésS'abonner → - 5
Voici la matrice d'adjacence d'un graphe dont les sommets sont A, B, C, D (dans cet ordre) :
M =
( 0 1 1 0 )
( 1 0 1 1 )
( 1 1 0 0 )
( 0 1 0 0 )
a) Le graphe est-il orienté ?
b) Quel est le degré de B ?
c) Combien le graphe a-t-il d'arêtes ?🔒 Corrigé réservé aux abonnésS'abonner → - 6
Parmi les trois matrices suivantes, indiquer lesquelles sont des matrices de transition (matrices stochastiques) et justifier.
M₁ =
( 0,7 0,3 )
( 0,4 0,6 )
M₂ =
( 0,5 0,6 )
( 0,2 0,8 )
M₃ =
( 0,2 0,8 )
( 1 0 )🔒 Corrigé réservé aux abonnésS'abonner → - 7
On modélise l'évolution entre deux états A et B. À chaque étape, on passe de A à B avec la probabilité 0,25 et de B à A avec la probabilité 0,5.
a) Écrire la matrice de transition M en rangeant les états dans l'ordre A puis B.
b) Quelle est la probabilité de rester en A d'une étape à la suivante ?🔒 Corrigé réservé aux abonnésS'abonner → - 8
On considère la matrice de transition
M =
( 0,75 0,25 )
( 0,5 0,5 )
et l'état initial P₀ = ( 1 0 ) (on part de l'état A).
Calculer les états probabilistes P₁ puis P₂.🔒 Corrigé réservé aux abonnésS'abonner → - 9
On considère le graphe non orienté à 5 sommets A, B, C, D, E dont les arêtes sont A−B, B−C, C−D, D−E et E−A.
a) Quelle est la longueur de la chaîne A−B−C−D ?
b) La suite de sommets A−B−C−D−E−A est-elle un cycle ? Quelle est sa longueur ?🔒 Corrigé réservé aux abonnésS'abonner → - 10
Soit le graphe non orienté « triangle » à 3 sommets 1, 2, 3 tous reliés deux à deux, de matrice d'adjacence
M =
( 0 1 1 )
( 1 0 1 )
( 1 1 0 )
a) Calculer M².
b) Combien y a-t-il de chaînes de longueur 2 reliant le sommet 1 à lui-même ? Et du sommet 1 au sommet 2 ?🔒 Corrigé réservé aux abonnésS'abonner →
Comment ça s'est passé ?
Retrouve tout dans Mon suivi.