Exercices#

Graphes

Mode d’emploi

Niveau : ★ échauffement, ★★ classique (niveau bac), ★★★ défi ; les coups de pouce et les corrigés se déplient sous chaque exercice.
▶ À programmer et tester en Python.
On dispose de la classe Graphe du cours (graphes non orientés) : constructeur Graphe(sommets), méthodes ajoute_arete(a, b), voisins(s), sont_voisins(a, b).
Usage de l’IA, indiqué sur chaque exercice : aucune ; en appui (déboguer, reformuler, vérifier ; la réponse finale est écrite et comprise par vous) ; l’exercice s’appuie sur une réponse d’IA. Voir la charte d’usage de l’IA.

class Graphe:
    def __init__(self, sommets):
        self.sommets = sommets
        self.adj = {}
        for s in sommets:
            self.adj[s] = []
    def ajoute_arete(self, a, b):
        self.adj[a].append(b)
        self.adj[b].append(a)
    def voisins(self, s):
        return self.adj[s]
    def sont_voisins(self, a, b):
        return b in self.adj[a]

Vocabulaire et modélisation#

★ Exercice 1 #

• essentiel On considère le graphe non orienté ci-dessous.

Donner la liste des voisins de B, puis le degré de chaque sommet.
Donner une chaîne de longueur $4$ reliant A à F.
Ce graphe est-il connexe ? Justifier.
Donner un cycle de ce graphe.

Coup de pouce

Le degré d’un sommet est son nombre de voisins. Une chaîne de longueur $4$ emprunte $4$ arêtes. Pour la connexité : peut-on aller de n’importe quel sommet à n’importe quel autre ? Un cycle est une chaîne qui revient à son point de départ sans réutiliser d’arête.

Corrigé

Remarque

On donne une version simple de chaque programme ; d’autres sont possibles. Les ordres de parcours dépendent de l’ordre dans lequel on liste les voisins.

1. Voisins de B : A, C, D. Degrés : A :2, B :3, C :3, D :3, E :3, F :2.

2. Par exemple A -- B -- D -- E -- F (longueur $4$).

3. Oui, il est connexe : tout sommet est atteignable depuis n’importe quel autre (un seul morceau).

4. Par exemple le cycle A -- B -- C -- A, ou B -- D -- E -- C -- B.

▷ Erreur fréquente. Se tromper d’un degré sans s’en apercevoir : la somme des degrés vaut toujours le double du nombre d’arêtes ($2+3+3+3+3+2 = 16 = 2 \times 8$), ce qui permet de se vérifier.

★ Exercice 2 #

Dans une classe, on relève les binômes de travail : Alice travaille avec Bilal et Chloé ; Bilal avec Alice, Chloé et Dora ; Chloé avec Alice, Bilal et Émile ; Dora avec Bilal ; Émile avec Chloé.

Dire si ce graphe est orienté ou non orienté, et pourquoi.
Dessiner le graphe (un sommet par initiale).
Qui a le plus de partenaires ? Traduire cette question en vocabulaire de graphe.

Coup de pouce

Si Alice travaille avec Bilal, Bilal travaille-t-il forcément avec Alice ? Pour la question 3, quel mot du vocabulaire désigne le nombre de voisins d’un sommet ?

Corrigé

1. Non orienté : « travaille avec » est une relation symétrique.

2.

3. « Qui a le plus de partenaires ? » $=$ « quel sommet a le plus grand degré ? ». Ici Bilal et Chloé (degré $3$).

★ Exercice 3 #

• essentiel Sur un réseau social, on note « $X\to Y$ » lorsque « $X$ suit $Y$ ». On relève : A$\to$B, A$\to$C, B$\to$C, C$\to$A, D$\to$C.

Dessiner le graphe orienté correspondant.
Donner les successeurs de A, puis les prédécesseurs de C.
Existe-t-il un chemin de D vers B ? de B vers D ? Que remarque-t-on ?
Ce graphe possède-t-il un cycle (au sens orienté) ?

Coup de pouce

Chaque relevé « $X\to Y$ » donne une flèche de $X$ vers $Y$. Les successeurs de A sont les sommets vers lesquels partent ses flèches ; les prédécesseurs de C, ceux d’où partent les flèches qui arrivent sur C. Un chemin doit suivre le sens des flèches.

Corrigé

1.

2. Successeurs de A : B, C. Prédécesseurs de C : A, B, D.

3. D$\to$B : oui (D$\to$C$\to$A$\to$B). B$\to$D : non (aucun arc n’arrive sur D). Un chemin peut exister dans un sens sans exister dans l’autre : c’est propre aux graphes orientés.

▷ Erreur fréquente. Répondre « oui » de B vers D parce que les sommets sont reliés par une suite d’arcs : dans un graphe orienté, un chemin doit suivre le sens des flèches.

4. Oui : A$\to$B$\to$C$\to$A est un cycle orienté.

Représenter un graphe#

★ Exercice 4 #

• essentiel On reprend le graphe non orienté de l’exercice 1 (sommets A à F, ordre alphabétique).

Écrire sa matrice d’adjacence. Vérifier qu’elle est symétrique.
Écrire sa liste d’adjacence (dictionnaire Python).

Coup de pouce

Matrice : une ligne et une colonne par sommet, dans l’ordre alphabétique ; la case (ligne $X$, colonne $Y$) vaut $1$ si $X$ et $Y$ sont reliés. Liste d’adjacence : un dictionnaire qui associe à chaque sommet la liste de ses voisins.

Corrigé

1. Sommets A,B,C,D,E,F ; arêtes A-B, A-C, B-C, B-D, C-E, D-E, D-F, E-F : $$M=\begin{pmatrix} 0&1&1&0&0&0\\ 1&0&1&1&0&0\\ 1&1&0&0&1&0\\ 0&1&0&0&1&1\\ 0&0&1&1&0&1\\ 0&0&0&1&1&0 \end{pmatrix}$$ Elle est bien symétrique.

2. Démarche : à chaque sommet (une clé), on associe la liste de ses voisins, par ordre alphabétique.

G = {'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['A', 'B', 'E'],
     'D': ['B', 'E', 'F'], 'E': ['C', 'D', 'F'], 'F': ['D', 'E']}

▷ Erreur fréquente. N’écrire chaque arête qu’une fois : dans un graphe non orienté, l’arête A-B donne B dans les voisins de A et A dans les voisins de B.

★ Exercice 5 #

Construire (dessiner) le graphe correspondant à chacune des représentations suivantes.

$M=\begin{pmatrix} 0 & 1 & 1 & 1 & 0\\ 1 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 & 1\\ 1 & 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 1 & 0 \end{pmatrix}$ (sommets A, B, C, D, E)
la liste de listes adj = [[1, 2], [0, 2, 3], [0, 1], [1, 4], [3]] (sommets $0$ à $4$).

Coup de pouce

Matrice : un $1$ en ligne $i$, colonne $j$ indique une arête entre le $i$-ième et le $j$-ième sommet ; la matrice étant symétrique, il suffit de lire les cases situées au-dessus de la diagonale. Liste de listes : adj[i] contient les voisins du sommet $i$.

Corrigé

1. A-B, A-C, A-D, B-C, C-D, C-E, D-E. 2. Sommets $0..4$ : 0-1, 0-2, 1-2, 1-3, 3-4.

★★ Exercice 6 — ▶ #

On numérote les sommets de $0$ à $n-1$. Un graphe est donné soit par sa matrice M (liste de listes de $0/1$), soit par ses listes d’adjacence adj (liste de listes d’entiers).

Écrire matrice_vers_listes(M) qui renvoie les listes d’adjacence correspondantes.
Écrire listes_vers_matrice(adj) qui renvoie la matrice d’adjacence correspondante.
Tester que les deux fonctions sont bien « inverses » l’une de l’autre sur un exemple.

Coup de pouce

Question 1 : pour chaque ligne i de M, garder les indices j tels que M[i][j] vaut $1$. Question 2 : partir d’une matrice $n\times n$ remplie de $0$, puis placer les $1$.

Coup de pouce 2 (début de solution)

def matrice_vers_listes(M):
adj = []
for i in range(len(M)):
voisins_i = [] …

Corrigé

1. Les voisins du sommet i sont les indices j de la ligne i où la matrice vaut $1$ : on construit cette liste par compréhension, ligne après ligne.

def matrice_vers_listes(M):
    n = len(M)
    adj = []
    for i in range(n):
        adj.append([j for j in range(n) if M[i][j] == 1])   # voisins de i
    return adj

Autre méthode : sans compréhension, avec deux boucles imbriquées.

def matrice_vers_listes(M):
    adj = []
    for i in range(len(M)):
        voisins_i = []
        for j in range(len(M)):
            if M[i][j] == 1:
                voisins_i.append(j)
        adj.append(voisins_i)
    return adj

2. On part d’une matrice $n \times n$ remplie de $0$, puis on place un $1$ pour chaque voisin j de chaque sommet i.

def listes_vers_matrice(adj):
    n = len(adj)
    M = [[0] * n for i in range(n)]
    for i in range(n):
        for j in adj[i]:
            M[i][j] = 1
    return M

3. On vérifie que listes_vers_matrice(matrice_vers_listes(M)) == M redonne bien la matrice de départ.

★★ Exercice 7 #

On considère le graphe pondéré suivant (les poids sont des distances en km).

Proposer une matrice de poids pour ce graphe (mettre $0$ sur la diagonale et là où il n’y a pas d’arête).
Donner, en énumérant les chemins, le trajet le plus court (en km) de A à D.

Coup de pouce

Lister tous les chemins de A à D qui ne repassent jamais par un même sommet, puis additionner les poids de chacun.

Corrigé

1. (poids sur la diagonale $=0$, et $0$ en l’absence d’arête) $$P=\begin{pmatrix} 0&4&7&0\\ 4&0&2&5\\ 7&2&0&3\\ 0&5&3&0 \end{pmatrix}\quad(\text{ordre }\texttt{A},\texttt{B},\texttt{C},\texttt{D})$$ 2. A-B-C-D $=4+2+3=9$ ; A-B-D$=4+5=9$ ; A-C-D$=7+3=10$ ; A-C-B-D$=7+2+5=14$. Le plus court fait 9 km, longueur atteinte par deux trajets : A-B-D et A-B-C-D.

La classe `Graphe`#

★★ Exercice 8 — ▶ #

• essentiel En utilisant uniquement l’interface de la classe Graphe (méthodes voisins et sont_voisins), écrire les fonctions suivantes.

degre(g, s) : renvoie le degré du sommet s.
est_isole(g, s) : renvoie True si s n’a aucun voisin.
nb_aretes(g) : renvoie le nombre d’arêtes du graphe.

Coup de pouce

Que renvoie g.voisins(s), et comment en déduire le degré ? Pour nb_aretes, additionner les degrés de tous les sommets (g.sommets) : attention, chaque arête est alors comptée deux fois.

Corrigé

Démarche : on n’utilise que l’interface : g.voisins(s) renvoie la liste des voisins, sa longueur est le degré ; pour le nombre d’arêtes, on additionne les degrés de tous les sommets.

def degre(g, s):
    return len(g.voisins(s))

def est_isole(g, s):
    return g.voisins(s) == []

def nb_aretes(g):
    total = 0
    for s in g.sommets:
        total = total + len(g.voisins(s))
    return total // 2      # chaque arete est comptee deux fois

▷ Erreur fréquente. Renvoyer total sans le diviser par $2$ : chaque arête a-b est comptée deux fois, dans les voisins de a et dans ceux de b.

Parcourir un graphe#

★★ Exercice 9 #

• essentiel On considère ce graphe (les voisins seront toujours pris par ordre alphabétique).

Donner « à la main » le parcours en largeur (BFS) depuis A, en écrivant à chaque étape le contenu de la file.
Donner « à la main » le parcours en profondeur (DFS) depuis A.
Les deux parcours visitent-ils les mêmes sommets ? Dans le même ordre ?

Coup de pouce

BFS : écrire la file à chaque étape ; on défile en tête, on enfile en queue les voisins non encore découverts, par ordre alphabétique. DFS : aller le plus loin possible avant de revenir en arrière.

Corrigé

1. BFS depuis A (file entre crochets) : on visite A (file [B,C]), B ([C,D]), C ([D]), D ([E,F]), E ([F]), F. Résultat : [A, B, C, D, E, F].

▷ Erreur fréquente. Enfiler C une seconde fois en traitant B : C est déjà découvert (il attend dans la file). On teste tous les sommets découverts, pas seulement les sommets déjà visités.

2. DFS depuis A : A$\to$B$\to$C$\to$D$\to$E$\to$F. Résultat : [A, B, C, D, E, F].

3. Ils visitent les mêmes sommets (toute la composante connexe), mais pas forcément dans le même ordre (ici ils coïncident par hasard ; changez une arête et l’ordre diffère).

★★ Exercice 10 — ▶ #

Programmer la classe Graphe, puis les fonctions BFS(g, depart) et DFS(g, sommet) (récursive) du cours. Pour la file du BFS, reprendre la classe File du chapitre Structures linéaires.

Coup de pouce

Q1 : relire les deux codes du cours. Le BFS tient trois choses à jour : la file en_attente, la liste decouverts (testée avant d’enfiler un voisin) et la liste traites. Le DFS récursif transmet sa liste traites à chaque appel ; que vaut ce paramètre au premier appel ?
Construire le graphe de l’exercice précédent et vérifier vos réponses aux traces à la main.
Programmer aussi DFS_iteratif(g, depart) (avec une pile). Donne-t-il le même ordre que le DFS récursif ? Expliquer.

Coup de pouce

Q3 : reprendre le code du BFS en remplaçant la file par une pile. Dans quel ordre les voisins d’un sommet sortent-ils de la pile ?

Corrigé

Voir le cours pour BFS, DFS (récursif) et DFS_iteratif. Pour la file, la classe File du chapitre Structures linéaires (avec pop(0)) convient ici : c’est un choix de simplicité, acceptable sur de petits graphes, mais chaque defiler coûte alors $O(n)$ ; sur un grand graphe, on changerait d’implémentation (liste chaînée, deux piles…) sans toucher au BFS. Sur ce graphe, le DFS itératif renvoie par exemple [A, C, D, F, E, B] : la pile traite en dernier le premier voisin empilé, d’où un ordre différent du DFS récursif — mais c’est bien un parcours en profondeur valide.

Chemins, cycles, connexité#

★★ Exercice 11 — ▶ #

• essentiel À l’aide d’un parcours, écrire :

existe_chemin(g, u, v) : renvoie True s’il existe une chaîne de u à v.

Coup de pouce

Q1 : quels sommets un parcours lancé depuis u visite-t-il ?
est_connexe(g) : renvoie True si le graphe est connexe.

Coup de pouce

Q2 : un parcours depuis n’importe quel sommet doit visiter tous les sommets.

Corrigé

Démarche : un parcours lancé depuis u visite exactement les sommets reliés à u par une chaîne ; il suffit de regarder si v en fait partie. Le graphe est connexe si un parcours depuis un sommet quelconque visite tous les sommets.

def existe_chemin(g, u, v):
    return v in DFS(g, u)          # ou BFS

def est_connexe(g):
    depart = g.sommets[0]
    return len(BFS(g, depart)) == len(g.sommets)

★★★ Exercice 12 — ▶ #

≈ 30 min On veut le plus court chemin en nombre d’arêtes.

En vous inspirant du BFS, écrire plus_court_chemin(g, depart, arrivee) qui renvoie la liste des sommets d’un plus court chemin (ou None).

Coup de pouce

Q1 : pendant le BFS, mémoriser le parent de chaque sommet découvert (le sommet depuis lequel on l’a découvert), puis remonter de l’arrivée jusqu’au départ.

Coup de pouce 2 (début de solution)

Q1 :
parent = {depart: None}
en_attente = File()
en_attente.enfiler(depart)
while not en_attente.est_vide():
s = en_attente.defiler() … À la fin, remonter avec s = parent[s] et retourner la liste obtenue.
Écrire distances(g, depart) qui renvoie un dictionnaire donnant, pour chaque sommet, sa distance (nombre d’arêtes) au départ.

Coup de pouce

Q2 : un sommet découvert depuis s est à la distance de s plus $1$.
Sur un graphe de votre choix, vérifier que len(plus_court_chemin(...)) - 1 vaut bien la distance renvoyée.

Corrigé

def plus_court_chemin(g, depart, arrivee):
    decouverts = [depart]
    en_attente = File()
    en_attente.enfiler(depart)
    parent = {depart: None}
    while not en_attente.est_vide():
        s = en_attente.defiler()
        if s == arrivee:
            chemin = [arrivee]
            while parent[chemin[0]] is not None:
                chemin = [parent[chemin[0]]] + chemin
            return chemin
        for v in g.voisins(s):
            if v not in decouverts:
                decouverts.append(v)
                en_attente.enfiler(v)
                parent[v] = s
    return None

def distances(g, depart):
    d = {depart: 0}              # sert aussi de liste des decouverts
    en_attente = File()
    en_attente.enfiler(depart)
    while not en_attente.est_vide():
        s = en_attente.defiler()
        for v in g.voisins(s):
            if v not in d:
                d[v] = d[s] + 1
                en_attente.enfiler(v)
    return d

3. Sur le graphe de l’exercice 9, plus_court_chemin(g, ’A’, ’F’) vaut [’A’,’B’,’D’,’F’] : longueur $3$, qui est bien la valeur distances(g,’A’)[’F’].

Vers le bac#

★★ Exercice 13 — d’après Amérique du Nord 2024, jour 1, ex. 2 #

≈ 45 min

On modélise un groupe de huit personnes (Anas, Emma, Gabriel, Jade, Lou, Milo, Nina, Yanis) par un graphe : les sommets sont les personnes, les arêtes les liens d’amitié.

Gabriel est ami avec Jade, Yanis, Nina et Milo ;
Jade est amie avec Gabriel, Yanis, Emma et Lou ;
Yanis est ami avec Gabriel, Jade, Emma, Nina, Milo et Anas ;
Emma est amie avec Jade, Yanis et Nina ;
Nina est amie avec Gabriel, Yanis et Emma ;
Milo est ami avec Gabriel, Yanis et Anas ;
Anas est ami avec Yanis et Milo ;
Lou est amie avec Jade.

Partie A — Matrice d’adjacence

Dessiner ce graphe (chaque personne par l’initiale de son prénom, entourée d’un cercle).
Recopier et compléter la matrice d’adjacence (un $1$ pour un lien d’amitié, un $0$ sinon).

# sommets :     G, J, Y, E, N, M, A, L
matrice_adj = [[0, 1, 1, 0, 1, 1, 0, 0],   # G
               [......................],   # J
               ...                     ]

On dispose de sommets = [’G’,’J’,’Y’,’E’,’N’,’M’,’A’,’L’] et d’une fonction position(l, s) qui renvoie la position de s dans la liste l (ou None s’il est absent).

Indiquer les retours de position(sommets, ’G’) et position(sommets, ’Z’).
Recopier et compléter la fonction nb_amis qui renvoie le nombre d’amis du sommet s (ou None s’il est absent).

Coup de pouce

Q4 : la ligne pos_s de la matrice ne contient que des $0$ et des $1$ : que représente la somme de ses éléments ?
```
def nb_amis(L, m, s):
    pos_s = ...
    if pos_s == None:
        return ...
    amis = 0
    for i in range(len(m)):
        amis += ...
    return ...
```
Indiquer le retour de nb_amis(sommets, matrice_adj, ’G’).

Partie B — Dictionnaire de listes d’adjacence

Dans un dictionnaire {c : v}, que représentent c et v ici ?
Recopier et compléter le dictionnaire graphe de listes d’adjacence des amis.
Écrire nb_amis(d, s) qui renvoie le nombre d’amis de s (on suppose s présent dans d).

Milo se fâche avec Gabriel et Yanis, et Anas avec Yanis ; le nouveau graphe est :

graphe = {'G': ['J', 'Y', 'N'],       'J': ['G', 'Y', 'E', 'L'],
          'Y': ['G', 'J', 'E', 'N'],  'E': ['J', 'Y', 'N'],
          'N': ['G', 'Y', 'E'],       'M': ['A'],
          'A': ['M'],                 'L': ['J']}

Le « cercle d’amis » d’une personne est l’ensemble des personnes atteignables depuis elle ; on l’obtient par un parcours en profondeur.

Donner le cercle d’amis de Lou.

Recopier et compléter la fonction de parcours en profondeur.

Coup de pouce

Q10 : marquer d’abord s comme visité, puis ne relancer le parcours que sur les voisins pas encore visités.

def parcours_en_profondeur(d, s, visites=None):
    if visites is None:
        visites = []
    ...
    for v in d[s]:
        ...
            parcours_en_profondeur(d, v, visites)
    return visites

Corrigé

Barème indicatif (sur 6) : Q1 : 0,5 ; Q2 : 0,5 ; Q3 : 0,5 ; Q4 : 0,75 ; Q5 : 0,25 ; Q6 : 0,5 ; Q7 : 0,5 ; Q8 : 0,5 ; Q9 : 0,5 ; Q10 : 1,5

Partie A. 1.

2. (ordre G,J,Y,E,N,M,A,L)

matrice_adj = [[0,1,1,0,1,1,0,0],  # G
               [1,0,1,1,0,0,0,1],  # J
               [1,1,0,1,1,1,1,0],  # Y
               [0,1,1,0,1,0,0,0],  # E
               [1,0,1,1,0,0,0,0],  # N
               [1,0,1,0,0,0,1,0],  # M
               [0,0,1,0,0,1,0,0],  # A
               [0,1,0,0,0,0,0,0]]  # L

3. position(sommets,’G’) vaut 0 ; position(sommets,’Z’) vaut None.

4. Démarche : on cherche la ligne du sommet dans la matrice ; elle ne contient que des $0$ et des $1$, donc la somme de ses éléments est le nombre d’amis.

def nb_amis(L, m, s):
    pos_s = position(L, s)
    if pos_s == None:
        return None
    amis = 0
    for i in range(len(m)):
        amis += m[pos_s][i]
    return amis

5. nb_amis(sommets, matrice_adj, ’G’) vaut 4.

Partie B. 6. c est une clé (un sommet), v est la valeur associée (la liste de ses voisins).

7. Démarche : pour chaque personne (une clé), la liste de ses amis, lue dans l’énoncé.

graphe = {'G': ['J','Y','N','M'], 'J': ['G','Y','E','L'],
          'Y': ['G','J','E','N','M','A'], 'E': ['J','Y','N'],
          'N': ['G','Y','E'], 'M': ['G','Y','A'],
          'A': ['Y','M'], 'L': ['J']}

8. def nb_amis(d, s): return len(d[s])

9. Cercle d’amis de Lou (graphe des fâcheries) : [’L’,’J’,’G’,’Y’,’E’,’N’] — Milo et Anas ne sont plus atteignables.

▷ Erreur fréquente. Ajouter Milo et Anas au cercle d’amis de Lou : après les fâcheries, aucune chaîne ne relie L à M ou à A.

10. Démarche : on marque d’abord s comme visité, puis on relance le parcours sur chacun de ses voisins pas encore visités.

def parcours_en_profondeur(d, s, visites=None):
    if visites is None:
        visites = []
    visites.append(s)
    for v in d[s]:
        if v not in visites:
            parcours_en_profondeur(d, v, visites)
    return visites

★★ Exercice 14 — d’après Asie 2024, jour 1, ex. 2 #

≈ 30 min

La fabrication d’un pain se décompose en tâches ; un arc (i)$\to$(j) signifie « la tâche (i) doit être faite avant la tâche (j) ». On donne une partie du graphe des dépendances :

S’agit-il d’un graphe orienté ou non orienté ?
D’après le graphe, dire si l’on peut faire : (f) puis (g) ? (g) puis (f) ? (b) puis (e) ?
Donner toutes les tâches à réaliser nécessairement avant de pouvoir faire (l).

Coup de pouce

Q3 : remonter les arcs depuis (l), puis depuis chacun de ses prédécesseurs, et ainsi de suite.
Ce graphe contient-il un cycle ? Qu’est-ce que cela garantit sur la faisabilité de la recette ?
Un élève lance un parcours en profondeur depuis (b), puis depuis (d). Il applique la règle : « si l’on retombe sur un sommet déjà découvert qui n’est pas celui d’où l’on vient, il y a un cycle ». En arrivant de (d) sur (f), déjà découvert, il conclut à un cycle. Expliquer son erreur et donner le bon critère pour un graphe orienté.

Coup de pouce

Q5 : au moment où l’on arrive de (d), l’exploration de (f) est-elle encore en cours, ou déjà terminée ? Peut-on revenir de (f) vers (d) en suivant les flèches ?

On considère maintenant la matrice d’adjacence d’un graphe orienté (M[i][j] = 1 s’il existe un arc de i vers j).

M = [ [0, 1, 0, 0, 0],
      [0, 0, 1, 0, 0],
      [0, 0, 0, 1, 0],
      [0, 1, 0, 0, 1],
      [0, 0, 0, 0, 0] ]

Dessiner le graphe associé (les sommets sont leurs indices $0$ à $4$).
Déterminer s’il est possible de trouver un ordre de réalisation des tâches respectant toutes les dépendances. Si oui, le donner ; si non, expliquer pourquoi. (On parle d’un tri topologique du graphe.)

Coup de pouce

Q7 : chercher un cycle dans le graphe dessiné à la question 6 : que se passe-t-il si des tâches dépendent les unes des autres en boucle ?

Corrigé

Barème indicatif (sur 4) : Q1 : 0,25 ; Q2 : 0,5 ; Q3 : 0,5 ; Q4 : 0,5 ; Q5 : 1 ; Q6 : 0,5 ; Q7 : 0,75

1. Graphe orienté (les flèches donnent l’ordre « avant / après »).

2. (f) puis (g) : oui (arc f$\to$g). (g) puis (f) : non. (b) puis (e) : oui.

3. Tâches nécessaires avant (l) : b, d, e, f, g, h, i, k.

▷ Erreur fréquente. Ne citer que g et k, les prédécesseurs directs de (l) : il faut remonter tous les arcs, de prédécesseur en prédécesseur.

4. Non, pas de cycle. C’est indispensable : un cycle de dépendances rendrait la recette impossible à réaliser (chaque tâche attendrait l’autre).

5. La règle utilisée ne vaut que pour un graphe non orienté. Ici, (f) a été atteinte depuis (e) lors du premier parcours, qui l’a terminée ((f), (g), (l) entièrement explorés). Arriver de (d) sur (f) signifie seulement que deux chemins, (b)$\to$(e)$\to$(f) et (d)$\to$(f), se rejoignent : aucune flèche ne permet de revenir de (f) à (d). Bon critère pour un graphe orienté : au cours d’un parcours en profondeur, il y a un cycle lorsqu’un arc mène à un sommet en cours (encore dans la pile d’appels, pas encore terminé) ; un arc vers un sommet terminé ne signale pas de cycle.

6. Arcs : 0$\to$1, 1$\to$2, 2$\to$3, 3$\to$1, 3$\to$4.

7. Impossible : le graphe contient le cycle 1$\to$2$\to$3$\to$1. On ne peut donc pas ordonner ces tâches (aucun tri topologique n’existe quand il y a un cycle).

★★ Exercice 15 — d’après Pays étrangers 2025, sujet PE2, ex. 3 (partie A) #

≈ 30 min

Un parc d’attractions est modélisé par un graphe : chaque sommet est une attraction (de durée donnée), chaque arête porte la durée (en minutes) du trajet entre deux attractions.

Les attractions sont des objets de la classe suivante ; les voisines sont stockées sous forme de couples (attraction, durée_du_trajet).

class Attraction:
    def __init__(self, nom, duree):
        self.nom = nom
        self.duree = duree
        self.voisines = []

a1 = Attraction("Grand huit", 11)
a2 = Attraction("Petits chevaux", 6)
a3 = Attraction("Train fantome", 9)
a4 = Attraction("Grande roue", 10)
a1.voisines = [(a2, 7), (a3, 5)]
a2.voisines = [(a1, 7), (a3, 3), (a4, 4)]
a3.voisines = [(a1, 5), (a2, 3), (a4, 6)]
a4.voisines = ...

La grande roue est ralentie : sa durée passe à $12$ minutes. Écrire la ligne de code qui réalise cette modification.
Donner et expliquer la valeur de a2.voisines[2][1].

Coup de pouce

Q2 : a2.voisines[2] est un couple : que contient sa composante d’indice $1$ ?
Recopier et compléter la dernière ligne (a4.voisines = ...).
Expliquer pourquoi cette modélisation utilise un graphe non orienté.

Une balade est un chemin du graphe ; sa durée est la somme des durées de ses sommets et de ses arêtes. On modélise une balade par la liste des attractions parcourues.

Calculer la durée de la balade [a1, a2, a3] et expliquer le calcul.
Expliquer pourquoi [a2, a1, a4, a3] n’est pas une balade.
▶ Écrire sont_voisines(x, y) qui renvoie True si les attractions x et y sont voisines.

Coup de pouce

Q7 : parcourir les couples de x.voisines : seule leur première composante sert ici.
▶ Écrire est_balade(tab) qui renvoie True si la liste tab d’attractions est une balade (chaque attraction voisine de la suivante).

Coup de pouce

Q8 : réutiliser sont_voisines ; jusqu’à quel indice la boucle doit-elle aller pour que « la suivante » existe toujours ?

Corrigé

Barème indicatif (sur 4) : Q1 : 0,25 ; Q2 : 0,5 ; Q3 : 0,5 ; Q4 : 0,25 ; Q5 : 0,5 ; Q6 : 0,5 ; Q7 : 0,5 ; Q8 : 1

1. a4.duree = 12

2. a2.voisines[2][1] vaut 4 : dans le 3^e couple (a4, 4) de la liste des voisines de a2, on lit l’élément d’indice $1$, c’est-à-dire la durée du trajet (4 min) entre « Petits chevaux » et « Grande roue ».

3. a4.voisines = [(a2, 4), (a3, 6)]

4. Le trajet est le même dans les deux sens (aller de $x$ à $y$ prend le même temps que de $y$ à $x$) : la relation est symétrique, d’où un graphe non orienté.

5. Durée de [a1, a2, a3] $=$ (durées des attractions) $+$ (durées des trajets) $= (11+6+9) + (7+3) = \mathbf{36}$ min.

6. [a2, a1, a4, a3] n’est pas une balade car a4 n’est pas voisine de a1 : il n’y a pas d’arête entre « Grand huit » et « Grande roue ».

7–8. On parcourt les couples (voisine, durée) de x en cherchant y ; pour une balade, on vérifie que chaque attraction est voisine de la suivante, d’où la boucle jusqu’à l’avant-dernier indice.

def sont_voisines(x, y):
    for (v, duree) in x.voisines:
        if v == y:
            return True
    return False

def est_balade(tab):
    for i in range(len(tab) - 1):
        if not sont_voisines(tab[i], tab[i+1]):
            return False
    return True

Autre méthode pour sont_voisines : construire par compréhension la liste des seules attractions voisines (première composante des couples), puis tester l’appartenance.

def sont_voisines(x, y):
    voisines = [v for (v, duree) in x.voisines]
    return y in voisines

★★ Exercice 16 — d’après Centres étrangers 2024, groupe 1, jour 1, ex. 1 #

≈ 30 min

Un réseau de $5$ ordinateurs numérotés $0$ à $4$ est représenté par des listes de voisins.

Recopier et compléter la variable voisins (la case d’indice i contient la liste des voisins de i).

voisins = [[1, 2, 3, 4],
           [0, 2, 3],
           [0, 1],
           [...],
           [...]]

On ajoute un ordinateur $5$, accessible seulement depuis $0$ et $2$. Dessiner le nouveau graphe et donner la nouvelle variable voisins.
▶ Écrire voisin_alea(voisins, s) qui renvoie un voisin de s choisi au hasard. (On dispose de la fonction random.randrange(n), qui renvoie un entier de $0$ inclus à n exclu.)

Coup de pouce

Q3 : tirer au hasard un indice valide de la liste voisins[s].

Au début, un virus n’est présent que sur un ordinateur. À chaque étape, il contamine tous ses voisins non encore contaminés.

▶ Proposer (et programmer) un algorithme qui, à partir d’un sommet de départ s, renvoie le nombre d’étapes nécessaires pour contaminer tout le réseau.

Coup de pouce

Q4 : c’est un parcours en largeur « par vagues » : chaque vague de nouveaux contaminés correspond à une étape.

Coup de pouce 2 (début de solution)

Q4 :
contamines = [s]
frontiere = [s]
etapes = 0
while len(contamines) < len(voisins): … Construire la nouvelle frontière (la vague suivante) à partir des voisins de la frontière courante.

Corrigé

Barème indicatif (sur 4) : Q1 : 0,5 ; Q2 : 0,75 ; Q3 : 0,75 ; Q4 : 2

1. voisins = [[1,2,3,4], [0,2,3], [0,1], [0,1], [0]]

2. On ajoute le sommet $5$, relié à $0$ et $2$ : voisins = [[1,2,3,4,5], [0,2,3], [0,1,5], [0,1], [0], [0,2]].

3. Démarche : on tire au hasard un indice valide de la liste voisins[s], puis on renvoie le voisin situé à cet indice.

import random
def voisin_alea(voisins, s):
    liste = voisins[s]
    i = random.randrange(len(liste))
    return liste[i]

4. C’est un parcours en largeur « par vagues » : à chaque étape, on contamine tous les voisins non encore contaminés, et on compte les étapes.

def temps_propagation(voisins, s):
    contamines = [s]
    frontiere = [s]           # contamines a l'etape precedente
    etapes = 0
    while len(contamines) < len(voisins):
        nouveaux = []
        for x in frontiere:
            for v in voisins[x]:
                if v not in contamines:
                    contamines.append(v)
                    nouveaux.append(v)
        etapes = etapes + 1
        frontiere = nouveaux
    return etapes

Depuis le sommet $4$ (réseau initial), la contamination prend 2 étapes.

★★★ Exercice 17 — d’après Polynésie 2024, jour 2, ex. 1 #

≈ 45 min

Une agence de voyages relie des villes ; le graphe pondéré ci-dessous donne les distances (en km).

Déterminer le plus court chemin (en km) de Mp à Nc et sa longueur.

Coup de pouce

Q1 : Nc n’est relié qu’à Mr, To, Ax et Di : chercher d’abord la meilleure distance de Mp à chacune de ces villes.
On veut aller de Mp à Nc en visitant le moins de villes possible. Déterminer les deux chemins possibles.

On oublie désormais les distances (graphe non pondéré). On implémente le graphe par un dictionnaire de listes d’adjacence (sommets de type str).

Donner l’implémentation Python G de ce graphe (une paire clé/valeur par ligne).
Rappeler la signification de LIFO et FIFO. Lequel désigne une file ?

On donne la fonction parcours (la file utilise creerFile, estVide, enfiler, defiler) :

def parcours(graphe, sommet):
    f = creerFile()
    enfiler(f, sommet)
    visite = [sommet]
    while not estVide(f):
        s = defiler(f)
        for v in graphe[s]:
            if not (v in visite):
                visite.append(v)
                enfiler(f, v)
    return visite

S’agit-il d’un parcours en largeur ou en profondeur ? Justifier.
▶ En modifiant parcours, écrire distance(graphe, sommet) qui renvoie un dictionnaire donnant, pour chaque sommet, sa distance (nombre d’arêtes) au sommet de départ.

Coup de pouce

Q6 : remplacer la liste visite par un dictionnaire : un sommet découvert depuis s est à la distance de s plus $1$.

Coup de pouce 2 (début de solution)

Q6 : dist = {sommet: 0} remplace visite = [sommet] ; dans la boucle :
if not (v in dist):
dist[v] = dist[s] + 1 …
▶ Écrire une fonction parcours2(G, s) réalisant un parcours en profondeur à l’aide d’une pile. Donner un résultat possible de parcours2(G, ’Av’).

Coup de pouce

Q7 : même structure que parcours, en remplaçant la file par une pile ; un sommet n’est marqué visité qu’au moment où on le dépile.

Corrigé

Barème indicatif (sur 6) : Q1 : 0,75 ; Q2 : 0,5 ; Q3 : 0,75 ; Q4 : 0,5 ; Q5 : 0,5 ; Q6 : 1,5 ; Q7 : 1,5

1. Plus court chemin Mp$\to$Nc : Mp -- Ar -- Ax -- Nc, de longueur $80+76+176 = \mathbf{332}$ km.

2. En visitant le moins de villes possible (3 arêtes) : Mp -- Ar -- Ax -- Nc et Mp -- Ar -- Mr -- Nc.

3.

G = {'Av': ['Ni', 'Mr', 'Ax'],
     'Ni': ['Av', 'Ar', 'Mp'],
     'Mp': ['Ni', 'Ar'],
     'Ar': ['Ni', 'Mp', 'Ax', 'Mr'],
     'Mr': ['Av', 'Ar', 'To', 'Ax', 'Nc'],
     'To': ['Mr', 'Ax', 'Nc'],
     'Ax': ['Av', 'Ar', 'Mr', 'To', 'Nc', 'Di'],
     'Nc': ['Mr', 'To', 'Ax', 'Di'],
     'Di': ['Nc', 'Ax']}

4. LIFO $=$ Last In, First Out (pile) ; FIFO $=$ First In, First Out (file).

5. Parcours en largeur : la structure f est une file (on défile le premier entré), on découvre donc les sommets par distances croissantes.

6. Démarche : on remplace la liste visite par un dictionnaire de distances : le départ est à la distance $0$, et un sommet découvert depuis s est à la distance de s plus $1$.

def distance(graphe, sommet):
    dist = {sommet: 0}
    f = creerFile()
    enfiler(f, sommet)
    while not estVide(f):
        s = defiler(f)
        for v in graphe[s]:
            if v not in dist:
                dist[v] = dist[s] + 1
                enfiler(f, v)
    return dist

Ainsi distance(G, ’Av’) vaut :

{'Av':0, 'Ni':1, 'Mr':1, 'Ax':1, 'Ar':2, 'Mp':2, 'To':2, 'Nc':2, 'Di':2}

7. On remplace la file par une pile :

def parcours2(G, s):
    pile = [s]
    visite = []
    while pile != []:
        x = pile.pop()
        if x not in visite:
            visite.append(x)
            for v in G[x]:
                if v not in visite:
                    pile.append(v)
    return visite

Un résultat possible : parcours2(G, ’Av’) $=$ [’Av’,’Ax’,’Di’,’Nc’,’To’,’Mr’,’Ar’,’Mp’,’Ni’] (l’ordre dépend de l’ordre des voisins).

Critiquer une réponse d’IA#

★★ Exercice 18 — Un parcours en largeur écrit par un assistant d’IA #

Un élève demande à un assistant d’IA : « Écris en Python un parcours en largeur d’un graphe g (dictionnaire des listes d’adjacence) depuis un sommet depart, qui renvoie la liste des sommets dans l’ordre où ils sont traités. » Voici la réponse obtenue :

def parcours_largeur(g, depart):
    en_attente = [depart]          # file des sommets decouverts
    decouverts = [depart]
    traites = []
    while en_attente != []:
        sommet = en_attente.pop()  # on retire le prochain sommet
        for voisin in g[sommet]:
            if voisin not in decouverts:
                decouverts.append(voisin)
                en_attente.append(voisin)
        traites.append(sommet)
    return traites

« On découvre d’abord tous les voisins du départ, puis les voisins des voisins, etc. : la liste en_attente joue le rôle de la file du parcours en largeur, et decouverts évite de traiter deux fois un même sommet. »

La réponse est-elle correcte ? ▶ Dérouler la fonction à la main sur le graphe G = {’A’: [’B’, ’C’], ’B’: [’A’, ’D’], ’C’: [’A’, ’E’], ’D’: [’B’], ’E’: [’C’]} depuis ’A’ (noter l’état de en_attente à chaque tour) et comparer avec l’ordre attendu d’un parcours en largeur.
Localiser et corriger l’erreur.

Coup de pouce

Sans argument, pop() retire-t-il le premier ou le dernier élément de la liste ? Quelle structure obtient-on alors ?
Quelle vérification simple, faite avant de faire confiance à la réponse, aurait suffi à détecter l’erreur ?

Corrigé

1. Non. Trace : en_attente = [A] ; on retire A, on ajoute B puis C $\to$ [B, C] ; pop() retire le dernier, C, qui ajoute E $\to$ [B, E] ; on retire E ; puis B, qui ajoute D ; puis D. La fonction renvoie donc [’A’, ’C’, ’E’, ’B’, ’D’]. Or E est à distance $2$ de A et est traité avant B, à distance $1$ : ce n’est pas un parcours en largeur. La liste se comporte en pile : le parcours s’enfonce comme un parcours en profondeur (sur ce petit graphe sans cycle, on obtient même l’ordre de DFS_iteratif), mais ce n’en est pas tout à fait un en général, puisque les sommets sont marqués dès l’empilement (voir la règle du cours et son contre-exemple). L’ordre attendu est [’A’, ’B’, ’C’, ’D’, ’E’].

2. L’erreur : en_attente.pop() retire le dernier élément ajouté (comportement de pile, LIFO). Pour une file (FIFO), il faut retirer le premier :

        sommet = en_attente.pop(0)  # on defile (FIFO)

Avec cette ligne, la fonction renvoie [’A’, ’B’, ’C’, ’D’, ’E’]. C’est la correction la plus courte, et elle suffit sur un petit graphe ; mais c’est un choix de simplicité : chaque pop(0) décale toute la liste et coûte $O(n)$ (chapitre Structures linéaires). La version du cours, avec l’interface File (enfiler/defiler/est_vide), évite à la fois l’erreur de l’IA et ce coût caché.

3. Dérouler le code sur un graphe de quatre ou cinq sommets où un sommet est à distance $2$ : en largeur, tous les sommets à distance $1$ doivent sortir avant ceux à distance $2$. Réflexe du cours : « file (FIFO) $=$ largeur ; pile (LIFO) $=$ profondeur ». Sur une list, pop() retire le dernier élément : on obtient une pile, et le parcours n’est plus en largeur.

S’entraîner à l’oral#

★★ Exercice 19 — Expliquer en deux minutes #

Au Grand Oral comme devant l’examinateur de l’épreuve pratique, il faut savoir expliquer une notion clairement, sans lire ses notes. Choisir l’un des sujets suivants (ou le tirer au sort) :

Expliquer la différence entre le parcours en largeur et le parcours en profondeur d’un graphe, et la structure (pile ou file) utilisée par chacun.
Expliquer à un camarade de Première comment un graphe modélise un réseau routier ou un réseau social, avec le vocabulaire de base.
Expliquer comment choisir entre une matrice d’adjacence et une liste de successeurs pour représenter un graphe.

Préparation (5 min, seul). Noter au brouillon trois idées et un exemple, rien de plus : comme au Grand Oral, ces notes servent d’aide-mémoire. Exposé (2 min, chronométré). Debout, face à un camarade, sans lire ses notes et sans rien écrire : tout passe par la parole. Retour (2 min). Le camarade pose une question de relance (on peut alors s’aider d’un schéma), remplit la grille ci-dessous et donne un conseil ; puis on échange les rôles. Cette grille reprend les critères d’évaluation du Grand Oral.

Coup de pouce

Structurer chaque explication en trois temps : une définition en une phrase, un exemple petit et concret déroulé à voix haute, puis le piège (l’erreur que l’auditeur risque de faire). Finir par une phrase qui répond à la question posée. Prévoir un graphe de quatre sommets que l’on sait décrire à voix haute (« A est relié à B et à C…») et l’utiliser comme exemple. Sujet 1 : dans quel ordre les sommets sont-ils découverts ?

Grille entre camarades	Oui	En partie	Pas encore
Clair — audible, posé ; chaque mot technique est expliqué	▫	▫	▫
Juste — c’est exact, et l’exemple montre vraiment l’idée	▫	▫	▫
Construit — un fil conducteur, tenu en deux minutes, sans lire	▫	▫	▫
Un conseil pour la prochaine fois :

Corrigé

Pas de texte à apprendre par cœur : voici les éléments attendus pour chaque sujet. L’ordre, les mots et l’exemple peuvent être différents ; l’explication est réussie si ces idées y sont, justes et reliées entre elles.

Sujet 1.

Largeur : on visite tous les voisins du départ, puis les voisins de ces voisins, « par couches » de distance croissante ; on utilise une file.
Profondeur : on avance le plus loin possible le long d’un chemin, puis on revient en arrière ; on utilise une pile (ou la récursivité).
Exemple : arêtes A–B, A–C, B–D, en partant de A : largeur A, B, C, D ; profondeur A, B, D, C.
Piège : oublier de marquer les sommets déjà visités (boucle sans fin dès qu’il y a un cycle) ; le parcours en largeur donne un plus court chemin en nombre d’arêtes.

Sujet 2.

Sommets : les lieux ou les personnes ; arêtes (ou arcs si le graphe est orienté) : les routes ou les liens ; un poids peut porter une distance.
Vocabulaire : voisins (adjacents), chemin, cycle, graphe connexe.
Exemple : un sens unique ou « suivre » quelqu’un sur un réseau social donne un graphe orienté ; une amitié réciproque, un graphe non orienté.
Intérêt : un même algorithme (parcours, plus court chemin) résout des problèmes très différents dès qu’ils sont modélisés par un graphe.

Sujet 3.

Matrice d’adjacence : tableau $n \times n$ où la case $[i][j]$ vaut $1$ si $i$ et $j$ sont voisins ; tester une arête est immédiat, mais il faut $n^2$ cases même s’il y a peu d’arêtes.
Liste de successeurs (un dictionnaire qui associe à chaque sommet la liste de ses voisins) : la mémoire est proportionnelle au nombre d’arêtes, et parcourir les voisins d’un sommet est rapide.
Exemple : un réseau social de millions de personnes ayant chacune quelques centaines d’amis : la liste s’impose.
Piège : pour un graphe non orienté, la matrice est symétrique et chaque arête apparaît deux fois dans les listes.

Entraînement#

Des séries courtes pour rendre une méthode automatique : même consigne, données différentes. Les réponses sont brèves dans le corrigé.

★ Exercice 20 — Parcours à la main en série #

• essentiel Pour chacun des trois graphes ci-dessous, donner l’ordre de visite du parcours en largeur depuis A, en écrivant le contenu de la file après chaque sommet défilé, puis l’ordre de visite du parcours en profondeur récursif (fonction DFS du cours) depuis A. Les voisins sont toujours pris par ordre alphabétique. Répondre enfin à la question propre à chaque graphe.

Coup de pouce

En largeur : on défile le sommet de tête, on enfile ses voisins non encore découverts, par ordre alphabétique, puis on note la file. En profondeur : on visite un sommet, puis on relance le parcours sur son premier voisin non encore visité ; on ne revient en arrière qu’à l’impasse. Dans les deux cas, un sommet déjà découvert n’est jamais repris.

Un graphe orienté : on ne suit un arc que dans le sens de la flèche (les voisins d’un sommet sont ses successeurs). Quel sommet n’est jamais visité, et pourquoi ?
Un graphe non connexe. Quels sommets ne sont pas visités ? Comment compléter le travail pour visiter tous les sommets du graphe ?
Un graphe avec des cycles. Pourquoi aucun des deux parcours ne tourne-t-il en rond ?

Corrigé

La file est écrite dans l’ordre de sortie (le prochain sommet à défiler en premier).

a) Largeur : A (file B, D) ; B (D, C, E) ; D (C, E) ; C (E) ; E (vide). Ordre A, B, D, C, E. Profondeur : A, B, C, E, D. Le sommet F n’est jamais visité : l’arc F$\to$D part de F, mais aucun arc n’arrive sur F ; en suivant les flèches depuis A, on ne peut pas l’atteindre.

▷ Erreur fréquente. Visiter F depuis D parce que les deux sommets sont reliés : dans un graphe orienté, on ne suit que les successeurs, et F n’est pas un successeur de D.

b) Largeur : A (B, C) ; B (C, D) ; C (D) ; D (vide). Ordre A, B, C, D. Profondeur : A, B, D, C. Les sommets E, F, G ne sont pas visités : aucune chaîne ne les relie à A (le graphe n’est pas connexe). Pour tout visiter, on relance un parcours depuis un sommet non visité, par exemple E (qui donne E, F, G), et ainsi de suite tant qu’il reste des sommets non visités.

c) Largeur : A (B, D) ; B (D, C) ; D (C) ; C (E) ; E (F, G) ; F (G) ; G (vide). Ordre A, B, D, C, E, F, G. Profondeur : A, B, C, D, E, F, G. Les parcours ne tournent pas en rond parce qu’un sommet déjà découvert (en largeur) ou déjà visité (en profondeur) n’est jamais repris : en traitant D, on ne revient ni vers A ni vers C.

Exercices#

Vocabulaire et modélisation#

★ Exercice 1 #

★ Exercice 2 #

★ Exercice 3 #

Représenter un graphe#

★ Exercice 4 #

★ Exercice 5 #

★★ Exercice 6 — ▶ #

★★ Exercice 7 #

La classe Graphe#

★★ Exercice 8 — ▶ #

Parcourir un graphe#

★★ Exercice 9 #

★★ Exercice 10 — ▶ #

Chemins, cycles, connexité#

★★ Exercice 11 — ▶ #

★★★ Exercice 12 — ▶ #

Vers le bac#

★★ Exercice 13 — d’après Amérique du Nord 2024, jour 1, ex. 2 #

★★ Exercice 14 — d’après Asie 2024, jour 1, ex. 2 #

★★ Exercice 15 — d’après Pays étrangers 2025, sujet PE2, ex. 3 (partie A) #

★★ Exercice 16 — d’après Centres étrangers 2024, groupe 1, jour 1, ex. 1 #

★★★ Exercice 17 — d’après Polynésie 2024, jour 2, ex. 1 #

Critiquer une réponse d’IA#

★★ Exercice 18 — Un parcours en largeur écrit par un assistant d’IA #

S’entraîner à l’oral#

★★ Exercice 19 — Expliquer en deux minutes #

Entraînement#

★ Exercice 20 — Parcours à la main en série #

La classe `Graphe`#