\documentclass[10pt,aspectratio=169]{beamer}

% --- Thème ---
\usetheme[language=french]{Celestia}

% Avec [allowframebreaks] sur les frames de questions, Beamer ajoute
% par défaut « (1) », « (2) », « (3) »... sur chaque sous-slide. On
% supprime entièrement cette annotation : un template vide pour
% « frametitle continuation ». L'enseignant identifie visuellement la
% continuation par le contenu de la slide. (Les variantes [from second]
% et [roman] interagissent mal avec un titre contenant \textemdash{}
% sous Celestia : elles déclenchent une erreur « Missing $ inserted ».)
\setbeamertemplate{frametitle continuation}{}

\subject{Numérique et sciences informatiques}
\title{Graphes}
\subtitle{QCM}
\author{Terminale}
\date{\today}

\begin{document}

\begin{frame}
    \titlepage
\end{frame}

% Q1 - Réponse en C
\begin{frame}[fragile]{Question 1 \textemdash{} Définition d'un graphe}
    Qu'est-ce qu'un \textbf{graphe} en informatique ?\medskip
    \begin{itemize}
        \item[A.] Un type d'arbre
        \item[B.] Une représentation visuelle de données numériques (camembert, histogramme)
        \item[\alert<2>{C.}] \alert<2>{Un ensemble de sommets (ou nœuds) reliés par des arêtes (ou arcs si orientés)}
        \item[D.] Un dictionnaire trié
    \end{itemize}
\end{frame}

% Q2 - Réponse en A
\begin{frame}[fragile]{Question 2 \textemdash{} Graphe orienté}
    Quelle est la différence entre un graphe \textbf{orienté} et
un graphe \textbf{non orienté} ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Dans un graphe orienté, chaque arête a un sens (de A vers B), alors que dans un graphe non orienté, l'arête relie A et B sans préférence}
        \item[B.] Un graphe orienté n'a pas de cycle
        \item[C.] Le graphe orienté contient plus de sommets
        \item[D.] Un graphe non orienté est plus rapide à parcourir
    \end{itemize}
\end{frame}

% Q3 - Réponse en D
\begin{frame}[fragile]{Question 3 \textemdash{} Graphe pondéré}
    Qu'est-ce qu'un graphe \textbf{pondéré} ?\medskip
    \begin{itemize}
        \item[A.] Un graphe avec beaucoup d'arêtes
        \item[B.] Un graphe partagé entre plusieurs utilisateurs
        \item[C.] Un graphe trop lourd à stocker en mémoire
        \item[\alert<2>{D.}] \alert<2>{Un graphe où chaque arête porte un poids (valeur numérique), représentant par exemple une distance, un coût, un temps}
    \end{itemize}
\end{frame}

% Q4 - Réponse en A
\begin{frame}[fragile]{Question 4 \textemdash{} Matrice d'adjacence}
    Une \textbf{matrice d'adjacence} d'un graphe à $n$ sommets est :\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Une matrice $n \times n$ où $M[i][j] = 1$ s'il existe une arête entre $i$ et $j$, sinon $0$ (ou le poids de l'arête si pondéré)}
        \item[B.] Un tableau $1 \times n$ contenant les degrés
        \item[C.] Un arbre
        \item[D.] Un dictionnaire de listes
    \end{itemize}
\end{frame}

% Q5 - Réponse en D
\begin{frame}[fragile]{Question 5 \textemdash{} Liste d'adjacence}
    Une \textbf{liste d'adjacence} d'un graphe consiste à :\medskip
    \begin{itemize}
        \item[A.] Stocker uniquement les sommets isolés
        \item[B.] Trier les sommets par degré
        \item[C.] Numéroter les arêtes de $1$ à $m$
        \item[\alert<2>{D.}] \alert<2>{Stocker pour chaque sommet la liste de ses voisins}
    \end{itemize}
\end{frame}

% Q6 - Réponse en A
\begin{frame}[fragile]{Question 6 \textemdash{} Parcours en largeur}
    Le parcours en \textbf{largeur} d'un graphe :\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Visite d'abord tous les voisins du sommet de départ, puis tous leurs voisins non visités, et ainsi de suite par niveaux}
        \item[B.] Parcourt la branche la plus profonde d'abord
        \item[C.] Trie les sommets par valeur
        \item[D.] Visite uniquement les feuilles
    \end{itemize}
\end{frame}

% Q7 - Réponse en A
\begin{frame}[fragile]{Question 7 \textemdash{} Parcours en profondeur}
    Le parcours en \textbf{profondeur} d'un graphe :\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Explore aussi loin que possible une branche avant de revenir en arrière pour explorer une autre}
        \item[B.] Trie les sommets par profondeur
        \item[C.] Visite tous les voisins du sommet de départ avant d'aller plus loin
        \item[D.] Calcule la longueur totale du graphe
    \end{itemize}
\end{frame}

% Q8 - Réponse en C
\begin{frame}[fragile]{Question 8 \textemdash{} Structure utilisée par parcours en largeur}
    Pour implémenter un parcours en largeur, quelle structure
de données utilise-t-on naturellement ?\medskip
    \begin{itemize}
        \item[A.] Un dictionnaire
        \item[B.] Une pile
        \item[\alert<2>{C.}] \alert<2>{Une file (FIFO)}
        \item[D.] Aucune structure
    \end{itemize}
\end{frame}

% Q9 - Réponse en D
\begin{frame}[fragile]{Question 9 \textemdash{} Structure utilisée par parcours en profondeur}
    Le parcours en profondeur peut s'implémenter en utilisant :\medskip
    \begin{itemize}
        \item[A.] Une file uniquement
        \item[B.] Un graphe imbriqué
        \item[C.] Un arbre binaire
        \item[\alert<2>{D.}] \alert<2>{Une pile (explicite ou la pile d'appels via la récursivité)}
    \end{itemize}
\end{frame}

% Q10 - Réponse en B
\begin{frame}[fragile]{Question 10 \textemdash{} Plus court chemin}
    Pour trouver le plus court chemin (en nombre d'arêtes)
entre deux sommets dans un graphe \textbf{non pondéré}, on
utilise :\medskip
    \begin{itemize}
        \item[A.] Un tri topologique
        \item[\alert<2>{B.}] \alert<2>{Un parcours en largeur}
        \item[C.] Un parcours en profondeur
        \item[D.] L'algorithme de Dijkstra
    \end{itemize}
\end{frame}

% Q11 - Réponse en A
\begin{frame}[fragile]{Question 11 \textemdash{} Degré d'un sommet}
    Le \textbf{degré} d'un sommet dans un graphe non orienté
est :\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Le nombre d'arêtes incidentes à ce sommet (i.e. le nombre de voisins).}
        \item[B.] Le poids de l'arête la plus lourde incidente au sommet
        \item[C.] La distance jusqu'à la racine
        \item[D.] Sa profondeur dans un parcours
    \end{itemize}
\end{frame}

% Q12 - Réponse en D
\begin{frame}[fragile]{Question 12 \textemdash{} Cycle dans un graphe}
    Un \textbf{cycle} dans un graphe est :\medskip
    \begin{itemize}
        \item[A.] Un sommet isolé
        \item[B.] Une arête répétée
        \item[C.] Un sommet de degré pair
        \item[\alert<2>{D.}] \alert<2>{Une suite d'arêtes qui revient à son point de départ}
    \end{itemize}
\end{frame}

% Q13 - Réponse en C
\begin{frame}[fragile]{Question 13 \textemdash{} Graphe connexe}
    Un graphe non orienté est \textbf{connexe} quand :\medskip
    \begin{itemize}
        \item[A.] Il est orienté
        \item[B.] Il a beaucoup d'arêtes
        \item[\alert<2>{C.}] \alert<2>{Il existe un chemin entre toute paire de sommets}
        \item[D.] Il a au moins $n$ arêtes
    \end{itemize}
\end{frame}

% Q14 - Réponse en D
\begin{frame}[fragile]{Question 14 \textemdash{} DAG}
    Que signifie l'acronyme \textbf{DAG} ?\medskip
    \begin{itemize}
        \item[A.] Décomposition d'Algorithme par Graphe
        \item[B.] Distribution Aléatoire de Graphes
        \item[C.] Données Algorithmiques Génériques
        \item[\alert<2>{D.}] \alert<2>{Directed Acyclic Graph (graphe orienté acyclique)}
    \end{itemize}
\end{frame}

% Q15 - Réponse en A
\begin{frame}[fragile]{Question 15 \textemdash{} Espace mémoire matrice vs liste}
    Pour un graphe à $n = 1000$ sommets et $m = 5000$
arêtes, quelle représentation est la plus économe en
mémoire ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{La liste d'adjacence ($O(n + m) = 6000$ entrées)}
        \item[B.] La matrice d'adjacence ($O(n^2) = 10^6$ cases)
        \item[C.] Aucune différence
        \item[D.] Cela dépend du langage de programmation
    \end{itemize}
\end{frame}

% Q16 - Réponse en D
\begin{frame}[fragile]{Question 16 \textemdash{} Parcours en largeur et distance}
    Avec un parcours en largeur depuis le sommet $s$, on calcule pour chaque
sommet $v$ atteignable :\medskip
    \begin{itemize}
        \item[A.] Les sommets isolés
        \item[B.] Tous les chemins possibles
        \item[C.] Le poids minimal du chemin $s \to v$ (si pondéré)
        \item[\alert<2>{D.}] \alert<2>{Le nombre minimal d'arêtes du chemin $s \to v$}
    \end{itemize}
\end{frame}

% Q17 - Réponse en A
\begin{frame}[fragile]{Question 17 \textemdash{} Application réseau social}
    Sur un réseau social, on veut trouver tous les amis
« à distance $2$ » (amis d'amis) d'un utilisateur $u$.
Quel algorithme utiliser ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Un parcours en largeur, en s'arrêtant à la profondeur $2$}
        \item[B.] Un tri des amis par valeur d'identifiant
        \item[C.] Un parcours en profondeur sans limite
        \item[D.] Une recherche dichotomique
    \end{itemize}
\end{frame}

% Q18 - Réponse en D
\begin{frame}[fragile]{Question 18 \textemdash{} Liste d'adjacence en Python}
    Comment représenter naturellement une liste d'adjacence
en Python ?\medskip
    \begin{itemize}
        \item[A.] Comme un entier
        \item[B.] Comme un tuple unique
        \item[C.] Comme une chaîne de caractères
        \item[\alert<2>{D.}] \alert<2>{Comme un dictionnaire où la clé est un sommet et la valeur est la liste de ses voisins}
    \end{itemize}
\end{frame}

% Q19 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 19 \textemdash{} Code parcours en largeur}
    Quelle fonction Python implémente correctement un parcours en largeur
depuis un sommet \texttt{depart} dans un graphe \texttt{g} (dictionnaire) ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def bfs(g, depart):
    return [v for v in g]
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
def bfs(g, depart):
    visites = {depart}
    from collections import deque
    f = deque([depart])
    while f:
        v = f.popleft()
        for w in g[v]:
            if w not in visites:
                visites.add(w)
                f.append(w)
    return visites
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
def bfs(g, depart):
    return g[depart]
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
def bfs(g, depart):
    return sorted(g.keys())
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q19 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 19 \textemdash{} Code parcours en largeur}
    Quelle fonction Python implémente correctement un parcours en largeur
depuis un sommet \texttt{depart} dans un graphe \texttt{g} (dictionnaire) ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def bfs(g, depart):
    return [v for v in g]
\end{lstlisting}

        \item[\alert{B.}]~\\
\begin{lstlisting}
def bfs(g, depart):
    visites = {depart}
    from collections import deque
    f = deque([depart])
    while f:
        v = f.popleft()
        for w in g[v]:
            if w not in visites:
                visites.add(w)
                f.append(w)
    return visites
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
def bfs(g, depart):
    return g[depart]
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
def bfs(g, depart):
    return sorted(g.keys())
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q20 - Réponse en A
\begin{frame}[fragile]{Question 20 \textemdash{} Arbre comme cas particulier}
    Un \textbf{arbre} (au sens informatique) est un cas
particulier de :\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Graphe : c'est un graphe non orienté, connexe et acyclique}
        \item[B.] Tableau
        \item[C.] File
        \item[D.] Pile
    \end{itemize}
\end{frame}

% Q21 - Réponse en A
\begin{frame}[fragile]{Question 21 \textemdash{} Algorithme de Dijkstra}
    L'algorithme de \textbf{Dijkstra} calcule les plus courts
chemins depuis une source dans un graphe pondéré. Quelle
est sa contrainte sur les poids ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Les poids doivent être positifs ou nuls (pas de poids négatifs)}
        \item[B.] Les poids doivent être entiers
        \item[C.] Les poids doivent être triés à l'avance
        \item[D.] Les poids doivent être tous identiques
    \end{itemize}
\end{frame}

% Q22 - Réponse en A
\begin{frame}[fragile]{Question 22 \textemdash{} Tri topologique}
    Un \textbf{tri topologique} d'un DAG :\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Range les sommets dans un ordre tel que pour chaque arête $u \to v$, $u$ apparaît avant $v$}
        \item[B.] Trie les sommets par valeur croissante
        \item[C.] Élimine les cycles
        \item[D.] Trie les sommets par degré
    \end{itemize}
\end{frame}

% Q23 - Réponse en B
\begin{frame}[fragile]{Question 23 \textemdash{} Composantes connexes}
    Pour calculer les \textbf{composantes connexes} d'un graphe
non orienté, on peut :\medskip
    \begin{itemize}
        \item[A.] Utiliser une recherche dichotomique
        \item[\alert<2>{B.}] \alert<2>{Lancer un parcours en largeur (ou parcours en profondeur) depuis chaque sommet non encore visité ; chaque parcours visite une composante}
        \item[C.] Compter les sommets
        \item[D.] Trier les sommets par numéro
    \end{itemize}
\end{frame}

% Q24 - Réponse en D
\begin{frame}[fragile]{Question 24 \textemdash{} Arbre couvrant}
    Un \textbf{arbre couvrant} d'un graphe connexe est :\medskip
    \begin{itemize}
        \item[A.] Un sous-graphe qui contient toutes les arêtes
        \item[B.] Une racine du graphe
        \item[C.] Un cycle qui passe par tous les sommets
        \item[\alert<2>{D.}] \alert<2>{Un sous-graphe qui contient tous les sommets et forme un arbre (connexe, sans cycle)}
    \end{itemize}
\end{frame}

% Q25 - Réponse en D
\begin{frame}[fragile]{Question 25 \textemdash{} Choisir le bon algorithme}
    Vous voulez calculer le chemin le plus court entre deux
villes sur un réseau routier (les routes ont des
longueurs en kilomètres positives). Quel algorithme
choisir ?\medskip
    \begin{itemize}
        \item[A.] parcours en profondeur
        \item[B.] parcours en largeur
        \item[C.] Tri topologique
        \item[\alert<2>{D.}] \alert<2>{L'algorithme de Dijkstra (les poids sont positifs)}
    \end{itemize}
\end{frame}

% Q26 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Conversion entre représentations}
    Soit le graphe non orienté représenté par la
liste d'adjacence
\texttt{g = \{'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B']\}}.
Quelle est la matrice d'adjacence correspondante
avec l'ordre des sommets \texttt{[A, B, C]} ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
[[0, 1, 0],
 [1, 0, 1],
 [0, 1, 0]]
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
[[0, 1, 1],
 [1, 0, 1],
 [1, 1, 0]]
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q26 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Conversion entre représentations}
    Soit le graphe non orienté représenté par la
liste d'adjacence
\texttt{g = \{'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B']\}}.
Quelle est la matrice d'adjacence correspondante
avec l'ordre des sommets \texttt{[A, B, C]} ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
[[0, 1, 0],
 [1, 0, 1],
 [0, 1, 0]]
\end{lstlisting}

        \item[\alert{B.}]~\\
\begin{lstlisting}
[[0, 1, 1],
 [1, 0, 1],
 [1, 1, 0]]
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q27 - Réponse en D
\begin{frame}[fragile]{Question 27 \textemdash{} Théorème des poignées de mains}
    Dans un graphe \textbf{non orienté}, quelle relation
relie la somme $S$ des degrés de tous les
sommets et le nombre $m$ d'arêtes ?\medskip
    \begin{itemize}
        \item[A.] $S = n$ (nombre de sommets)
        \item[B.] $S = m$
        \item[C.] $S = m^2$
        \item[\alert<2>{D.}] \alert<2>{$S = 2m$}
    \end{itemize}
\end{frame}

% Q28 - Réponse en A
\begin{frame}[fragile]{Question 28 \textemdash{} Trace d'un parcours en largeur}
    On effectue un parcours en largeur du graphe
\texttt{g = \{'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C', 'E'], 'E': ['D']\}}
en partant de \texttt{'A'}, en visitant les voisins
dans l'ordre où ils apparaissent dans la liste.
Dans quel ordre les sommets sont-ils visités ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{A, B, C, D, E
}
        \item[B.] A, B, D, E, C

        \item[C.] A, C, B, D, E

        \item[D.] A, B, C, E, D

    \end{itemize}
\end{frame}

% Q29 - Réponse en D
\begin{frame}[fragile]{Question 29 \textemdash{} Trace de l'algorithme de Dijkstra}
    On considère le graphe pondéré suivant
(arêtes non orientées) :
\texttt{A-B (4)}, \texttt{A-C (2)}, \texttt{B-C (1)}, \texttt{B-D (5)},
\texttt{C-D (8)}, \texttt{C-E (10)}, \texttt{D-E (2)}. On lance
Dijkstra depuis le sommet \texttt{A}. Quelle est la
distance minimale de \texttt{A} à \texttt{E} ?\medskip
    \begin{itemize}
        \item[A.] $14$ (en passant par \texttt{A-B-D-E})
        \item[B.] $12$ (en passant directement par \texttt{C-E})
        \item[C.] $11$
        \item[\alert<2>{D.}] \alert<2>{$10$}
    \end{itemize}
\end{frame}

% Q30 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 30 \textemdash{} Code du parcours en profondeur récursif}
    Quel code Python implémente correctement un
parcours en profondeur récursif d'un graphe \texttt{g}
(dictionnaire d'adjacence) à partir d'un
sommet \texttt{depart} ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def parcours_profondeur(g, depart, visites=None):
    if visites is None:
        visites = set()
    visites.add(depart)
    for voisin in g[depart]:
        if voisin not in visites:
            parcours_profondeur(g, voisin, visites)
    return visites
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
def parcours_profondeur(g, depart):
    for voisin in g[depart]:
        parcours_profondeur(g, voisin)
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
def parcours_profondeur(g, depart):
    return list(g[depart])
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
def parcours_profondeur(g, depart, visites={}):
    visites[depart] = True
    for voisin in g[depart]:
        if voisin not in visites:
            parcours_profondeur(g, voisin, visites)
    return visites
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q30 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 30 \textemdash{} Code du parcours en profondeur récursif}
    Quel code Python implémente correctement un
parcours en profondeur récursif d'un graphe \texttt{g}
(dictionnaire d'adjacence) à partir d'un
sommet \texttt{depart} ?\medskip
    \begin{itemize}
        \item[\alert{A.}]~\\
\begin{lstlisting}
def parcours_profondeur(g, depart, visites=None):
    if visites is None:
        visites = set()
    visites.add(depart)
    for voisin in g[depart]:
        if voisin not in visites:
            parcours_profondeur(g, voisin, visites)
    return visites
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
def parcours_profondeur(g, depart):
    for voisin in g[depart]:
        parcours_profondeur(g, voisin)
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
def parcours_profondeur(g, depart):
    return list(g[depart])
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
def parcours_profondeur(g, depart, visites={}):
    visites[depart] = True
    for voisin in g[depart]:
        if voisin not in visites:
            parcours_profondeur(g, voisin, visites)
    return visites
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q31 - Réponse en A
\begin{frame}[fragile]{Question 31 \textemdash{} Détection de cycle dans un graphe orienté}
    Comment \textbf{détecter la présence d'un cycle}
dans un graphe \textbf{orienté} à l'aide d'un
parcours en profondeur ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{On marque chaque sommet avec trois états :
non visité, en cours de visite
(sur la pile d'appels actuelle), et
terminé. Si pendant le parcours, on
rencontre une arête vers un sommet « en
cours de visite », on a détecté un cycle
}
        \item[B.] On compte simplement le nombre d'arêtes :
s'il dépasse $n - 1$, il y a un cycle

        \item[C.] Il est impossible de détecter un cycle en
temps polynomial

        \item[D.] On regarde si la matrice d'adjacence est
symétrique

    \end{itemize}
\end{frame}

% Q32 - Réponse en C
\begin{frame}[fragile]{Question 32 \textemdash{} Algorithme de Kahn pour le tri topologique}
    Quel est le principe de l'\textbf{algorithme de
Kahn} pour calculer un tri topologique d'un
DAG ?\medskip
    \begin{itemize}
        \item[A.] On effectue un parcours en largeur depuis
le premier sommet

        \item[B.] On trie les sommets par ordre alphabétique
de leur identifiant

        \item[\alert<2>{C.}] \alert<2>{On retire répétitivement les sommets de
degré entrant nul (qui ne dépendent
de rien) ; à chaque retrait, on les
ajoute à la liste de sortie et on
décrémente le degré entrant de leurs
voisins. On continue jusqu'à ce qu'il ne
reste plus aucun sommet
}
        \item[D.] On calcule la matrice d'adjacence puis on
cherche les valeurs propres

    \end{itemize}
\end{frame}

\begin{frame}[standout]{}
    Fin de l'évaluation
\end{frame}

\end{document}
