\documentclass[a4paper,11pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais,bloc,completemulti]{automultiplechoice}
\usepackage[french]{babel}
\usepackage{amsmath, amssymb}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,calc,patterns}

\title{Graphes, matrices et chaînes de Markov}
\date{Mathématiques}

\begin{document}

\noindent\textbf{Graphes, matrices et chaînes de Markov} \hfill \textit{Mathématiques}\\[0.4em]
Nom~: \dotfill\ Prénom~: \dotfill

\bigskip

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q01}
    Dans un graphe non orienté, qu'appelle-t-on degré d'un
sommet ?
    \begin{choices}
    \correctchoice{Le nombre d'arêtes dont ce sommet est une extrémité}
    \wrongchoice{Le nombre total de sommets du graphe}
    \wrongchoice{Le nombre total d'arêtes du graphe}
    \wrongchoice{La longueur de la plus longue chaîne partant du sommet}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q02}
    Combien d'arêtes possède le graphe complet à $5$ sommets
(chaque paire de sommets est reliée) ?
    \begin{choices}
    \correctchoice{$10$}
    \wrongchoice{$20$}
    \wrongchoice{$5$}
    \wrongchoice{$25$}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q03}
    Que signifie « le graphe est connexe » ?
    \begin{choices}
    \correctchoice{Deux sommets quelconques sont toujours reliés par au
moins une chaîne}
    \wrongchoice{Chaque paire de sommets est reliée par une arête directe}
    \wrongchoice{Le graphe ne contient aucun cycle}
    \wrongchoice{Tous les sommets ont le même degré}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q04}
    Soit $A = \begin{pmatrix} 1 & 0 & 2 \\ 3 & -1 & 4
\end{pmatrix}$. Quelles sont les dimensions de $A$ ?
    \begin{choices}
    \correctchoice{$2 \times 3$ : deux lignes, trois colonnes}
    \wrongchoice{$3 \times 2$}
    \wrongchoice{$6$}
    \wrongchoice{$2 \times 2$}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q05}
    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$ ?
    \begin{choices}
    \correctchoice{$AB = \begin{pmatrix} 5 & 2 \\ 1 & 1 \end{pmatrix}$}
    \wrongchoice{$AB = \begin{pmatrix} 3 & 0 \\ 0 & 1 \end{pmatrix}$}
    \wrongchoice{$AB = \begin{pmatrix} 4 & 2 \\ 1 & 2 \end{pmatrix}$}
    \wrongchoice{$AB = \begin{pmatrix} 3 & 2 \\ 1 & 1 \end{pmatrix}$}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q06}
    Soit $A = \begin{pmatrix} 2 & 1 \\ 5 & 3 \end{pmatrix}$.
Quelle est la matrice inverse $A^{-1}$ ?
    \begin{choices}
    \correctchoice{$A^{-1} = \begin{pmatrix} 3 & -1 \\ -5 & 2 \end{pmatrix}$}
    \wrongchoice{$A^{-1} = \begin{pmatrix} \frac{1}{2} & 1 \\ \frac{1}{5}
& \frac{1}{3} \end{pmatrix}$}
    \wrongchoice{$A^{-1} = \begin{pmatrix} 3 & 1 \\ 5 & 2 \end{pmatrix}$}
    \wrongchoice{$A$ n'est pas inversible}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q07}
    Qu'est-ce que la matrice d'adjacence d'un graphe à $n$
sommets ?
    \begin{choices}
    \correctchoice{La matrice carrée $n \times n$ dont le coefficient
$(i\ ;\ j)$ compte les arêtes reliant le sommet $i$ au
sommet $j$}
    \wrongchoice{La matrice colonne des degrés des sommets}
    \wrongchoice{Une matrice $2 \times n$ listant les arêtes}
    \wrongchoice{La matrice identité $I_n$}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q08}
    Soit $A$ la matrice d'adjacence d'un graphe. Que représente
le coefficient $(1\ ;\ 3)$ de la matrice $A^4$ ?
    \begin{choices}
    \correctchoice{Le nombre de chemins de longueur $4$ allant du sommet
$1$ au sommet $3$}
    \wrongchoice{La distance entre les sommets $1$ et $3$}
    \wrongchoice{Le nombre d'arêtes entre les sommets $1$ et $3$}
    \wrongchoice{$4$ fois le coefficient $(1\ ;\ 3)$ de $A$}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q09}
    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$ ?
    \begin{choices}
    \correctchoice{$U_n = A^n\,U_0$}
    \wrongchoice{$U_n = n\,A\,U_0$}
    \wrongchoice{$U_n = A\,U_0^n$}
    \wrongchoice{$U_n = A^{n-1}\,U_1$ donc rien de plus simple}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q10}
    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) ?
    \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{choices}
    \correctchoice{$P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}3 & 0{,}7
\end{pmatrix}$}
    \wrongchoice{$P = \begin{pmatrix} 0{,}8 & 0{,}3 \\ 0{,}2 & 0{,}7
\end{pmatrix}$}
    \wrongchoice{$P = \begin{pmatrix} 0{,}2 & 0{,}8 \\ 0{,}7 & 0{,}3
\end{pmatrix}$}
    \wrongchoice{$P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}7 & 0{,}3
\end{pmatrix}$}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q11}
    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$ ?
    \begin{choices}
    \correctchoice{La distribution de probabilité de l'état du système
après $n$ transitions}
    \wrongchoice{La probabilité de rester dans l'état initial}
    \wrongchoice{La matrice des chemins de longueur $n$ du graphe}
    \wrongchoice{Toujours la distribution uniforme}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q12}
    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$) ?
    \begin{choices}
    \correctchoice{$\pi = (0{,}6\ ;\ 0{,}4)$}
    \wrongchoice{$\pi = (0{,}5\ ;\ 0{,}5)$}
    \wrongchoice{$\pi = (0{,}8\ ;\ 0{,}2)$}
    \wrongchoice{Il n'en existe pas}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q13}
    Dans un graphe non orienté, que vaut la somme des degrés de
tous les sommets ?
    \begin{choices}
    \correctchoice{Le double du nombre d'arêtes}
    \wrongchoice{Le nombre d'arêtes}
    \wrongchoice{Le nombre de sommets}
    \wrongchoice{Cela dépend du graphe, sans formule générale}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q14}
    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$ ?
    \begin{choices}
    \correctchoice{$A$ : l'identité est neutre pour le produit}
    \wrongchoice{$I_2$}
    \wrongchoice{La matrice nulle}
    \wrongchoice{$2A$}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q15}
    Pour deux matrices carrées $A$ et $B$, a-t-on toujours
$AB = BA$ ?
    \begin{choices}
    \correctchoice{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}$}
    \wrongchoice{Oui : la multiplication est toujours commutative}
    \wrongchoice{Oui, dès que les deux matrices sont carrées de même
taille}
    \wrongchoice{Non, sauf si les matrices sont différentes}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q16}
    $A$ est de taille $2 \times 3$ et $B$ de taille $3 \times
1$. Que dire du produit $AB$ ?
    \begin{choices}
    \correctchoice{Il existe et mesure $2 \times 1$ (une colonne de hauteur
$2$)}
    \wrongchoice{Il n'existe pas : les tailles sont différentes}
    \wrongchoice{Il existe et mesure $3 \times 3$}
    \wrongchoice{Il existe et mesure $2 \times 3$}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q17}
    Soit $A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$.
Que vaut $A^2$ ?
    \begin{choices}
    \correctchoice{$A^2 = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}$}
    \wrongchoice{$A^2 = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$}
    \wrongchoice{$A^2 = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^2 =
\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ coefficient
par coefficient}
    \wrongchoice{$A^2 = \begin{pmatrix} 2 & 2 \\ 0 & 2 \end{pmatrix}$}
    \end{choices}
  \end{question}
}

\element{mathsexpertesgraphesmatrices}{
  \begin{question}{q18}
    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 ?
    \begin{choices}
    \correctchoice{Non : la première ligne somme à $1{,}1 \neq 1$}
    \wrongchoice{Oui : tous les coefficients sont entre $0$ et $1$}
    \wrongchoice{Non : les colonnes ne somment pas à $1$}
    \wrongchoice{Oui : il suffit de la diviser par $1{,}1$}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{mathsexpertesgraphesmatrices}
  \insertgroup{mathsexpertesgraphesmatrices}
}

\end{document}
