\documentclass[12pt] {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}{Exercices de bac sur l'algorithme de Dijkstra (1)}}\end{center}



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

\subsection{\textcolor{blue}{Pondichéry avril 2012 (extrait)}}
Les points de collecte d'un camion d'une société recyclant des \og déchets papier \fg, ainsi que les temps de trajet (en minutes) entre ces différents points, sont représentés par le graphe \no 1. 
Le dépôt est représenté par le sommet A et les autres sommets représentent les différents points de collecte. 

\psset{unit=0.8cm}
\begin{center}
\begin{pspicture}(10,8)
\cnodeput(0.5,4){A}{A} \cnodeput(3,7.5){B}{B}\cnodeput(3,4){C}{C} \cnodeput(5,0.5){D}{D}
\cnodeput(5,6){E}{E}\cnodeput(8,7.5){F}{F}\cnodeput(6,2.5){G}{G}\cnodeput(10,2.5){H}{H}
\ncline{A}{B}\ncput*{3}\ncline{A}{C}\ncput*{7}\ncline{A}{D}\ncput*{11}\ncline{B}{C}\ncput*{3}
\ncline{B}{D}\ncput*{7}\ncline{B}{E}\ncput*{11}\ncline{C}{D}\ncput*{4}\ncline{C}{E}\ncput*{3}
\ncline{D}{E}\ncput*{9}\ncline{D}{G}\ncput*{2}\ncline{E}{F}\ncput*{8}\ncline{E}{G}\ncput*{10}
\ncline{F}{G}\ncput*{4}\ncline{F}{H}\ncput*{7}\ncline{G}{H}\ncput*{12}
\rput(5,0){Graphe \no 1}
\end{pspicture}
\end{center}
 
\begin{enumerate}
\item Afin de rendre son plan plus lisible, le chauffeur du camion souhaite colorer les sommets du graphe représentant son réseau de manière à ce que deux sommets adjacents n'aient jamais la même couleur. Peut-il utiliser seulement trois couleurs ? Justifier. 
\item On appelle $M$ la matrice associée au graphe \no 1, $M$ étant construite en utilisant les sommets dans l'ordre alphabétique. On donne ci-dessous la matrice $M^4$ : 

\[M^4 = \begin{pmatrix}31 &34 &34 &38 &40 &13 &23 &9\\ 
34 &47& 46& 50 &44& 22& 33 &10\\ 
34& 46 &47& 50& 44& 22& 33 &10\\ 
38& 50& 50& 62& 54& 28& 34& 16\\ 
40& 44& 44& 54 &60& 24& 36& 20\\ 
13 &22 &22 &28& 24 &21 &23 &11\\ 
23 &33 &33 &34& 36 &23 &35 &13\\ 
9 &10 &10 &16 &20 &11 &13 &11\\
\end{pmatrix}\]
 
Combien y a-t-il de trajets possibles permettant d'aller du dépôt A au point de collecte H en quatre étapes? Justifier la réponse. 
\item Le conducteur doit se rendre du dépôt A au point de collecte H. Il cherche le chemin qui minimise le temps de trajet. Déterminer ce chemin en expliquant le procédé utilisé, et préciser le temps minimum de parcours obtenu. 
\end{enumerate}

\subsection{\textcolor{blue}{Polynésie juin 2012 (extrait)}}
Jonathan  est  un  sportif  adepte  du  semi-marathon  (course  à  pied  de  21,1  km).  Depuis  le  1\up{er} janvier  2012,  il  a  décidé  de  courir  un  semi-marathon  par  mois.  Afin  d'améliorer  sa préparation, il décide d'enchaîner les courses pédestres de 10 km dans différentes villes.  

\medskip

Le graphe pondéré ci-dessous représente les villes A, B, C, D, E, F, H organisant des courses de  10  km  et  la  ville  G  est  celle  organisant  le  prochain  semi-marathon  auquel  Jonathan  est inscrit. 

Le poids de chaque arête représente le temps, en minutes, nécessaire pour relier une ville à une autre grâce aux transports en commun. 

\begin{center}
\psset{unit=0.8cm}
\begin{pspicture}(0,0)(11,8.3)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\newcommand{\Pg}[1]{\small{\textsf{\prune{#1}}}}% poids des arêtes
\newcommand{\Sg}[1]{\small{\textsf{\bleu{#1}}}}% Sommet du graphe
\psset{dotstyle=*,dotscale=1.2,linecolor=bleu}
\dotnode(4,8){A} \dotnode(0,2.5){B} \dotnode(3.5,0){C} \dotnode(6,1.5){D} \dotnode(5.2,6){E} \dotnode(9,7.5){F} \dotnode(11,5.5){H} \dotnode(11,3){G} 
\uput[u](4,8){\Sg{A}} \uput[l](0,2.5){\Sg{B}} \uput[d](3.5,0){\Sg{C}} \uput[d](6,1.5){\Sg{D}} \uput[u](5.2,6){\Sg{E}} \uput[u](9,7.5){\Sg{F}} \uput[r](11,3){\Sg{G}} \uput[r](11,5.53){\Sg{H}}
\psset{linewidth=1pt,linecolor=bleu,shortput=nab}
\ncline{A}{B}_{\Pg{60}} \ncline{A}{C}^{\Pg{70}} \ncline{A}{E}^{\Pg{20}} \ncline{A}{F}^{\Pg{45}} \ncline{B}{C}_{\Pg{10}} \ncline{B}{E}_{\Pg{20}} \ncline{C}{D}_{\Pg{15}} 
\ncline{D}{E}_{\Pg{60}} \ncline{D}{G}_{\Pg{20}} \ncline{E}{F}^{\Pg{40}} \ncline{E}{H}_{\Pg{50}} \ncline{F}{H}^{\Pg{35}} \ncline{G}{H}_{\Pg{20}} 
\end{pspicture}
\end{center}

Jonathan vient de courir dans la ville A et souhaite se rendre dans la ville G pour repérer le parcours  de  son  prochain  semi-marathon.  Déterminer  à  l'aide  d'un  algorithme  le  chemin permettant de relier le plus rapidement la ville A à la ville G et donner la durée de ce parcours en minutes. 

\end{multicols}

\label{fin}
\end{document}  