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

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

\usepackage{tikz}
\usetikzlibrary{arrows.meta,calc,patterns}

\setbeamertemplate{frametitle continuation}{}

\subject{Mathématiques}
\title{Graphes, matrices et chaînes de Markov}
\subtitle{QCM}
\author{Maths expertes}
\date{\today}

\begin{document}

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

% Q1 - Réponse en A
\begin{frame}[fragile]{Question 1 \textemdash{} Degré d'un sommet}
    Dans un graphe non orienté, qu'appelle-t-on degré d'un
sommet ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Le nombre d'arêtes dont ce sommet est une extrémité}
        \item[B.] Le nombre total de sommets du graphe
        \item[C.] Le nombre total d'arêtes du graphe
        \item[D.] La longueur de la plus longue chaîne partant du sommet
    \end{itemize}
\end{frame}

% Q2 - Réponse en A
\begin{frame}[fragile]{Question 2 \textemdash{} Graphe complet}
    Combien d'arêtes possède le graphe complet à $5$ sommets
(chaque paire de sommets est reliée) ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$10$}
        \item[B.] $20$
        \item[C.] $5$
        \item[D.] $25$
    \end{itemize}
\end{frame}

% Q3 - Réponse en A
\begin{frame}[fragile]{Question 3 \textemdash{} Graphe connexe}
    Que signifie « le graphe est connexe » ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Deux sommets quelconques sont toujours reliés par au
moins une chaîne}
        \item[B.] Chaque paire de sommets est reliée par une arête directe
        \item[C.] Le graphe ne contient aucun cycle
        \item[D.] Tous les sommets ont le même degré
    \end{itemize}
\end{frame}

% Q4 - Réponse en A
\begin{frame}[fragile]{Question 4 \textemdash{} Dimensions d'une matrice}
    Soit $A = \begin{pmatrix} 1 & 0 & 2 \\ 3 & -1 & 4
\end{pmatrix}$. Quelles sont les dimensions de $A$ ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$2 \times 3$ : deux lignes, trois colonnes}
        \item[B.] $3 \times 2$
        \item[C.] $6$
        \item[D.] $2 \times 2$
    \end{itemize}
\end{frame}

% Q5 - Réponse en A
\begin{frame}[fragile]{Question 5 \textemdash{} Produit de matrices}
    Soient $A = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}$ et
$B = \begin{pmatrix} 3 & 0 \\ 1 & 1 \end{pmatrix}$. Que vaut
le produit $AB$ ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$AB = \begin{pmatrix} 5 & 2 \\ 1 & 1 \end{pmatrix}$}
        \item[B.] $AB = \begin{pmatrix} 3 & 0 \\ 0 & 1 \end{pmatrix}$
        \item[C.] $AB = \begin{pmatrix} 4 & 2 \\ 1 & 2 \end{pmatrix}$
        \item[D.] $AB = \begin{pmatrix} 3 & 2 \\ 1 & 1 \end{pmatrix}$
    \end{itemize}
\end{frame}

% Q6 - Réponse en A
\begin{frame}[fragile]{Question 6 \textemdash{} Inverse d'une matrice $2 \times 2$}
    Soit $A = \begin{pmatrix} 2 & 1 \\ 5 & 3 \end{pmatrix}$.
Quelle est la matrice inverse $A^{-1}$ ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$A^{-1} = \begin{pmatrix} 3 & -1 \\ -5 & 2 \end{pmatrix}$}
        \item[B.] $A^{-1} = \begin{pmatrix} \frac{1}{2} & 1 \\ \frac{1}{5}
& \frac{1}{3} \end{pmatrix}$
        \item[C.] $A^{-1} = \begin{pmatrix} 3 & 1 \\ 5 & 2 \end{pmatrix}$
        \item[D.] $A$ n'est pas inversible
    \end{itemize}
\end{frame}

% Q7 - Réponse en A
\begin{frame}[fragile]{Question 7 \textemdash{} Matrice d'adjacence}
    Qu'est-ce que la matrice d'adjacence d'un graphe à $n$
sommets ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{La matrice carrée $n \times n$ dont le coefficient
$(i\ ;\ j)$ compte les arêtes reliant le sommet $i$ au
sommet $j$}
        \item[B.] La matrice colonne des degrés des sommets
        \item[C.] Une matrice $2 \times n$ listant les arêtes
        \item[D.] La matrice identité $I_n$
    \end{itemize}
\end{frame}

% Q8 - Réponse en A
\begin{frame}[fragile]{Question 8 \textemdash{} Compter les chemins avec $A^k$}
    Soit $A$ la matrice d'adjacence d'un graphe. Que représente
le coefficient $(1\ ;\ 3)$ de la matrice $A^4$ ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Le nombre de chemins de longueur $4$ allant du sommet
$1$ au sommet $3$}
        \item[B.] La distance entre les sommets $1$ et $3$
        \item[C.] Le nombre d'arêtes entre les sommets $1$ et $3$
        \item[D.] $4$ fois le coefficient $(1\ ;\ 3)$ de $A$
    \end{itemize}
\end{frame}

% Q9 - Réponse en A
\begin{frame}[fragile]{Question 9 \textemdash{} Suite $U_{n+1} = AU_n$}
    Une suite de matrices colonnes vérifie $U_{n+1} = A\,U_n$
pour tout $n$. Comment s'exprime $U_n$ en fonction de
$U_0$ ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$U_n = A^n\,U_0$}
        \item[B.] $U_n = n\,A\,U_0$
        \item[C.] $U_n = A\,U_0^n$
        \item[D.] $U_n = A^{n-1}\,U_1$ donc rien de plus simple
    \end{itemize}
\end{frame}

% Q10 - Réponse en A
\begin{frame}[fragile]{Question 10 \textemdash{} Matrice de transition}
    Le graphe ci-contre décrit une chaîne de Markov à deux états
$A$ et $B$. Quelle est sa matrice de transition $P$ (états
dans l'ordre $A$, $B$, lignes = état de départ) ?\medskip
    \begin{center}
\begin{tikzpicture}
  \node[draw, circle, minimum size=9mm] (A) at (0,0) {$A$};
  \node[draw, circle, minimum size=9mm] (B) at (3.6,0) {$B$};
  \draw[->] (A) to[bend left=25] node[above, font=\small] {$0{,}2$} (B);
  \draw[->] (B) to[bend left=25] node[below, font=\small] {$0{,}3$} (A);
  \draw[->] (A) .. controls (-1.5,1.1) and (-1.5,-1.1) .. (A);
  \node[font=\small] at (-1.55,0) {$0{,}8$};
  \draw[->] (B) .. controls (5.1,1.1) and (5.1,-1.1) .. (B);
  \node[font=\small] at (5.15,0) {$0{,}7$};
\end{tikzpicture}
    \end{center}
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}3 & 0{,}7
\end{pmatrix}$}
        \item[B.] $P = \begin{pmatrix} 0{,}8 & 0{,}3 \\ 0{,}2 & 0{,}7
\end{pmatrix}$
        \item[C.] $P = \begin{pmatrix} 0{,}2 & 0{,}8 \\ 0{,}7 & 0{,}3
\end{pmatrix}$
        \item[D.] $P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}7 & 0{,}3
\end{pmatrix}$
    \end{itemize}
\end{frame}

% Q11 - Réponse en A
\begin{frame}[fragile]{Question 11 \textemdash{} Distribution après $n$ transitions}
    Une chaîne de Markov a pour matrice de transition $P$ et
pour distribution initiale la matrice ligne $\pi_0$. Que
représente la matrice ligne $\pi_0 P^n$ ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{La distribution de probabilité de l'état du système
après $n$ transitions}
        \item[B.] La probabilité de rester dans l'état initial
        \item[C.] La matrice des chemins de longueur $n$ du graphe
        \item[D.] Toujours la distribution uniforme
    \end{itemize}
\end{frame}

% Q12 - Réponse en A
\begin{frame}[fragile]{Question 12 \textemdash{} Distribution invariante}
    Pour la chaîne de matrice $P = \begin{pmatrix} 0{,}8 & 0{,}2
\\ 0{,}3 & 0{,}7 \end{pmatrix}$, quelle est la distribution
invariante $\pi = (x\ ;\ y)$ (vérifiant $\pi P = \pi$ et
$x + y = 1$) ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$\pi = (0{,}6\ ;\ 0{,}4)$}
        \item[B.] $\pi = (0{,}5\ ;\ 0{,}5)$
        \item[C.] $\pi = (0{,}8\ ;\ 0{,}2)$
        \item[D.] Il n'en existe pas
    \end{itemize}
\end{frame}

% Q13 - Réponse en A
\begin{frame}[fragile]{Question 13 \textemdash{} Le lemme des poignées de main}
    Dans un graphe non orienté, que vaut la somme des degrés de
tous les sommets ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Le double du nombre d'arêtes}
        \item[B.] Le nombre d'arêtes
        \item[C.] Le nombre de sommets
        \item[D.] Cela dépend du graphe, sans formule générale
    \end{itemize}
\end{frame}

% Q14 - Réponse en A
\begin{frame}[fragile]{Question 14 \textemdash{} La matrice identité}
    Que vaut le produit $A\,I_2$, où $I_2 = \begin{pmatrix} 1 &
0 \\ 0 & 1 \end{pmatrix}$ et $A$ est une matrice $2 \times
2$ ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$A$ : l'identité est neutre pour le produit}
        \item[B.] $I_2$
        \item[C.] La matrice nulle
        \item[D.] $2A$
    \end{itemize}
\end{frame}

% Q15 - Réponse en A
\begin{frame}[fragile]{Question 15 \textemdash{} $AB$ contre $BA$}
    Pour deux matrices carrées $A$ et $B$, a-t-on toujours
$AB = BA$ ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Non : par exemple $\begin{pmatrix} 0 & 1 \\ 0 & 0
\end{pmatrix}\begin{pmatrix} 0 & 0 \\ 1 & 0
\end{pmatrix} \neq \begin{pmatrix} 0 & 0 \\ 1 & 0
\end{pmatrix}\begin{pmatrix} 0 & 1 \\ 0 & 0
\end{pmatrix}$}
        \item[B.] Oui : la multiplication est toujours commutative
        \item[C.] Oui, dès que les deux matrices sont carrées de même
taille
        \item[D.] Non, sauf si les matrices sont différentes
    \end{itemize}
\end{frame}

% Q16 - Réponse en A
\begin{frame}[fragile]{Question 16 \textemdash{} Dimensions compatibles}
    $A$ est de taille $2 \times 3$ et $B$ de taille $3 \times
1$. Que dire du produit $AB$ ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Il existe et mesure $2 \times 1$ (une colonne de hauteur
$2$)}
        \item[B.] Il n'existe pas : les tailles sont différentes
        \item[C.] Il existe et mesure $3 \times 3$
        \item[D.] Il existe et mesure $2 \times 3$
    \end{itemize}
\end{frame}

% Q17 - Réponse en A
\begin{frame}[fragile]{Question 17 \textemdash{} Calculer $A^2$}
    Soit $A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$.
Que vaut $A^2$ ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$A^2 = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}$}
        \item[B.] $A^2 = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$
        \item[C.] $A^2 = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^2 =
\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ coefficient
par coefficient
        \item[D.] $A^2 = \begin{pmatrix} 2 & 2 \\ 0 & 2 \end{pmatrix}$
    \end{itemize}
\end{frame}

% Q18 - Réponse en A
\begin{frame}[fragile]{Question 18 \textemdash{} Une matrice de transition valide ?}
    La matrice $\begin{pmatrix} 0{,}5 & 0{,}6 \\ 0{,}3 & 0{,}7
\end{pmatrix}$ peut-elle être la matrice de transition
d'une chaîne de Markov ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Non : la première ligne somme à $1{,}1 \neq 1$}
        \item[B.] Oui : tous les coefficients sont entre $0$ et $1$
        \item[C.] Non : les colonnes ne somment pas à $1$
        \item[D.] Oui : il suffit de la diviser par $1{,}1$
    \end{itemize}
\end{frame}

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

\end{document}
