\documentclass[10pt] {article} \usepackage[T1]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,graphicx,multicol,mathrsfs, fancyhdr,enumerate,fourier,eurosym,alterqcm,enumerate,tabularx,variations,numprint,systeme}
\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é) : correction du 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 ?
Trouvons le degré de chaque sommet :

\begin{tabular}{|*{6}{c|}}\hline
Sommet&P&Q&R&S&T\\
\hline
Degré&3&2&3&4&2\\
\hline
\end{tabular}

\item %Ce graphe contient-il une chaîne eulérienne ? Justifier.
Ce graphe connexe n'a que deux sommets de degré impair (P et R). Il existe donc une chaîne eulérienne partant de P et finissant de R.

\item %Contient-il un cycle eulérien ? Justifier.
Pour qu'il y ait un cycle eulérien, il faut que tous les sommets soient de degré pair ; ce n'est pas le cas, donc le graphe n'a pas de cycle eulérien.

\end{enumerate}
\end{multicols}

\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}$.
Soient les matrices $A=\begin{pmatrix}1&1\\-2&-1\end{pmatrix}$ et $\begin{pmatrix}2&-3&5\\-1&1&-1\end{pmatrix}$.\\
$A\times B=\begin{pmatrix}1&1\\-2&-1\end{pmatrix}\times \begin{pmatrix}2&-3&5\\-1&1&-1\end{pmatrix}\\=\begin{pmatrix}1\times 2+1\times (-1)&1\times (-3)+1\times 1&1\times 5+1\times (-1)\\-2\times 2+(-1)\times (-1)&-2\times (-3)+(-1)\times 1&-2\times 5+(-1)\times (-1)\end{pmatrix}$\\
Donc : \[\boxed{\textcolor{red}{A\times B=\begin{pmatrix}1&-2&4\\-3&5&-9\end{pmatrix}}}.\]


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

\subsection{}

\medskip

On considère la matrice  $A=\left(\begin{array}{cc} -3&0\\1&2 \end{array} \right)$
\begin{enumerate}
\item %Montrer que la matrice $A$ est inversible.
La matrice $A$ est inversible car $-3\times (-2)-1\times 5=6-5=1\neq 0$.

\item %Déterminer, sans calculatrice, l'inverse de la matrice $A$.\\
On note $A^{-1}=\begin{pmatrix}a&b\\c&d\end{pmatrix}$.\\
On doit avoir $A\times A^{-1}=\begin{pmatrix}1&0\\0&1\end{pmatrix}$ d'où \\
$\begin{pmatrix}-3a+5c&a-2c=0\\ -3b+5d=0&b-2d=1\end{pmatrix}=\begin{pmatrix}1&0\\0&1\end{pmatrix}$.\\

\bigskip

On en déduit :\\
$\systeme{-3a+5c=1,a-2c=0,-3a+5d=0,b-2d=1}$.\\
On résout : $\systeme{-3a+5c=1,a-2c=0}$.\\
La deuxième équation donne $a=2c$ ; on remplace dans la première équation. On trouve $-6c+5c=1\Leftrightarrow -c=1\Leftrightarrow \boxed{\textcolor{red}{c=-1}}$.\\
On en déduit $a=2c=-2$.\\

\bigskip

On résout ensuite : $\systeme{-3b+5d=0,b-2d=1}$.\\
La première équation donne $b=\dfrac{5}{3}d$.\\
On remplace dans la deuxième équation : $\dfrac{5}{3}d-2d=1\Leftrightarrow -\dfrac{d}{3}=1\Leftrightarrow d=-3$.\\
D'où $b=\dfrac{5}{3}d=\dfrac{5}{3}\times (-3)=-5$.\\
On en déduit $\boxed{\textcolor{red}{A^{-1}=\begin{pmatrix}-2&-5\\-1&-3\end{pmatrix}}}$
\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.
La matrice $A$ est inversible car $3\times 2-4\times 1=2\neq 0$.

\item On pose $X=\begin{pmatrix}x\\y\end{pmatrix}$ et $B=\begin{pmatrix}10\\8\end{pmatrix}$.\\
%Écrire sous forme matricielle ce système.
Le système s'écrit $\boxed{\textcolor{red}{AX=B}}$

\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.
$AX=B\Leftrightarrow A^{-1}\times AX=A^{-1}B$ donc $X=A^{-1}B=\begin{pmatrix}1&-2\\-\dfrac{1}{2}&\dfrac{3}{2}\end{pmatrix}\times \begin{pmatrix}10\\8\end{pmatrix}=\begin{pmatrix}10-16\\-5+12\end{pmatrix}=\begin{pmatrix}-6\\7\end{pmatrix}$.\\
Le couple solution du système est $\boxed{\textcolor{red}{(-6~;~7)}}$
\end{enumerate}

\end{multicols}

 
\subsection{}%Liban mai 2014
\begin{minipage}{0.38\textwidth} 
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.
\end{minipage}
\begin{minipage}{0.6\textwidth}
\begin{flushright}
\psset{unit=0.8cm}
\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{flushright}
\end{minipage}


\medskip

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. 
Dans le graphe donné dans le texte, deux sommets quelconques peuvent être reliés entre eux par au moins un chemin donc ce graphe est 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. 
Le graphe donné dans le texte est connexe et non orienté car les sommets sont reliés par des arêtes et pas par des arcs. 

Pour que l'agent puisse passer par toutes les salles en utilisant une fois et une seule chaque passage, il faut que le graphe contienne une chaîne eulérienne; pour cela, il faut que le graphe admette 0 ou 2 sommets de degrés impairs.

On cherche les degrés des sommets du graphe:

\begin{center}
 \begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline 
Sommet & A & B & C & D & E & F & H \\ 
\hline 
Degrés & 4 & 2 & 4 & 3 & 4 & 3 & 2 \\ 
\hline 
\end{tabular}
 \end{center} 

Il n'y a que deux sommets de degrés impairs -- D et F -- donc ce graphe admet des chaînes eulériennes qui partent de D pour arriver à F, ou qui partent de F pour arriver à D.

Le gardien peut donc passer par toutes les salles en utilisant une fois et une seule chacun des 11 passages; exemple de trajet: D - C - B - A - C - E - A - F - E - D - H - F

\item On range les 7 sommets par ordre alphabétique: A - B - C - D - E - F - H

La matrice d'adjacence $M$ associée au graphe est une matrice carrée d'ordre 7, ne contenant que des 0 et des 1. Si une arête relie le sommet numéro $i$ ($1 \leqslant i \leqslant 7$) au sommet numéro $j$ ($1 \leqslant j \leqslant 7$), on mettra un 1 à la ligne $i$ et la colonne $j$ de la matrice; sinon on mettra un 0.\\ 

La matrice d'adjacence est donc: \hfill
$M=\begin{pmatrix}
0	&	1	&	1	&	0	&	1	&	1	&	0	\\	
1	&	0	&	1	&	0	&	0	&	0	&	0	\\
1	&	1	&	0	&	1	&	1	&	0	&	0	\\
0	&	0	&	1	&	0	&	1	&	0	&	1	\\
1	&	0	&	1	&	1	&	0	&	1	&	0	\\
1	&	0	&	0	&	0	&	1	&	0	&	1	\\
0	&	0	&	0	&	1	&	0	&	1	&	0	\\
\end{pmatrix}$ \hfill\,

\item \ \\[-10pt]

On donne:\hfill 
$M^4 = \begin{pmatrix}
31	&15 &26 &21 &27 &18 &12\\ 
15 	&12 &15 &12 &18 &12 &\boxed{\textcolor{red}{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}$\hfill\,

La matrice $M^4$ donne le nombre de chemins de longueur 4 entre tous les sommets. Le sommet B est le numéro 2, le sommet H le numéro 7; le nombre de chemins de longueur 4 allant de B à H est le nombre situé dans la matrice à la ligne 2 et la colonne 7. 

Il y a donc 6 chemins de longueur 4 allant de B vers H.


\end{enumerate}

%Barème :
%I : 1,5+1+1=3,5
%II : 2,5
%III : 1+2=3
%IV : 1+1,5+2,5=5
%V : 1+2+1+2=6

\label{fin}
\end{document}  