\documentclass[a4paper,11pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais,bloc,completemulti]{automultiplechoice}
\usepackage[french]{babel}
\usepackage{amsmath, amssymb}

\title{Graphes}
\date{Numérique et sciences informatiques}

\begin{document}

\noindent\textbf{Graphes} \hfill \textit{Numérique et sciences informatiques}\\[0.4em]
Nom~: \dotfill\ Prénom~: \dotfill

\bigskip

\element{terminalegraphes}{
  \begin{question}{q01}
    Qu'est-ce qu'un \textbf{graphe} en informatique ?
    \begin{choices}
    \wrongchoice{Un type d'arbre}
    \wrongchoice{Une représentation visuelle de données numériques (camembert, histogramme)}
    \correctchoice{Un ensemble de sommets (ou nœuds) reliés par des arêtes (ou arcs si orientés)}
    \wrongchoice{Un dictionnaire trié}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q02}
    Quelle est la différence entre un graphe \textbf{orienté} et
un graphe \textbf{non orienté} ?
    \begin{choices}
    \correctchoice{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}
    \wrongchoice{Un graphe orienté n'a pas de cycle}
    \wrongchoice{Le graphe orienté contient plus de sommets}
    \wrongchoice{Un graphe non orienté est plus rapide à parcourir}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q03}
    Qu'est-ce qu'un graphe \textbf{pondéré} ?
    \begin{choices}
    \wrongchoice{Un graphe avec beaucoup d'arêtes}
    \wrongchoice{Un graphe partagé entre plusieurs utilisateurs}
    \wrongchoice{Un graphe trop lourd à stocker en mémoire}
    \correctchoice{Un graphe où chaque arête porte un poids (valeur numérique), représentant par exemple une distance, un coût, un temps}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q04}
    Une \textbf{matrice d'adjacence} d'un graphe à $n$ sommets est :
    \begin{choices}
    \correctchoice{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é)}
    \wrongchoice{Un tableau $1 \times n$ contenant les degrés}
    \wrongchoice{Un arbre}
    \wrongchoice{Un dictionnaire de listes}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q05}
    Une \textbf{liste d'adjacence} d'un graphe consiste à :
    \begin{choices}
    \wrongchoice{Stocker uniquement les sommets isolés}
    \wrongchoice{Trier les sommets par degré}
    \wrongchoice{Numéroter les arêtes de $1$ à $m$}
    \correctchoice{Stocker pour chaque sommet la liste de ses voisins}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q06}
    Le parcours en \textbf{largeur} d'un graphe :
    \begin{choices}
    \correctchoice{Visite d'abord tous les voisins du sommet de départ, puis tous leurs voisins non visités, et ainsi de suite par niveaux}
    \wrongchoice{Parcourt la branche la plus profonde d'abord}
    \wrongchoice{Trie les sommets par valeur}
    \wrongchoice{Visite uniquement les feuilles}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q07}
    Le parcours en \textbf{profondeur} d'un graphe :
    \begin{choices}
    \correctchoice{Explore aussi loin que possible une branche avant de revenir en arrière pour explorer une autre}
    \wrongchoice{Trie les sommets par profondeur}
    \wrongchoice{Visite tous les voisins du sommet de départ avant d'aller plus loin}
    \wrongchoice{Calcule la longueur totale du graphe}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q08}
    Pour implémenter un parcours en largeur, quelle structure
de données utilise-t-on naturellement ?
    \begin{choices}
    \wrongchoice{Un dictionnaire}
    \wrongchoice{Une pile}
    \correctchoice{Une file (FIFO)}
    \wrongchoice{Aucune structure}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q09}
    Le parcours en profondeur peut s'implémenter en utilisant :
    \begin{choices}
    \wrongchoice{Une file uniquement}
    \wrongchoice{Un graphe imbriqué}
    \wrongchoice{Un arbre binaire}
    \correctchoice{Une pile (explicite ou la pile d'appels via la récursivité)}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q10}
    Pour trouver le plus court chemin (en nombre d'arêtes)
entre deux sommets dans un graphe \textbf{non pondéré}, on
utilise :
    \begin{choices}
    \wrongchoice{Un tri topologique}
    \correctchoice{Un parcours en largeur}
    \wrongchoice{Un parcours en profondeur}
    \wrongchoice{L'algorithme de Dijkstra}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q11}
    Le \textbf{degré} d'un sommet dans un graphe non orienté
est :
    \begin{choices}
    \correctchoice{Le nombre d'arêtes incidentes à ce sommet (i.e. le nombre de voisins).}
    \wrongchoice{Le poids de l'arête la plus lourde incidente au sommet}
    \wrongchoice{La distance jusqu'à la racine}
    \wrongchoice{Sa profondeur dans un parcours}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q12}
    Un \textbf{cycle} dans un graphe est :
    \begin{choices}
    \wrongchoice{Un sommet isolé}
    \wrongchoice{Une arête répétée}
    \wrongchoice{Un sommet de degré pair}
    \correctchoice{Une suite d'arêtes qui revient à son point de départ}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q13}
    Un graphe non orienté est \textbf{connexe} quand :
    \begin{choices}
    \wrongchoice{Il est orienté}
    \wrongchoice{Il a beaucoup d'arêtes}
    \correctchoice{Il existe un chemin entre toute paire de sommets}
    \wrongchoice{Il a au moins $n$ arêtes}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q14}
    Que signifie l'acronyme \textbf{DAG} ?
    \begin{choices}
    \wrongchoice{Décomposition d'Algorithme par Graphe}
    \wrongchoice{Distribution Aléatoire de Graphes}
    \wrongchoice{Données Algorithmiques Génériques}
    \correctchoice{Directed Acyclic Graph (graphe orienté acyclique)}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q15}
    Pour un graphe à $n = 1000$ sommets et $m = 5000$
arêtes, quelle représentation est la plus économe en
mémoire ?
    \begin{choices}
    \correctchoice{La liste d'adjacence ($O(n + m) = 6000$ entrées)}
    \wrongchoice{La matrice d'adjacence ($O(n^2) = 10^6$ cases)}
    \wrongchoice{Aucune différence}
    \wrongchoice{Cela dépend du langage de programmation}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q16}
    Avec un parcours en largeur depuis le sommet $s$, on calcule pour chaque
sommet $v$ atteignable :
    \begin{choices}
    \wrongchoice{Les sommets isolés}
    \wrongchoice{Tous les chemins possibles}
    \wrongchoice{Le poids minimal du chemin $s \to v$ (si pondéré)}
    \correctchoice{Le nombre minimal d'arêtes du chemin $s \to v$}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q17}
    Sur un réseau social, on veut trouver tous les amis
« à distance $2$ » (amis d'amis) d'un utilisateur $u$.
Quel algorithme utiliser ?
    \begin{choices}
    \correctchoice{Un parcours en largeur, en s'arrêtant à la profondeur $2$}
    \wrongchoice{Un tri des amis par valeur d'identifiant}
    \wrongchoice{Un parcours en profondeur sans limite}
    \wrongchoice{Une recherche dichotomique}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q18}
    Comment représenter naturellement une liste d'adjacence
en Python ?
    \begin{choices}
    \wrongchoice{Comme un entier}
    \wrongchoice{Comme un tuple unique}
    \wrongchoice{Comme une chaîne de caractères}
    \correctchoice{Comme un dictionnaire où la clé est un sommet et la valeur est la liste de ses voisins}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q19}
    Quelle fonction Python implémente correctement un parcours en largeur
depuis un sommet \texttt{depart} dans un graphe \texttt{g} (dictionnaire) ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def bfs(g, depart):
    return [v for v in g]
\end{lstlisting}
}
    \correctchoice{\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}
}
    \wrongchoice{\begin{lstlisting}
def bfs(g, depart):
    return g[depart]
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def bfs(g, depart):
    return sorted(g.keys())
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q20}
    Un \textbf{arbre} (au sens informatique) est un cas
particulier de :
    \begin{choices}
    \correctchoice{Graphe : c'est un graphe non orienté, connexe et acyclique}
    \wrongchoice{Tableau}
    \wrongchoice{File}
    \wrongchoice{Pile}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q21}
    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 ?
    \begin{choices}
    \correctchoice{Les poids doivent être positifs ou nuls (pas de poids négatifs)}
    \wrongchoice{Les poids doivent être entiers}
    \wrongchoice{Les poids doivent être triés à l'avance}
    \wrongchoice{Les poids doivent être tous identiques}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q22}
    Un \textbf{tri topologique} d'un DAG :
    \begin{choices}
    \correctchoice{Range les sommets dans un ordre tel que pour chaque arête $u \to v$, $u$ apparaît avant $v$}
    \wrongchoice{Trie les sommets par valeur croissante}
    \wrongchoice{Élimine les cycles}
    \wrongchoice{Trie les sommets par degré}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q23}
    Pour calculer les \textbf{composantes connexes} d'un graphe
non orienté, on peut :
    \begin{choices}
    \wrongchoice{Utiliser une recherche dichotomique}
    \correctchoice{Lancer un parcours en largeur (ou parcours en profondeur) depuis chaque sommet non encore visité ; chaque parcours visite une composante}
    \wrongchoice{Compter les sommets}
    \wrongchoice{Trier les sommets par numéro}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q24}
    Un \textbf{arbre couvrant} d'un graphe connexe est :
    \begin{choices}
    \wrongchoice{Un sous-graphe qui contient toutes les arêtes}
    \wrongchoice{Une racine du graphe}
    \wrongchoice{Un cycle qui passe par tous les sommets}
    \correctchoice{Un sous-graphe qui contient tous les sommets et forme un arbre (connexe, sans cycle)}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q25}
    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 ?
    \begin{choices}
    \wrongchoice{parcours en profondeur}
    \wrongchoice{parcours en largeur}
    \wrongchoice{Tri topologique}
    \correctchoice{L'algorithme de Dijkstra (les poids sont positifs)}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q26}
    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]} ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
[[0, 1, 0],
 [1, 0, 1],
 [0, 1, 0]]
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
[[0, 1, 1],
 [1, 0, 1],
 [1, 1, 0]]
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q27}
    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 ?
    \begin{choices}
    \wrongchoice{$S = n$ (nombre de sommets)}
    \wrongchoice{$S = m$}
    \wrongchoice{$S = m^2$}
    \correctchoice{$S = 2m$}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q28}
    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 ?
    \begin{choices}
    \correctchoice{A, B, C, D, E
}
    \wrongchoice{A, B, D, E, C
}
    \wrongchoice{A, C, B, D, E
}
    \wrongchoice{A, B, C, E, D
}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q29}
    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} ?
    \begin{choices}
    \wrongchoice{$14$ (en passant par \texttt{A-B-D-E})}
    \wrongchoice{$12$ (en passant directement par \texttt{C-E})}
    \wrongchoice{$11$}
    \correctchoice{$10$}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q30}
    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} ?
    \begin{choices}
    \correctchoice{\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}
}
    \wrongchoice{\begin{lstlisting}
def parcours_profondeur(g, depart):
    for voisin in g[depart]:
        parcours_profondeur(g, voisin)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def parcours_profondeur(g, depart):
    return list(g[depart])
\end{lstlisting}
}
    \wrongchoice{\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{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q31}
    Comment \textbf{détecter la présence d'un cycle}
dans un graphe \textbf{orienté} à l'aide d'un
parcours en profondeur ?
    \begin{choices}
    \correctchoice{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
}
    \wrongchoice{On compte simplement le nombre d'arêtes :
s'il dépasse $n - 1$, il y a un cycle
}
    \wrongchoice{Il est impossible de détecter un cycle en
temps polynomial
}
    \wrongchoice{On regarde si la matrice d'adjacence est
symétrique
}
    \end{choices}
  \end{question}
}

\element{terminalegraphes}{
  \begin{question}{q32}
    Quel est le principe de l'\textbf{algorithme de
Kahn} pour calculer un tri topologique d'un
DAG ?
    \begin{choices}
    \wrongchoice{On effectue un parcours en largeur depuis
le premier sommet
}
    \wrongchoice{On trie les sommets par ordre alphabétique
de leur identifiant
}
    \correctchoice{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
}
    \wrongchoice{On calcule la matrice d'adjacence puis on
cherche les valeurs propres
}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{terminalegraphes}
  \insertgroup{terminalegraphes}
}

\end{document}
