Fiche d'exercices Logimaths | Terminale maths expertes
Fiche d'exercices : Graphes
8 exercices progressifs ⭐ → ⭐⭐⭐ : cherche d'abord, la correction est sous chaque énoncé
Échauffement
Exercice 1 : Vocabulaire et degrés⭐
Un graphe a pour sommets A, B, C, D, E et pour arêtes : A-B, A-C, A-D, B-C, C-D, D-E.
- Donne le degré de chaque sommet.
- Le graphe est-il complet ? Connexe ?
👆 ▶ Correction de l'exercice 1
1. deg(A) = 3, deg(B) = 2, deg(C) = 3, deg(D) = 3, deg(E) = 1.
2. Pas complet (B et E ne sont pas reliés, par exemple) ; connexe : on peut joindre n'importe quels sommets (E se raccroche par D).
2. Pas complet (B et E ne sont pas reliés, par exemple) ; connexe : on peut joindre n'importe quels sommets (E se raccroche par D).
Exercice 2 : Le lemme des poignées de main⭐
- Vérifie le lemme sur le graphe de l'exercice 1.
- Peut-il exister un graphe dont les degrés seraient 3, 3, 3, 1 ? Et 3, 3, 3, 3, 1 ?
👆 ▶ Correction de l'exercice 2
1. Somme des degrés = 3 + 2 + 3 + 3 + 1 = 12 = 2 × 6 arêtes ✔.
2. 3 + 3 + 3 + 1 = 10 (pair) : le lemme ne l'interdit pas… et pourtant ce graphe n'existe pas ! Les trois sommets de degré 3 sont chacun reliés aux trois autres, donc le 4ᵉ sommet reçoit une arête de chacun : il serait de degré 3, jamais 1. ⚠️ Une somme paire est nécessaire mais pas suffisante (en revanche la suite 3, 3, 2, 2 se réalise bien). 3 + 3 + 3 + 3 + 1 = 13 (impair) : impossible, la somme des degrés est toujours paire.
2. 3 + 3 + 3 + 1 = 10 (pair) : le lemme ne l'interdit pas… et pourtant ce graphe n'existe pas ! Les trois sommets de degré 3 sont chacun reliés aux trois autres, donc le 4ᵉ sommet reçoit une arête de chacun : il serait de degré 3, jamais 1. ⚠️ Une somme paire est nécessaire mais pas suffisante (en revanche la suite 3, 3, 2, 2 se réalise bien). 3 + 3 + 3 + 3 + 1 = 13 (impair) : impossible, la somme des degrés est toujours paire.
Le cœur du chapitre
Exercice 3 : Matrice d'adjacence⭐⭐
Soit le graphe de sommets 1, 2, 3 et d'arêtes 1-2, 2-3.
- Écris sa matrice d'adjacence M.
- Pourquoi M est-elle symétrique ? Que vaut sa diagonale ?
- Retrouve le degré du sommet 2 à partir de M.
👆 ▶ Correction de l'exercice 3
1. M = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}.
2. Une arête 1-2 se lit dans les deux sens (graphe non orienté) ; pas de boucle, donc diagonale nulle.
3. Somme de la ligne 2 : 1 + 0 + 1 = 2.
2. Une arête 1-2 se lit dans les deux sens (graphe non orienté) ; pas de boucle, donc diagonale nulle.
3. Somme de la ligne 2 : 1 + 0 + 1 = 2.
Exercice 4 : Chemins de longueur 2⭐⭐
Avec la matrice M de l'exercice 3 :
- Calcule M².
- Combien de chemins de longueur 2 mènent de 1 à 3 ? De 1 à 1 ? Décris-les.
👆 ▶ Correction de l'exercice 4
1. M^2 = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & 0 \\ 1 & 0 & 1 \end{pmatrix}.
2. De 1 à 3 : coefficient (1 ; 3) = 1 chemin (1 → 2 → 3). De 1 à 1 : 1 chemin (1 → 2 → 1, l'aller-retour compte !).
2. De 1 à 3 : coefficient (1 ; 3) = 1 chemin (1 → 2 → 3). De 1 à 1 : 1 chemin (1 → 2 → 1, l'aller-retour compte !).
Exercice 5 : Graphe orienté⭐⭐
Trois pages web se citent : 1 pointe vers 2 et 3 ; 2 pointe vers 3 ; 3 pointe vers 1.
- Écris la matrice d'adjacence M (ligne = départ, colonne = arrivée).
- M est-elle symétrique ? Pourquoi ?
- Combien de chemins de longueur 2 mènent de 1 à 1 ?
👆 ▶ Correction de l'exercice 5
1. M = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}.
2. Non : 1 pointe vers 2 mais 2 ne pointe pas vers 1 (les flèches ont un sens).
3. Chemins 1 → ? → 1 : seul 1 → 3 → 1 convient : 1 chemin (c'est le coefficient (1 ; 1) de M²).
2. Non : 1 pointe vers 2 mais 2 ne pointe pas vers 1 (les flèches ont un sens).
3. Chemins 1 → ? → 1 : seul 1 → 3 → 1 convient : 1 chemin (c'est le coefficient (1 ; 1) de M²).
Exercice 6 : Marche aléatoire à deux états⭐⭐
Un vélo en libre-service est chaque soir à la station A ou B. S'il est en A, il y reste le lendemain avec probabilité 0,9 ; s'il est en B, il revient en A avec probabilité 0,4. Convention colonne : U_{n+1} = AU_n.
- Écris la matrice de transition A et vérifie que ses colonnes somment à 1.
- Le vélo part de A (U_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}). Calcule U_1 puis U_2.
👆 ▶ Correction de l'exercice 6
1. A = \begin{pmatrix} 0{,}9 & 0{,}4 \\ 0{,}1 & 0{,}6 \end{pmatrix} : 0,9 + 0,1 = 1 et 0,4 + 0,6 = 1 ✔.
2. U_1 = \begin{pmatrix} 0{,}9 \\ 0{,}1 \end{pmatrix} puis U_2 = \begin{pmatrix} 0{,}9 \times 0{,}9 + 0{,}4 \times 0{,}1 \\ 0{,}1 \times 0{,}9 + 0{,}6 \times 0{,}1 \end{pmatrix} = \begin{pmatrix} 0{,}85 \\ 0{,}15 \end{pmatrix}.
2. U_1 = \begin{pmatrix} 0{,}9 \\ 0{,}1 \end{pmatrix} puis U_2 = \begin{pmatrix} 0{,}9 \times 0{,}9 + 0{,}4 \times 0{,}1 \\ 0{,}1 \times 0{,}9 + 0{,}6 \times 0{,}1 \end{pmatrix} = \begin{pmatrix} 0{,}85 \\ 0{,}15 \end{pmatrix}.
Pour aller plus loin
Exercice 7 : L'état stable⭐⭐⭐
On garde la marche de l'exercice 6.
- Cherche l'état stable V = \begin{pmatrix} x \\ y \end{pmatrix} (AV = V et x + y = 1).
- Interprète le résultat pour l'exploitant des stations.
👆 ▶ Correction de l'exercice 7
1. 0{,}9x + 0{,}4y = x donne 0{,}4y = 0{,}1x, soit x = 4y. Avec x + y = 1 : x = 0,8 et y = 0,2.
2. À long terme, le vélo passe 80 % de ses nuits en A : la station B est sous-utilisée, l'exploitant peut redimensionner (les états U_n calculés se rapprochaient déjà de (0,8 ; 0,2)).
2. À long terme, le vélo passe 80 % de ses nuits en A : la station B est sous-utilisée, l'exploitant peut redimensionner (les états U_n calculés se rapprochaient déjà de (0,8 ; 0,2)).
Exercice 8 : Synthèse type bac : le réseau à trois sommets⭐⭐⭐
Soit le graphe complet à 3 sommets (triangle 1-2-3), de matrice d'adjacence M = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}.
- Calcule M² et interprète son coefficient (1 ; 1).
- Combien de chemins de longueur 2 entre deux sommets distincts ?
- Vérifie que M^2 = M + 2I et déduis-en M^3 en fonction de M et I.
👆 ▶ Correction de l'exercice 8
1. M^2 = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix} : le 2 en (1 ; 1) compte les allers-retours 1 → 2 → 1 et 1 → 3 → 1.
2. 1 seul (par le troisième sommet) : coefficients hors diagonale = 1.
3. M + 2I = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix} ✔. Alors \begin{aligned}M^3 &= M \times M^2 \\ &= M(M + 2I) \\ &= M^2 + 2M \\ &= 3M + 2I\end{aligned} : 3 chemins de longueur 3 entre sommets distincts, 2 entre un sommet et lui-même.
2. 1 seul (par le troisième sommet) : coefficients hors diagonale = 1.
3. M + 2I = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix} ✔. Alors \begin{aligned}M^3 &= M \times M^2 \\ &= M(M + 2I) \\ &= M^2 + 2M \\ &= 3M + 2I\end{aligned} : 3 chemins de longueur 3 entre sommets distincts, 2 entre un sommet et lui-même.