Exercices sur les graphes et chaînes de Markov en maths expertes

Télécharger les exercices sur les graphes et chaînes de Markov maths expertes en PDFà imprimer, avec les corrigés
⚡ Quiz pour démarrer · 3 questions

La somme des degrés d'un graphe à arêtes vaut :

Le coefficient de ( matrice d'adjacence) compte :

Dans une matrice de transition, chaque ligne a pour somme :

facile moyen difficile
🖨 Imprimer

Exercice 1Ordre et degrés 

On considère le graphe non orienté de sommets , , , et d'arêtes –, –, – et –.

  1. a. Donne l'ordre du graphe et le degré de chaque sommet.
  2. b. Vérifie que la somme des degrés est égale au double du nombre d'arêtes.
Voir le corrigé
  1. a. Ordre ; degrés : : , : , : , : .
  2. b. : chaque arête compte pour ses deux extrémités.
🖨 Imprimer

Exercice 2La matrice d'adjacence 

On considère le graphe non orienté de sommets , , , et d'arêtes –, –, – et –.

Écris la matrice d'adjacence du graphe, dans l'ordre , , , . Pourquoi est-elle symétrique ?

Voir le corrigé

. Le coefficient vaut s'il y a une arête entre les sommets et . Le graphe n'est pas orienté : – est aussi –, d'où la symétrie.

🖨 Imprimer

Exercice 3Le graphe complet 

Un graphe complet d'ordre a une arête entre chaque paire de sommets distincts.

  1. a. Quel est le degré de chaque sommet du graphe complet d'ordre ? Combien a-t-il d'arêtes ?
  2. b. Combien d'arêtes a le graphe complet d'ordre ?
Voir le corrigé
  1. a. Chaque sommet est relié aux autres : degré . Somme des degrés , donc arêtes.
  2. b. arêtes (une par paire de sommets).
🖨 Imprimer

Exercice 4Compter les chaînes de longueur 2 

On considère le graphe non orienté de sommets , , , et d'arêtes –, –, – et –.

On admet que .

  1. a. Combien de chaînes de longueur relient à ? Écris-les.
  2. b. Que représentent les coefficients diagonaux de ?
Voir le corrigé
  1. a. Le coefficient vaut : une seule chaîne, ––.
  2. b. Les chaînes de longueur qui reviennent au point de départ : ce sont les degrés des sommets (aller-retour par chaque arête).

Le coefficient de est le nombre de chaînes de longueur reliant à .

🖨 Imprimer

Exercice 5Un graphe orienté 

Un graphe orienté a pour sommets , , et pour arcs , , et .

  1. a. Écris sa matrice d'adjacence .
  2. b. On admet que . Combien de chemins de longueur vont de à ? Lesquels ?
Voir le corrigé
  1. a. (ligne = départ, colonne = arrivée) ; elle n'est pas symétrique.
  2. b. Un seul : .
🖨 Imprimer

Exercice 6Une chaîne de Markov à deux états 

S'il fait beau, il fait beau le lendemain avec probabilité ; s'il pleut, il pleut le lendemain avec probabilité .

  1. a. Donne la matrice de transition (état : beau, état : pluie).
  2. b. Il fait beau aujourd'hui. Calcule la loi du temps dans jours.
  3. c. Détermine l'état stable.
Voir le corrigé
  1. a. (chaque ligne a pour somme ).
  2. b. , , .
  3. c. avec : , .

Chaîne de Markov : si est la loi (ligne) à l'étape et la matrice de transition, alors et . Un état stable vérifie , avec des coefficients de somme .

🖨 Imprimer

Exercice 7Graphe connexe ? 

On considère le graphe non orienté de sommets , , , et d'arêtes –, –, – et –.

  1. a. Le graphe est-il connexe ? Justifie.
  2. b. On supprime l'arête –. Le graphe reste-t-il connexe ?
Voir le corrigé
  1. a. Oui : , , sont reliés entre eux, et est relié à . Toute paire de sommets est reliée par une chaîne.
  2. b. Non : devient isolé (degré ).
🖨 Imprimer

Exercice 8Une chaîne à trois états 

Un client achète chaque semaine l'une des marques , ou selon la matrice de transition . Cette semaine, il achète la marque .

Calcule la loi des marques achetées dans une semaine, puis dans deux semaines.

Voir le corrigé

, (première ligne de ), .

🖨 Imprimer

Exercice 9L'état stable à trois états 

On reprend la matrice de l'exercice 8. On cherche tel que et .

  1. a. Écris le système vérifié par , , .
  2. b. À la calculatrice, résous-le.
Voir le corrigé
  1. a. (la troisième équation de est redondante).
  2. b. .
🖨 Imprimer

Exercice 10Simuler l'évolution en Python 

Complète la fonction qui calcule la loi de la chaîne de l'exercice 6, en partant de .

def loi(n):
    b, p = 1, 0
    for k in range(n):
        b, p = ........ , ........
    return b, p
Voir le corrigé

: et .

        b, p = 0.7*b + 0.4*p, 0.3*b + 0.6*p

L'affectation simultanée évite d'utiliser la nouvelle valeur de b dans le calcul de p. Pour grand, on obtient , l'état stable.

🖨 Imprimer

Exercice 11Une formule explicite 

Une chaîne à deux états a pour matrice . On note , avec .

  1. a. Montre que .
  2. b. Déduis-en en fonction de et sa limite.
Voir le corrigé
  1. a. .
  2. b. Point fixe . est géométrique de raison : et .
🖨 Imprimer

Exercice 12Une marche sur un triangle 

Un pion se déplace sur les sommets , , d'un triangle : à chaque étape, il va sur l'un des deux autres sommets, avec la même probabilité. Il part de ; est la probabilité qu'il soit en à l'étape .

  1. a. Donne la matrice de transition et l'état stable.
  2. b. Montre que , puis que .
Voir le corrigé
  1. a. . Par symétrie, l'état stable est .
  2. b. Pour être en à l'étape , il faut ne pas y être à l'étape (probabilité ) puis choisir (). est géométrique de raison et vaut au départ : on obtient la formule. .
🖨 Imprimer

Exercice 13type contrôleUn petit réseau social 

Cinq personnes , , , , sont reliées par les amitiés –, –, –, –, – et –.

  1. 1. Représente le graphe et donne le degré de chaque sommet. Qui a le plus d'amis ?
  2. 2. Écris la matrice d'adjacence (ordre alphabétique).
  3. 3. On admet que . Combien d'amis communs ont et ? Qui sont-ils ?
  4. 4. Deux personnes non amies sont « amies d'amis » si elles ont au moins un ami commun. Quelles paires ne sont ni amies, ni amies d'amis ?
Voir le corrigé
  1. 1. : , : , : , : , : . et ont le plus d'amis.
  2. 2. .
  3. 3. Coefficient : amis communs, et .
  4. 4. Les paires non amies sont , , et . Leurs coefficients dans valent , , et , tous non nuls : aucune paire n'est ni amie, ni amie d'amis.
🖨 Imprimer

Exercice 14type contrôleDeux plateformes de streaming 

Chaque mois, des abonnés de la plateforme A passent chez B et des abonnés de B passent chez A. Au départ, les deux plateformes ont autant d'abonnés.

  1. 1. Donne la matrice de transition (état : A, état : B) et .
  2. 2. Calcule .
  3. 3. On note . Montre que .
  4. 4. Déduis-en en fonction de , sa limite, et l'état stable.
  5. 5. À partir de quel mois la part de A passe-t-elle sous ?
Voir le corrigé
  1. 1. , .
  2. 2. .
  3. 3. .
  4. 4. Point fixe : , , état stable .
  5. 5. : au mois.
🖨 Imprimer

Exercice 15type bacLes lecteurs de deux journaux 

Dans une ville, chaque habitant lit chaque jour le journal ou le journal . Un lecteur de reste fidèle le lendemain avec probabilité ; un lecteur de passe à avec probabilité . Le premier jour, des habitants lisent .

  1. 1. Représente la situation par un graphe probabiliste et donne la matrice de transition .
  2. 2. Calcule la répartition le deuxième jour.
  3. 3. Détermine l'état stable et interprète-le.
  4. 4. On admet que , où est la part de le jour (). Vérifie pour et , puis détermine à partir de quel jour dépasse .
Voir le corrigé
  1. 1. Deux sommets et , arcs pondérés (), (), (), (). .
  2. 2. .
  3. 3. : . À long terme, des habitants lisent .
  4. 4. et . : à partir de , soit le cinquième jour.
🖨 Imprimer

Exercice 16type bacUn réseau de routes 

Quatre villes , , , sont reliées par des routes à double sens : –, –, –, –, –.

  1. 1. Écris la matrice d'adjacence (ordre , , , ).
  2. 2. On admet que . Combien de trajets de routes vont de à ? Écris-les.
  3. 3. Existe-t-il un trajet de routes partant de et revenant en ? Combien ?
  4. 4. Quelle est la longueur minimale d'un trajet de à ?
Voir le corrigé
  1. 1. .
  2. 2. Coefficient : trajets, ––– et –––.
  3. 3. Coefficient : trajets, les deux sens du triangle ––– et –––.
  4. 4. et ne sont pas voisins (), mais –– existe : longueur .

Les autres exercices de maths expertes

Annales du bac de maths corrigées

Questions fréquentes

Qu'est-ce que la matrice d'adjacence d'un graphe ?

C'est la matrice dont le coefficient ligne i, colonne j vaut 1 s'il y a une arête (ou un arc) de i vers j, et 0 sinon. Pour un graphe non orienté, elle est symétrique.

Comment compter les chemins de longueur n ?

Le coefficient ligne i, colonne j de la puissance Mⁿ de la matrice d'adjacence est le nombre de chemins de longueur n allant de i à j.

Qu'est-ce qu'une chaîne de Markov ?

C'est une suite d'états aléatoires où l'état suivant ne dépend que de l'état présent. Elle est décrite par une matrice de transition P, dont chaque ligne a pour somme 1, et la loi évolue selon π(n+1) = π(n) × P.

Comment trouver l'état stable d'une chaîne de Markov ?

On résout πP = π avec la condition que la somme des coefficients de π vaut 1. Pour deux états, on obtient une équation du premier degré.

Les exercices sont-ils gratuits ?

Oui. Les 16 exercices et leurs corrigés sont gratuits, en ligne et en PDF à imprimer, sans inscription.