\documentclass[11pt] {article} \usepackage[T1]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,graphicx,multicol,mathrsfs, fancyhdr,enumerate,fourier,eurosym,alterqcm,enumerate,tabularx,variations,numprint}
\usepackage[dvips]{color}
\usepackage[tikz]{bclogo}
\usepackage{pst-plot,pst-tree,pstricks,pst-node,pstricks-add,pst-math,pst-xkey,pst-eucl}
\usepackage[francais]{babel} 
\everymath{\displaystyle}
%\usepackage[colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\textwidth 19cm \textheight 26cm \hoffset 
-1,4cm \voffset -3.7cm \oddsidemargin 0pt 
\renewcommand{\thesubsection}{\textcolor{blue}{\Roman{subsection}}} 
\renewcommand{\thesubsubsection}{\textcolor{blue}{\Roman{subsection}}.\textcolor{blue}{\arabic{subsubsection}}} 
\pagestyle{empty}
% pour le pied de page central
\cfoot{Page \thepage/\pageref{fin}}

\begin{document}
%\tableofcontents

\begin{center}\section*{\textcolor{red}{TES (spécialité) : contrôle sur les graphes et matrices}}\end{center}



\begin{multicols}{2}
\setlength{\columnseprule}{1pt}
\setlength{\columnsep}{2 cm}

\subsection{}
On considère le graphe PQRST ci-dessous :
\begin{center}
\begin{pspicture}(-1,-2.5)(5,2.5)
\psdots(0,0)(2,-1)(4,-1.5)(5,0)(1.5,1.5)
\uput[l](0,0){P}
\uput[l](2,-1){R}
\uput[d](4,-1.5){T}
\uput[r](5,0){S}
\uput[u](1.5,1.5){Q}
\psline(2,-1)
\psline(1.5,1.5)
\psline(5,0)
\psline(1.5,1.5)(5,0)
\psline(5,0)(2,-1)
\psline(5,0)(4,-1.5)
\psline(2,-1)(4,-1.5)
\end{pspicture}
\end{center}
\begin{enumerate}

\item Quel est le degré de chaque sommet ?

\item Ce graphe contient-il une chaîne eulérienne ? Justifier.

\item Contient-il un cycle eulérien ? Justifier.
\end{enumerate}

%\subsection{}
%Représenter un graphe associé à la matrice $M$ suivante :
%\begin{center}
%$M=\begin{pmatrix}
%0&1&1&0\\1&0&1&0\\1&1&0&1\\0&0&1&0
%\end{pmatrix}$
%
%\end{center}
%
%
%\subsection{}
%
%Soit $M$ la matrice : \[M=\left(\begin{array}{cccc} 1&-5&4&6\\1&3&-4&-1\\2&9&-1&2\end{array} \right)\]
%\begin{enumerate}
%	\item Donner la taille de cette matrice.
%	\item Donner la valeur des \'el\'ements $a_{11}$, $a_{23}$, $a_{33}$ et $a_{34}$ de cette matrice.
%\end{enumerate}
%
%\bigskip



\subsection{}

\medskip 

Calculer, sans calculatrice, le produit $A\times B$ des matrices $A=\begin{pmatrix}1&1\\-2&-1\end{pmatrix}$ et $\begin{pmatrix}2&-3&5\\-1&1&-1\end{pmatrix}$.

\subsection{}

\medskip

On considère la matrice  $A=\left(\begin{array}{cc} -3&5\\1&-2 \end{array} \right)$
\begin{enumerate}
\item Montrer que la matrice $A$ est inversible.
\item Déterminer, sans calculatrice, l'inverse de la matrice $A$.
\end{enumerate}


\subsection{}

\medskip

Soit le système $\left\{\begin{array}{l} 3x+4y=10 \\ x+2y=8\end{array}\right.$ 

\medskip

On considère la matrice $A=\left(\begin{array}{cc} 3&4\\1&2\end{array} \right)$

\medskip

\begin{enumerate}
\item Justifier que la matrice $A$ est inversible.

\item On pose $X=\begin{pmatrix}x\\y\end{pmatrix}$ et $B=\begin{pmatrix}10\\8\end{pmatrix}$.\\
Écrire sous forme de calcul matriciel ce système.

\item On admet que la matrice inverse $A^{-1}$ vaut $A^{-1}=\begin{pmatrix}1&-2\\-\dfrac{1}{2}&\dfrac{3}{2}\end{pmatrix}$.\\

 Résoudre alors  \textbf{à l'aide de la calculatrice} ce système.
\end{enumerate}
%
%
%\subsection{}
%
%\medskip
%
%Soit le système $\left\{\begin{array}{l} 2x+y-z=1 \\ x+2y-z=2 \\ x-y+2z=3 \end{array}\right.$ \\
%
%\begin{enumerate}
%\item Écrire sous forme matriciel ce système.
%%\item Vérifier que la matrice inverse de $A$ est : %\[A^{-1}=\left(\begin{array}{ccc} 0,5&-\frac{1}{6}&\frac{1}{6}\\-0,5&\frac{5}%{6}&\frac{1}{6}\\-0,5&0,5&0,5\end{array} \right)\]
%\item Résoudre \textbf{à l'aide de la calculatrice} ce système.
%\end{enumerate}
%
%\bigskip
%
%
%
%\subsection{}
%
%\medskip
%
%On considère la matrice $A=\left(\begin{array}{ccc}
%	1 & 1 & 0 \\
%	1 & 1 & 1 \\
%	0 & -1 & 1
%	\end{array}\right)$ 
%\begin{enumerate}
%\item Calculer, \textbf{à l'aide de la calculatrice}, les matrices $A^{2}$ et $A^{3}$.
%\item Calculer $A^3-3A^2+3A-I_{3}$ o\`u $I_{3}$ est la matrice identité d'ordre 3.
%\item En déduire $A^3-3A^2+3A$.
%\item En déduire, à l'aide d'une factorisation, que $A$ est inversible et donner une expression de $A^{-1}$.
% \end{enumerate}
% 


%\subsection{}
%
%\medskip 
%
%Le graphe ci-dessous représente les autoroutes entre les principales villes du Sud de la France :
% 
%Bordeaux (B), Clermont-Ferrand (C), Lyon (L), Marseille (M), Montpellier (P), Brive (R), Toulouse (T), Valence (V) et Biarritz (Z).
%
%\begin{center} 
%\begin{pspicture}(10,4)
%%\psgrid
%\cnodeput(0.5,0.5){A}{Z}\cnodeput(1,3){B}{B}\cnodeput(3.2,0){C}{T}
%\cnodeput(3,3.5){D}{R}\cnodeput(5.5,3.3){E}{C}\cnodeput(7,0.25){F}{P}
%\cnodeput(9,3.8){G}{L}\cnodeput(9.1,2.5){H}{V}\cnodeput(9.5,0.8){I}{M}
%\ncline{A}{B}\ncline{A}{C}\ncline{C}{B}\ncline{B}{D}\ncline{D}{C}
%\ncline{D}{E}\ncline{E}{F}\ncline{E}{G}\ncline{G}{H}
%\ncline{H}{F}\ncline{F}{I}\ncline{C}{F}\ncline{H}{I}
%\end{pspicture}
%\end{center}
%
%Pour cette question, on justifiera chaque réponse. 
%
%\begin{enumerate}
%\item 
%	\begin{enumerate}
%		\item Déterminer l'ordre du graphe. 
%		\item Déterminer si le graphe est connexe. 
%		\item Déterminer si le graphe est complet.
%	\end{enumerate} 
%\item Un touriste atterrit à l'aéroport de Lyon et loue une voiture.
% 
%Déterminer, en justifiant, s'il pourra visiter toutes les villes en empruntant une et une seule fois chaque autoroute. 
%\item Il décide finalement d'aller seulement de Lyon à Biarritz. 
%
%On note $N$ la matrice associée au graphe, les sommets étant rangés dans l'ordre alphabétique : B, C, L, M, P, R, T, V, Z. 
%
%Voici les matrices $N$ et $N^3$ : 
%
%
%\[N = \begin{pmatrix}
%0 &0 &0 &0 &0 &1 &1 &0 &1\\ 
%0 &0 &1 &0 &1 &1 &0 &0 &0 \\
%0 &1 &0 &0 &0 &0 &0 &1 &0\\ 
%0 &0 &0 &0 &1 &0 &0 &1 &0\\ 
%0 &1 &0 &1 &0 &0 &1 &1 &0\\
%1 &1 &0 &0 &0 &0 &1 &0 &0\\
%1 &0 &0 &0 &1 &1 &0 &0 &1 \\
%0 &0 &1 &1 &1 &0 &0 &0 &0\\ 
%1 &0 &0 &0 &0 &0 &1 &0 &0\\
%\end{pmatrix}
% \:\: \quad \text{et}\:\: \quad N^3 = \begin{pmatrix}
%4 &2 &1 &1 &3 &6 &6 &1 &5\\ 
%2 &0 &5 &2 &8 &6 &1 &1 &3\\ 
%1 &5 &0 &2 &1 &0 &3 &5 &0\\ 
%1 &2 &2 &2 &5 &2 &1 &4 &1\\ 
%3 &8 &1 &5 &2 &1 &8 &7 &1\\ 
%6 &6 &0 &2 &1 &2 &8 &3 &2\\ 
%6 &1 &3 &1 &8 &8 &4 &1 &6\\ 
%1 &1 &5 &4 &7 &3 &1 &2 &1\\ 
%5 &3 &0 &1 &1 &2 &6 &1 &2\\
%\end{pmatrix}\]
% 
%	\begin{enumerate}
%		\item En détaillant le calcul, déterminer le coefficient de la troisième ligne et dernière colonne de la matrice $N^4$. 
%		\item En donner une interprétation. 
%	\end{enumerate}
%\end{enumerate}
%
%\bigskip
%
%
%
%\subsection{}
%
%\medskip 
%
%La matrice $M$ ci-dessous est la matrice d'adjacence d'un graphe $G$ :
%\[\left( \begin{array}{cccc}
%0 & 1 & 0 & 2 \\ 
%1 & 0 & 1 & 1 \\ 
%0 & 1 & 1 & 1 \\ 
%2 & 0 & 1 & 0  
%\end{array} \right)\]
%
%\begin{minipage}{0.45\linewidth}
%Compléter le graphe $G$ ci-contre. (\textit{Les sommets seront pris dans l'ordre}.)
%\end{minipage} \hfill
%\begin{minipage}{0.6\linewidth}
%\begin{center}
%\psset{unit=1cm}
%\begin{pspicture}(6.5,4)
%\psdots[dotscale=2](2,3.5)(2,0.1)(5,3.5)(5,0.1)
%\uput[u](2,3.5){1} \uput[d](2,0.1){2} \uput[u](5,3.5){3} \uput[d](5,0.1){4} 
%\end{pspicture}
%\end{center}
%\end{minipage} \hfill
%
%\subsection{}
%
% 
%On considère le graphe $\Gamma$ ci-dessous : 
%
%\begin{center}
%\psset{unit=1cm}
%\begin{pspicture}(6.5,4)
%\psdots[dotscale=2](0,1.5)(1.3,3.5)(2,0.1)(3,2.2)(4.5,3.5)(5,0.1)(6,2.5)
%\uput[u](0,1.5){A} \uput[u](1.3,3.5){B} \uput[d](2,0.1){C} \uput[u](3,2.2){D} \uput[u](4.5,3.5){E} \uput[d](5,0.1){F} \uput[r](6,2.5){G}
%\psline(0,1.5)(1.3,3.5)(4.5,3.5)(6,2.5)(3,2.2)(4.5,3.5)(5,0.1)(2,0.1)(3,2.2)(2,0.1)(1.3,3.5)(0,1.5)
%\psline(6,2.5)(5,0.1)(3,2.2)(1.3,3.5)
%\psline(0,1.5)(2,0.1) 
%\end{pspicture}
%\end{center}
% 
%\medskip
% 
%\begin{enumerate}
%\item Ce graphe admet-il une chaîne eulérienne ? Justifier la réponse. Si oui donner une telle chaîne. 
%\item Ce graphe admet-il un cycle eulérien ? Justifier la réponse. Si oui donner un tel cycle. 
%\item Donner la matrice $M$ associée au graphe $\Gamma$. Les sommets seront pris dans l'ordre alphabétique : 
%A, B, C, D, E, F, G.
%\item Combien y a t-il de chemins de longueurs 9 partant de E ? 
%\end{enumerate}
%
%
%
%\subsection{}
%
%Le directeur d'un petit zoo veut réorganiser l'habitat de telle sorte que les animaux cohabitent dans des enclos plus vastes.
%
%Malheureusement, il n'est pas possible de laisser tous les animaux ensemble dans un seul enclos, car certains sont les prédateurs des autres !
%\\
%Le tableau ci-dessous indique, parmi dix animaux que possède le zoo, lesquels sont les prédateurs ou les proies des autres.
%
%\begin{center}
%{\renewcommand{\arraystretch}{}
%\begin{tabularx}{0.5\linewidth}{|*{11}{>{\centering \arraybackslash}X|}}\hline
%    &$a$&$b$&$c$&$d$&$e$&$f$&$g$&$h$&$i$&$j$ \\ \hline
% $a$&	&$\spadesuit$&   &   &$\spadesuit$&   &   &   &   &$\spadesuit$\\ \hline
% $b$&$\spadesuit$	&   &   &$\spadesuit$   &   &   &$\spadesuit$   &   &   &    \\ \hline
% $c$&	&   &   &   &   &   &   & $\spadesuit$  &   &$\spadesuit$    \\ \hline
% $d$&	&$\spadesuit$   &   &   &   &$\spadesuit$   &   &   &   &    \\ \hline
% $e$&$\spadesuit$	&   &   &   &   &   &   &   &$\spadesuit$   &    \\ \hline
% $f$&	&   &   &$\spadesuit$   &   &   &   &   &   &$\spadesuit$    \\ \hline
% $g$&	&$\spadesuit$   &   &   &   &   &   &   &   &    \\ \hline
% $h$&	&   & $\spadesuit$  &   &   &   &   &   & $\spadesuit$  &    \\ \hline
% $i$&	&   &   &   & $\spadesuit$  &   &   & $\spadesuit$  &   &$\spadesuit$    \\ \hline
% $j$&$\spadesuit$	&   & $\spadesuit$  &   &   & $\spadesuit$  &   &   & $\spadesuit$  &    \\ \hline
%\end{tabularx}}
%\end{center} 
%
%\medskip
%
%Combien d'enclos le directeur du zoo doit-il prévoir ? 
%(\textit{Justifier votre réponse avec une rédaction de qualité !})

%\subsection{}%\textcolor{blue}{Réunion juin 2004}extrait
%On note G le graphe représenté ci-dessous et $M$ sa matrice obtenue en prenant les
% sommets dans l'ordre alphabétique. La matrice $M^3$ est également donnée.
% 
% \vspace{1cm}
% 
%\begin{center}
%\begin{pspicture}(9,7)
%\cnodeput(0,2){B}{b} 
% \cnodeput(1.8,6.5){C}{c} \cnodeput(5.9,6.5){G}{g} 
% \cnodeput(6.7,3.3){F}{f} 
% \cnodeput(5.5,2){E}{e} \cnodeput(9,2){H}{h} \cnodeput(6.7,0){D}{d} 
% \cnodeput(2.5,0){A}{a}
% \ncarc{B}{C} \ncarc{B}{A} \ncarc{A}{C} \ncarc{A}{G} 
% \ncarc{A}{E} \ncarc{E}{C} \ncarc{G}{E} \ncarc{H}{G} 
% \ncarc{H}{F} \ncarc{H}{D} \ncarc{E}{D} \ncarc{A}{D}
% \ncarc{C}{G} \ncarc{F}{E}
%\end{pspicture} 
% 
% \vspace{0,8cm}
%
% $M^3 = \begin{pmatrix}
%10 &8 &11& 10& 12& 5& 13& 4\\
%8   & 2&  7& 3& 5& 2 & 4 & 3\\
%11 & 7& 8& 6& 12&  3& 10&  5\\
%10 &  3& 6& 2& 11&  1& 4 & 8\\
%12 & 5& 12& 11& 8 & 8& 13& 3\\
%5   & 2& 3& 1&	8 &0 &2 &6\\
%13 & 4& 10& 4& 13&  2&  6&  9\\
%4   &  3& 5& 8& 3& 6& 9&  0\\
%\end{pmatrix}$
%\end{center}
%
%\noindent Dire, en justifiant votre réponse, si les affirmations suivantes sont vraies ou
% fausses : 
%
%\begin{enumerate}\item L'ordre du graphe est égal au plus grand des degrés des sommets. 
%
%\item Le graphe G contient un sous-graphe complet d'ordre 3. 
%
%\item Les sommets de G peuvent être coloriés avec trois couleurs sans que deux
% sommets adjacents soient de même couleur. 
%
%\item Il est possible de parcourir ce graphe en passant une fois et une seule par 
%chaque arête. 
%
%\item Il existe au moins un chemin de longueur 3 qui relie chaque sommet \`a chacun
% des sept autres sommets du graphe. 
%
%\item Il y a 72 chemins de longueur 3 qui relient le sommet e \`a chacun des huit
% sommets du graphe.
% 
% \end{enumerate}
 
\subsection{}%Liban mai 2014
On a schématisé ci-dessous le plan d'une MJC (Maison de la Jeunesse et de la Culture) par un graphe dont les sommets sont les salles et les arêtes sont les passages (portes, couloirs ou escaliers) entre les salles. 
On appelle H le hall d'entrée et B le bureau du directeur.

\begin{center}
\psset{unit=1cm}
\begin{pspicture}(-0.5,-2.5)(8.5,2.5)
\psdots(0,0)(2,2)(6,2)(8,0)(6,-2)(4,0)(2,-2)%HFABECD 
\pspolygon(0,0)(2,2)(6,2)(8,0)(6,-2)(2,-2)%HFABCDH
\psline(2,2)(6,-2)(6,2)(2,-2)
\uput[ul](2,2){F} \uput[ur](6,2){A} \uput[l](0,0){H} 
\uput[r](8,0){B} \uput[dr](6,-2){C} \uput[u](4,0){E} 
\uput[dl](2,-2){D} 
\end{pspicture}
\end{center}

En fin de journée, un agent de service fait le tour de la MJC pour récupérer dans chaque salle (bureau du directeur et hall inclus) les objets oubliés par les enfants.

\medskip
 
\begin{enumerate}
\item Préciser si ce graphe est connexe en justifiant la réponse.\index{graphe connexe} 
\item Déterminer, en justifiant, si l'agent de service peut passer par toutes les salles en utilisant une fois et une seule chaque passage. 
\item On range les sommets par ordre alphabétique. 

Donner la matrice d'adjacence $M$ associée au graphe. 
\item On donne : 
\[M^4 = \begin{pmatrix}
31	&15 &26 &21 &27 &18 &12\\ 
15 	&12 &15 &12 &18 &12 &6\\ 
26	&15 &31 &18 &27 &21 &12\\ 
21 	&12 &18 &20 &17 &18 &5\\ 
27	&18	&27 &17 &34 &17 &16\\ 
18 	&12 &21 &18 &17 &20 &5\\ 
12 	&6 	&12 &5 	&16 &5 &10\\
\end{pmatrix}\] 

On admet que le coefficient $a_{ij}$ de la matrice $M^4$ donne le nombre de chemins de longueur 4 entre le sommet correspondant à i et celui correspondant à j.\\
En déduire le nombre de chemins de longueur 4 entre les sommets B et H.

\end{enumerate}


\end{multicols}
\label{fin}
\end{document}  