Soit A la matrice d'adjacence de K 3 (triangle complet). Calculer A 2 et A 3 . Combien de chemins de longueur 2 vont de 1 à 1 ? De 1 à 2 ? Combien de cycles de longueur 3 passent par le sommet 1 ?

Dénombrement de chemins par puissances de la matrice d'adjacence

Difficile Inspiré BAC France

Exercice inspiré d'un BAC France

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

Énoncé

Soit $A$ la matrice d'adjacence de $K_{3}$ (triangle complet).

Calculer $A^{2}$ et $A^{3}$ .
Combien de chemins de longueur 2 vont de $1$ à $1$ ? De $1$ à $2$ ?
Combien de cycles de longueur 3 passent par le sommet 1 ?

Indices

— clique pour révéler

1 Indice 1

Écris d'abord la matrice $A$ du graphe $K_3$ : un $1$ si deux sommets sont reliés, un $0$ sinon (et $0$ sur la diagonale).

2 Indice 2

Pour calculer $A^2$, effectue le produit matriciel $A \times A$ ligne par colonne ; l'élément $(A^2)_{ij}$ compte le nombre de chemins de longueur 2 de $i$ à $j$.

3 Indice 3

Pour les cycles de longueur 3 passant par 1, regarde la valeur de $(A^3)_{11}$ et essaie d'énumérer les chemins correspondants dans le graphe.

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

Graphe orienté — degrés et matrice Retour au chapitre Algorithme de Prim — arbre couvrant minimal

Dénombrement de chemins par puissances de la matrice d'adjacence

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Dénombrement de chemins par puissances de la matrice d'adjacence

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Valider votre réponse

Tu as vu 5 exercices aujourd'hui 🎯