\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{bclogo}
\usepackage{pst-plot,pst-tree,pstricks,pst-node,pstricks-add,pst-math,pst-xkey,pst-eucl}
\usepackage[francais]{babel} 
\everymath{\displaystyle}
\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}

\begin{center}\section*{\textcolor{red}{Exercices de bac}}\end{center}



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

\subsection{\textcolor{blue}{Pondichéry avril 2011}}
Un orchestre doit effectuer une tournée passant par les villes A, B, C, D, E, F, G et H, en utilisant le réseau autoroutier.\\
 Des contraintes de calendrier imposent en fait d'organiser un concert dans la ville F immédiatement après un concert dans la ville A.
 
Le graphe $\Gamma$ est complété ci-dessous par les longueurs en kilomètres de chaque tronçon (les longueurs des segments ne sont pas proportionnelles aux distances). 

\begin{center}
\psset{xunit=1.5cm,yunit=1.5cm}
\begin{pspicture}(5,7)
\uput[ul](0.5,6.5){A} \uput[r](2.3,5.5){B} \uput[l](1,4.8){C} \uput[ur](2.5,3.4){D} 
\uput[l](0.5,3.3){E} \uput[r](4.8,3){F} \uput[dl](2,0.6){G} \uput[d](3.6,0.2){H}
\pspolygon(0.5,6.5)(2.3,5.5)(2.5,3.4)(4.8,3)(3.6,0.2)(2,0.6)(0.5,3.3)(3.6,0.2)(2.5,3.4)(1,4.8)
\psline(2.3,5.5)(1,4.8)(0.5,3.3) 
\psdots(0.5,6.5)(2.3,5.5)(2.5,3.4)(4.8,3)(3.6,0.2)(2,0.6)(0.5,3.3)(1,4.8)
%\psgrid
\rput(1.5,6.2){300} \rput(0.5,5.6){500} \rput(1.6,4.9){400} \rput(2.7,4.5){400} 
\rput(1.5,4){100} \rput(0.5,4.1){200} \rput(3.6,3.4){700} \rput(4.5,1.6){200} 
\rput(3.3,2){700} \rput(2.7,0.2){200} \rput(2.1,2.1){300} \rput(1.,1.8){200} 
\end{pspicture}
\end{center}

\medskip
 
Déterminer, en utilisant un algorithme dont on citera le nom, le trajet autoroutier le plus court (en kilomètres) pour aller de A à F.
 
Préciser la longueur en kilomètres de ce trajet. 


\columnbreak

\subsection{\textcolor{blue}{Pondichéry avril 2013}}


\emph{Les parties A et B peuvent être traitées indépendamment}

\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}
 
\textbf{PARTIE A}

\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.
\end{enumerate}

\bigskip
 
\textbf{PARTIE B}

\medskip

Une région est munie d'un réseau de trains, représenté par le graphe $\Gamma$ ci-dessous.
 
Les stations sont symbolisées par les sommets A, B, C, D, E, F et G. Chaque arête représente une ligne reliant deux gares. Les temps de parcours (correspondance comprise) en minutes entre chaque sommet ont été rajoutés sur le graphe.

\begin{center}
\psset{unit=1cm}
\begin{pspicture}(6.5,4)
%\psgrid
\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)
\rput(0.6,2.7){4} \rput(1.4,1.8){7} \rput(1,0.6){8} \rput(2.2,2.9){18} \rput(2.4,1.3){10} \rput(3,3.7){21} 
\rput(3.7,3.1){15} \rput(4.2,2.5){31} \rput(4,1.4){12} \rput(3.5,0.2){25} \rput(4.9,1.8){10} \rput(5.35,3.1){17} 
\rput(5.6,1.2){7}   
\end{pspicture}
\end{center}
 
\begin{enumerate}
\item Déterminer le plus court chemin en minutes, reliant la gare B à la gare G. 

Justifier la réponse grâce à un algorithme. 
\item Quelle est la longueur en minutes de ce chemin ? 
\end{enumerate}

 




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