\documentclass[a4paper,11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[frenchb]{babel}
\usepackage{amsmath,amssymb}
\usepackage{mathptmx}
\DeclareSymbolFont{lmodern}{U}{euex}{m}{n}
\DeclareMathSymbol\infty \mathord{lmodern}{"31}
\usepackage[scaled=0.875]{helvet} % ss
\usepackage{textcomp}
\usepackage{dsfont}
\usepackage[left=2cm,right=2cm,top=2cm,bottom=2cm]{geometry}
\usepackage{fancyhdr} 
\fancyhf{}
\setlength{\headheight}{26pt}
\setlength{\footskip}{18pt}
\renewcommand {\headrulewidth}{0pt}
\renewcommand {\footrulewidth}{0pt}
\usepackage{lastpage}
%\usepackage{makeidx}
\usepackage{hyperxmp}
\usepackage[colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\pagestyle{fancy}
\usepackage {array}
\usepackage{tabularx}
\usepackage{eqnarray}
\usepackage{multirow}
\usepackage{colortbl}
\usepackage[table]{xcolor}
\usepackage{mathtools} %pour l'alignement des termes d'une matrice
\usepackage{fltpoint}
\usepackage{pstricks,pst-all,pstricks-add,pst-tree,pst-3dplot}
\usepackage{ifthen}
\usepackage{calc}
\usepackage{esvect}
% Mise en forme des algorithmes
\usepackage[french,boxed,titlenumbered,lined,longend]{algorithm2e}
  \SetKwIF {Si}{SinonSi}{Sinon}{si}{alors}{sinon\_si}{alors}{fin~si}
 \SetKwFor{Tq}{tant\_que~}{~faire~}{fin~tant\_que}
 \SetKwFor{PourCh}{pour\_chaque }{ faire }{fin pour\_chaque}
 \SetKwInput{Sortie}{Sortie}
\newcommand{\Algocmd}[1]{\textsf{\textsc{\textbf{#1}}}}\SetKwSty{Algocmd}
  \newcommand{\AlgCommentaire}[1]{\textsl{\small  #1}}  
%
\usepackage[np]{numprint}
 \setlength{\parindent}{0mm}
\usepackage [alwaysadjust]{paralist}
\setdefaultenum {1.}{a)}{}{}
\hyphenpenalty 10000 % empèche la coupure de mots
\renewcommand*{\tabularxcolumn}[1]{m{#1}} %centrage vertical des cellules d'un tableau tabularx
\newcommand{\Oij}{$\left( {{\mathrm{O}};\vec i,\vec j} \right)$}
\newcommand{\Oijk}{$\left( {{\mathrm{O}};\vec i,\vec j ,\vec k} \right)$}
\newcommand{\euro}{\texteuro{}}
\newcommand{\R}{\mathds {R}}
\newcommand{\N}{\mathds {N}}
\newcommand{\Z}{\mathds {Z}}
\newcommand{\Q}{\mathds {Q}}
\newcommand{\e}{\mathrm {e}}
\newcommand{\dd}{\mathrm {d}}
\newcommand{\fvalid}{\raisebox{1ex}{\rotatebox{180}{$\Rsh$}}} % flèche entrée pour prg casio
\DecimalMathComma


\newcommand{\QCM}[3]{ $\bullet$ \quad #1 \hfill 
$\bullet$ \quad #2 \hfill 
$\bullet$ \quad #3 }

\newcommand{\QCMc}[4]{   #1 \\ 
\makebox[3cm][l]{\psframe(.25,.25) \qquad #2 }\hfill 
\makebox[3cm][l]{\psframe(.25,.25) \qquad #3 }\hfill 
\makebox[3cm][l]{\psframe(.25,.25) \qquad #4 }} % QCM avec cases à cocher%

% en-tête
\lhead{\footnotesize{\textsf{Lycée JANSON DE SAILLY\\ 25 janvier 2016}}} %gauche
\chead{\textsf{\textcolor{red}{\textbf{\textsc{contrôle spécialité \no 3}}}}} %centre
\rhead{\footnotesize{\textsf{T\textsuperscript{le} ES 3\\Durée 45 minutes}}}%droit
%pied de page                                              
%\rfoot{\scriptsize{\textsf{Page~\thepage{}~sur~\pageref{LastPage}}}}
\lfoot{ \htmladdnormallink{\scriptsize{\textsf{\textsc{A. Yallouz (MATH@ES)}}}}{http://yallouz.arie.free.fr}}


\newcounter{nexo}           % déclaration du numéro d'exo
\setcounter{nexo}{0}        % initialisation du numero

\newcommand{\exo}{
  \stepcounter{nexo} 
  \par{\textsf{\textbf{\textcolor{blue}{{\small{EXERCICE \; \arabic{nexo}}}}}}}}
  
  

\hypersetup{
pdftitle={Contrôle \no 3.}, 
pdfauthor={Arié Yallouz},   
pdfsubject={Graphes}, 
pdfkeywords={Chaîne eulérienne, algorithme de Dijkstra.},
pdfcontacturl={http//yallouz.arie.free.fr/},
pdflang={fr},
baseurl={http://yallouz.arie.free.fr/terminale_controles/controles_terminale_2015-2016.php}
}
\begin{document}
\begin{center}
\emph{La calculatrice n'est pas autorisée}
\end{center}

On considère le graphe  ci-dessous :

\begin{center}
\psset{xunit=2.7cm,yunit=1.8cm}
\begin{pspicture}(4,2)
\newrgbcolor{bleu}{0.1 0.05 .5}
\psset{linecolor=bleu,linewidth=1pt}
\begin{footnotesize}
\cnodeput(1,0){A}{\bleu {A}} \cnodeput(0,1){B}{\bleu {B}} \cnodeput(1,2){C}{\bleu {C}} \cnodeput(2,2){D}{\bleu {D}} \cnodeput(2,0){E} {\bleu {E}}\cnodeput(3,0){F}{\bleu {F}} \cnodeput(4,1){G}{\bleu {G}} \cnodeput(3,2){H}{\bleu {H}}
\end{footnotesize}
\ncline{A}{C} \ncline{C}{D} \ncline{D}{A} \ncline{A}{B} \ncline{B}{C} \ncline{C}{E} \ncline{E}{D} \ncline{D}{F} \ncline{F}{G} \ncline{G}{H} \ncline{H}{F} \ncline{F}{E}\ncline{E}{H}
\end{pspicture}
\end{center}
\begin{enumerate}
\item On appelle $M$ la matrice d'adjacence de ce graphe, les sommets étant pris dans l'ordre alphabétique. 

Une des trois matrices $R$, $S$ ou $T$ est la matrice $M^4$.

\begin{center}
{\small{$R = \begin{pmatrix} 4 & 5 & 7 & 8 & 4 & 3 & 1 & 3 \\ 5 & 2 & 6 & 3 & 3 & 3 & 0 & 1 \\ 7 & 6 & 6 & 9 & 9 & 4 & 3 & 3 \\ 8 & 3 & 9 & 6 & 9 & 9 & 3 & 4 \\ 4 & 3 & 9 & 9 & 6 & 9 & 3 & 8 \\ 3 & 3 & 4 & 9 & 9 & 6 & 6 & 7 \\ 1 & 0 & 3 & 3 & 3 & 6 & 2 & 5 \\ 3 & 1 & 3 & 4 & 8 & 7 & 5 & 4\\\end{pmatrix}$ ; $S = \begin{pmatrix} 20 & 11 & 21 & 18 & 21 & 16 & 6 & 8 \\ 11 & 11 & 13 & 17 & 13 & 7 & 4 & 6 \\ 21 & 13 & 31 & 26 & 22 & 24 & 7 & 16 \\ 18 & 17 & 26 & 35 & 28 & 22 & 13 & 21 \\ 21 & 13 & 22 & 28 & 35 & 26 & 17 & 18 \\ 16 & 7 & 24 & 22 & 26 & 31 & 13 & 21 \\ 6 & 4 & 7 & 13 & 17 & 13 & 11 & 11 \\ 8 & 6 & 16 & 21 & 18 & 21 & 11 & 20\\\end{pmatrix}$ ; $T = \begin{pmatrix} 7 & 6 & 9 & 9 & 6 & 4 & 11 & 3 \\ 3 & 4 & 7 & 5 & 4 & 3 & 9 & 1 \\ 11 & 7 & 10 & 11 & 10 & 6 & 3 & 4 \\ 4 & 5 & 11 & 10 & 11 & 10 & 4 & 6 \\ 6 & 4 & 10 & 11 & 10 & 11 & 5 & 9 \\ 9 & 3 & 6 & 10 & 11 & 10 & 7 & 9 \\ 9 & 0 & 3 & 4 & 5 & 7 & 4 & 6 \\ 6 & 10 & 4 & 6 & 9 & 9 & 6 & 7\\\end{pmatrix}$}}
\end{center}

\begin{enumerate}
\item Sans calculer la matrice $M^4$, indiquer quelle est la matrice $M^4$ en justifiant votre choix.
\item En déduire le nombre de chaînes de longueur 4 entre B et H.
\end{enumerate}
\item \begin{enumerate}
\item Déterminer en justifiant si le graphe est complet.
\item Déterminer en justifiant si le graphe est connexe.
\end{enumerate}
\item Ce graphe modélise une partie du plan d'une commune. Les arêtes du graphe représentent les rues et les sommets du graphe sont les points de vente de quotidiens.

Est-il possible de planifier un parcours permettant le nettoyage de toutes ces rues sans emprunter plusieurs fois la même rue ? Justifier la réponse. Si oui proposer un parcours.
\item Le  graphe pondéré ci-dessous, donne en minutes, les temps de parcours moyens des différentes rues en tenant compte des sens uniques.
\begin{center}
\psset{xunit=2.7cm,yunit=1.8cm}
\begin{pspicture}(4,2)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{linewidth=1pt,linecolor=bleu, arrowscale=1.5}
\begin{footnotesize}
\cnodeput(1,0){A}{\bleu {A}} \cnodeput(0,1){B}{\bleu {B}} \cnodeput(1,2){C}{\bleu {C}} \cnodeput(2,2){D}{\bleu {D}} \cnodeput(2,0){E} {\bleu {E}}\cnodeput(3,0){F}{\bleu {F}} \cnodeput(4,1){G}{\bleu {G}} \cnodeput(3,2){H}{\bleu {H}}
\ncline{->}{A}{B}\ncput*{\textsf{\prune 5}} \ncline{->}{A}{C}\ncput*{\textsf{\prune 11}} \ncline{->}{B}{C}\ncput*{\textsf{\prune 7}} \ncline{->}{C}{D}\ncput*{\textsf{\prune 6}}\ncline{->}{C}{E}\ncput*[npos=.25]{\textsf{\prune 16}} \ncline{->}{D}{A}\ncput*[npos=.75]{\textsf{\prune 7}} \ncline{->}{E}{D}\ncput*{\textsf{\prune 10}} \ncline{->}{D}{F}\ncput*[npos=.25]{\textsf{\prune 5}} \ncline{->}{G}{F}\ncput*{\textsf{\prune 6}} \ncline{->}{H}{G} \ncput*{\textsf{\prune 8}}\ncline{->}{F}{H}\ncput*{\textsf{\prune 15}} \ncline{->}{F}{E}\ncput*{\textsf{\prune 4}}\ncline{->}{E}{H}\ncput*[npos=.25]{\textsf{\prune 7}}
\end{footnotesize}
\end{pspicture}
\end{center}
\begin{enumerate}
\item Après avoir effectué une livraison au point de vente A, le livreur doit récupérer les quotidiens invendus au point de vente G.

En utilisant un algorithme, déterminer le trajet le plus rapide pour  aller de A à G.
\item Est-il possible en partant de A d'effectuer une tournée qui dure moins de 45 minutes en passant par tous les points de vente de quotidiens ?
\end{enumerate}
\end{enumerate}

\end{document}

