Graphe orienté : matrice A = 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 (chemin 1 → 2 → 3 → 4 ). Calculer A 2 et A 3 . Calculer la fermeture transitive T = A ∨ A 2 ∨ A 3 . Interpréter ( T ) ij = 1 .

Fermeture transitive

Difficile Inspiré BAC France

Exercice inspiré d'un BAC France

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

Énoncé

Graphe orienté : matrice $A = 0000100001000010$ (chemin $1 \to 2 \to 3 \to 4$ ).

Calculer $A^{2}$ et $A^{3}$ .
Calculer la fermeture transitive $T = A \lor A^{2} \lor A^{3}$ .
Interpréter $(T)_{ij} = 1$ .

Indices

— clique pour révéler

1 Indice 1

Pour calculer $A^2$, effectue le produit matriciel de $A$ par elle-meme en suivant la regle ligne par colonne.

2 Indice 2

Pour calculer $A^3$, multiplie la matrice $A^2$ deja obtenue par $A$.

3 Indice 3

Pour la fermeture transitive, effectue une union logique (booleenne) case par case entre $A$, $A^2$ et $A^3$ : un coefficient vaut $1$ des qu'au moins une des trois matrices a un $1$ a cette position.

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

Algorithme de Prim — arbre couvrant minimal Retour au chapitre Algorithme glouton de coloration

Fermeture transitive

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Fermeture transitive

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Valider votre réponse

Tu as vu 5 exercices aujourd'hui 🎯