On considère le graphe orienté G à 4 sommets de matrice d'adjacence : A = 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 Reconnaître la structure de ce graphe. Calculer A 2 , A 3 , A 4 en utilisant la structure. Montrer que A 4 = I 4 . Combien y a-t-il de chemins de longueur 8 de 1 à 1 ? de longueur 9 de 1 à 2 ?

Matrices d'adjacence, puissances et accessibilité

Difficile Inspiré BAC France

Exercice inspiré d'un BAC France

Énoncé et solution adaptés au programme français. Voir crédits.

Énoncé

On considère le graphe orienté $G$ à 4 sommets de matrice d'adjacence :

A = 0001100001000010

Reconnaître la structure de ce graphe.
Calculer $A^{2}$ , $A^{3}$ , $A^{4}$ en utilisant la structure.
Montrer que $A^{4} = I_{4}$ .
Combien y a-t-il de chemins de longueur 8 de $1$ à $1$ ? de longueur 9 de $1$ à $2$ ?

Indices

— clique pour révéler

1 Indice 1

Regarde ou se trouvent les 1 dans la matrice $A$ pour comprendre comment les sommets sont relies entre eux successivement.

2 Indice 2

Pour calculer les puissances de $A$, pense a ce que represente $A^n$ en termes de chemins de longueur $n$ dans le graphe, plutot que de faire un calcul matriciel complet.

3 Indice 3

Une fois que tu as compris que $A^4 = I_4$, utilise cette periodicite pour simplifier $A^8$ et $A^9$ en les exprimant a l'aide de $A^4$.

Bloqué sur cet exercice ?

Léo peut t'expliquer pas à pas, en s'adaptant à ton niveau.

Demander à Léo

Exercice Terminé? 🎉

Validez votre réponse pour enregistrer votre progression et gagner des points

Lecture d'une matrice d'adjacence Retour au chapitre Modélisation par graphe — réseau de villes

Matrices d'adjacence, puissances et accessibilité

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Matrices d'adjacence, puissances et accessibilité

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Valider votre réponse

Tu as vu 5 exercices aujourd'hui 🎯