Soit le graphe non orienté G de matrice d'adjacence : A = 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 Calculer A 2 . Calculer ( A 2 ) 22 et interpréter en listant les promenades. Calculer ( A 3 ) 14 et lister les chemins. Quelle est la signification de ( A k ) ii ?

Chemin de longueur $k$ et interprétation combinatoire

Difficile Inspiré BAC France

Exercice inspiré d'un BAC France

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

Énoncé

Soit le graphe non orienté $G$ de matrice d'adjacence :

A = 0100101101010110

Calculer $A^{2}$ .
Calculer $(A^{2})_{22}$ et interpréter en listant les promenades.
Calculer $(A^{3})_{14}$ et lister les chemins.
Quelle est la signification de $(A^{k})_{ii}$ ?

Indices

— clique pour révéler

1 Indice 1

Pour calculer $A^2$, effectue le produit matriciel $A \times A$ ligne par colonne, en n'oubliant aucun coefficient.

2 Indice 2

Le coefficient $(A^2)_{ij}$ compte le nombre de promenades de longueur 2 entre le sommet i et le sommet j ; pour $(A^2)_{22}$, cherche tous les sommets voisins de 2 par lesquels on peut repartir vers 2.

3 Indice 3

Pour $(A^3)_{14}$, pense a $A^3 = A^2 \times A$, ou cherche directement tous les chemins de longueur 3 reliant le sommet 1 au sommet 4 en suivant les aretes du 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

Chaîne eulérienne — condition sur les degrés Retour au chapitre Circuit hamiltonien et graphe complet

Chemin de longueur $k$ et interprétation combinatoire

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Chemin de longueur $k$ et interprétation combinatoire

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Valider votre réponse

Tu as vu 5 exercices aujourd'hui 🎯