\documentclass[10pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[frenchb]{babel}
\usepackage{fourier}
\usepackage{fouriernc}
\usepackage[scaled=0.875]{helvet}
\renewcommand{\ttdefault}{lmtt}
\usepackage{amsmath,amssymb,makeidx}
\usepackage{pst-plot,pst-text}
\usepackage[normalem]{ulem}
\usepackage{fancybox}
\usepackage{ulem}
\usepackage{dcolumn}
\usepackage{textcomp}
\usepackage{slashbox}
\usepackage{mathrsfs}
\usepackage{esvect}
\usepackage{tabularx}
\usepackage{lscape}
\newcommand{\euro}{\eurologo{}}
\usepackage{color}
\usepackage{pstricks,pst-all,pstricks-add,pst-tree,pst-3dplot}
\usepackage[colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\setlength{\columnseprule}{0.5pt}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}

%%%%%%%%%%%% Algorithmes %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{xcolor}
\colorlet{LFBcoultable1}{blue!25!black!20}
\usepackage[french,ruled,lined,linesnumbered,inoutnumbered]{algorithm2e}

\SetKwInput{Lire}{Lire}
\SetKwInput{Afficher}{Afficher}

\SetKwFor{VarAlgo}{Variables}{}{finVariables}
\newcommand{\Variables}[1]{\SetAlgoVlined%
                           \VarAlgo{}{#1}
                           \SetAlgoLined}

\SetKwFor{EntrAlgo}{Entrées}{}{fin}
\newcommand{\Entrees}[1]{\SetAlgoVlined%
                           \EntrAlgo{}{#1}
                           \SetAlgoLined}

\SetKwFor{TraitAlgo}{Traitement}{}{fin}
\newcommand{\Traitement}[1]{\SetAlgoVlined%
                           \TraitAlgo{}{#1}
                           \SetAlgoLined}

\SetKwFor{SortAlgo}{Sorties}{}{fin}
\newcommand{\Sorties}[1]{\SetAlgoVlined%
                           \SortAlgo{}{#1}
                           \SetAlgoLined}
\makeatletter
\newsavebox{\LFB@lgo}
\newenvironment{algoLFB}[2][0.5]% % 2 parametres : 1-facultatif largeur en proportion 2-titre de l'algo
               {\setlength{\fboxsep}{0pt}\begin{lrbox}{\LFB@lgo}
               \small\begin{minipage}{#1\linewidth}%
                \begin{algorithm}[H]%
                \caption{#2}}%
               {\end{algorithm}%
                \end{minipage}%
                \end{lrbox}%
                \begin{center}
                \fcolorbox{black}{LFBcoultable1}{\usebox{\LFB@lgo}}
%                \fcolorbox{LFBcoultable2}{LFBcoultable1}{\usebox{\LFB@lgo}}
                \end{center}}
\makeatother
\newcommand{\recoit}{\ensuremath{\rightarrow}}

\newcommand{\vect}[1]{\mathchoice%
{\overrightarrow{\displaystyle\mathstrut#1\,\,}}%
{\overrightarrow{\textstyle\mathstrut#1\,\,}}%
{\overrightarrow{\scriptstyle\mathstrut#1\,\,}}%
{\overrightarrow{\scriptscriptstyle\mathstrut#1\,\,}}}
\renewcommand{\theenumi}{\textbf{\arabic{enumi}}}
\renewcommand{\labelenumi}{\textbf{\theenumi.}}
\renewcommand{\theenumii}{\textbf{\alph{enumii}}}
\renewcommand{\labelenumii}{\textbf{\theenumii.}}
\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%
\def\Oij{$\left(\text{O},~\vect{\imath},~\vect{\jmath}\right)$}
\def\Oijk{$\left(\text{O},~\vect{\imath},~ \vect{\jmath},~ \vect{k}\right)$}
\def\Ouv{$\left(\text{O},~\vect{u},~\vect{v}\right)$}
\usepackage{fancyhdr} 
\usepackage[np]{numprint}
\textheight 26.5 cm  
\topmargin -4cm 
\headheight 12pt
\parindent 0pt
\textwidth 170mm
\oddsidemargin -5 mm
\evensidemargin -25 mm
\usepackage{multicol}


\newcommand{\ds}[3]{
	\begin{center}
		\begin{LARGE}
			\textbf{\textsc{Devoir Surveillé de Mathématiques n°#1}}\\
		\end{LARGE}
		    \vspace*{0.3cm}
		 	\textit{#2}\hfill\textit{#3}
	\end{center}
	\hrule}
	
\newcounter{numeroexo}
\newcommand{\exercice}{\par\noindent\stepcounter{numeroexo}
	\underline{{\textbf{Exercice \arabic{numeroexo} :}}}\quad}

\begin{document}
	\ds{2}{le 13 décembre 2013 - 1h30}{Spé TES}
\hrule 
\vspace*{0.5cm}

\exercice \emph{(7 points)}

\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

\exercice \emph{(3 points)}

\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

\bigskip 
\newpage
\exercice \emph{(5 points)} 

\medskip
 
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}

\bigskip

\exercice \emph{(5 points)} 

\medskip

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é !})

\bigskip

\end{document}