Terminale · Mathématiques expertes

Devoir surveillé n°3 — Graphes et matrices

Ce DS évalue la compréhension des concepts de graphes (chaînes, cycles, connexité) et des opérations fondamentales sur les matrices.

1h30 · Moyen · 3 exercices · Barème sur 20 points

Entraînement généré par IA — vérification pédagogique complète non acquise.

Ce sujet n’est pas une annale officielle. La présence d’un corrigé ne garantit pas son exactitude. Vérifie les méthodes avec ton cours ; une note d’entraînement n’est pas une note officielle. Signaler une erreur.

La fenêtre d’impression de ton navigateur permet aussi d’enregistrer en PDF. Aucun téléchargement de PDF officiel n’est annoncé ici.

Sujet

Travaille d’abord sans consulter le corrigé. Note tes réponses et les étapes de ton raisonnement.

Exercice 1 — Vocabulaire des graphes (6 points)

On considère le graphe G suivant (à décrire) : Sommets : A, B, C, D, E. Arêtes : AB, AC, AD, BC, BD, CE, DE. 1. Représenter ce graphe. 2. Donner le degré de chaque sommet. Ce graphe est-il complet ? 3. Le graphe G est-il connexe ? Justifier. Est-il eulérien ?

Exercice 2 — Matrice d'adjacence et puissances (8 points)

Soit le graphe orienté Γ d'ordre 3 (sommets X, Y, Z dans cet ordre) dont la matrice d'adjacence est M = [[0,1,1],[1,0,0],[0,1,0]]. 1. Interpréter le coefficient m₁₂ = 1. 2. Calculer M². Que représente le coefficient (M²)₁₃ ? 3. Combien y a-t-il de chemins de longueur 3 partant de X et arrivant en Z ?

Exercice 3 — Problème : Algorithme de parcours (6 points)

On considère un graphe non orienté, connexe, dont les sommets sont numérotés de 1 à n. On utilise l'algorithme de parcours en profondeur (DFS) suivant, partant du sommet 1, avec une pile P. Initialisation : Marquer 1 comme visité, empiler 1. Tant que la pile P n'est pas vide : - Dépiler le sommet s. - Pour chaque voisin v de s non visité : marquer v comme visité, empiler v. Que garantit cet algorithme sur l'ensemble des sommets visités à la fin de son exécution ? Cet algorithme permet-il de trouver un chemin entre deux sommets quelconques ? Pourquoi ?

Corrigé et barème

Le total du barème est de 20 points. Les réponses rédigées admettent plusieurs formulations pertinentes ; compare le raisonnement, pas seulement les mots.

Exercice 1 — Vocabulaire des graphes : 6 points

1. Représentation non fournie ici, mais l'élève doit la tracer. 2. deg(A)=3, deg(B)=3, deg(C)=3, deg(D)=3, deg(E)=2. Le graphe n'est pas complet car, par exemple, les sommets A et E ne sont pas adjacents. 3. Le graphe est connexe : on peut relier n'importe quelle paire de sommets par une chaîne. Pour être eulérien (cycle eulérien), tous les sommets doivent être de degré pair. Ici, les sommets A, B, C, D sont de degré 3 (impair). Donc le graphe n'est pas eulérien.

Exercice 2 — Matrice d'adjacence et puissances : 8 points

1. Le coefficient m₁₂ = 1 signifie qu'il y a une arête orientée du sommet X (ligne 1) vers le sommet Y (colonne 2). 2. M² = M * M = [[0,1,1],[1,0,0],[0,1,0]] * [[0,1,1],[1,0,0],[0,1,0]] = [[1,1,0],[0,1,1],[1,0,0]]. Le coefficient (M²)₁₃ = 0 représente le nombre de chemins de longueur 2 allant de X à Z. Ici, il n'y en a pas. 3. On calcule M³ = M² * M = [[1,1,0],[0,1,1],[1,0,0]] * M = [[1,2,1],[1,1,0],[0,1,1]]. Le coefficient (M³)₁₃ = 1. Il y a donc exactement 1 chemin de longueur 3 partant de X et arrivant en Z.

Exercice 3 — Problème : Algorithme de parcours : 6 points

Cet algorithme, appliqué à un graphe connexe, garantit que tous les sommets seront visités à la fin de son exécution. En effet, partant du sommet 1 et étant donné que le graphe est connexe, tout sommet est relié à 1 par une chaîne. L'algorithme explore récursivement tous les voisins non visités, assurant ainsi la visite complète. Non, cet algorithme DFS tel qu'écrit ne calcule pas explicitement les chemins entre deux sommets quelconques. Il ne fait que visiter tous les sommets dans un certain ordre. Pour trouver un chemin spécifique, il faudrait modifier l'algorithme pour mémoriser le prédécesseur de chaque sommet lors de sa découverte, permettant ensuite de reconstituer le chemin en remontant.

Comprendre, puis réessayer

Repère une erreur précise, explique ce qui t’a manqué et refais l’exercice sans le corrigé. Reprends la notion dans ton cours avant de passer à un autre sujet.

Planifier une révision · Chercher un autre entraînement

Devoir surveillé n°1 — Nombres complexes (forme algébrique et géométrie)

Devoir surveillé n°2 — Arithmétique : Divisibilité et congruences

Devoir surveillé n°4 — Combinatoire et dénombrement