\documentclass[11pt] {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{red}{\Roman{subsubsection}}.\textcolor{blue}{\arabic{subsubsection}}} 
\pagestyle{empty}
% pour le pied de page central
\cfoot{Page \thepage/\pageref{fin}}

\begin{document}

\begin{center}\section*{\textcolor{red}{Corrigé de la feuille d'exercices (exosbac(2))}}\end{center}

\subsection{\textcolor{blue}{Pondichéry avril 2011}}
On utilise l'algorithme de Dijkstra :

\begin{center}
\begin{tabularx}{\linewidth}{|c|*{7}{>{\centering \arraybackslash \small}X|}m{2cm}|}\hline
A	&B&C&D&E&F&G&H&Sommet sélectionné\\ \hline
0	&$\infty$&$\infty$&$\infty$&$\infty$&$\infty$&$\infty$	&$\infty$	&A 0\\ \hline
	&300 A	&500 A&$\infty$c&$\infty$&$\infty$	&$\infty$	&$\infty$	&B 300\\ \hline
	&		&500 A	&700 B	&$\infty$&$\infty$	&$\infty$	&$\infty$	&C 500\\ \hline
	&		&		&600 C	&700 C	&$\infty$	&$\infty$	&$\infty$	&D 600\\ \hline
	&		&		&		&700 C	&300 D		&$\infty$	&1300 D		&E 700\\ \hline
	&		&		&		&		&1300 D		&900 E		&1000 E		&G 900\\ \hline
	&		&		&		&		&1300 D		&			&1000 E		&H 1000\\ \hline
	&		&		&		&		&1200 H		&			&			&F 1200\\ \hline
\end{tabularx}
\end{center}

En partant de F on remonte ses prédécesseurs : F - H - E - C - A.

le trajet le plus court A - C- E - H - F a une longueur de \numprint{1200}~km.


\subsection{\textcolor{blue}{Pondichéry avril 2013}}
\textbf{Partie A}


\begin{enumerate}
\item La chaîne A-B-E-G-F-C-D passe par tous les sommets du graphe $\Gamma$, donc le graphe $\Gamma$ est connexe.

Degré des sommets :

\begin{tabular}{|*8{l|}} \hline
Sommets&A&B&C&D&E&F&G\\
\hline
Degrés&2&4&4&5&4&4&3\\
\hline
\end{tabular}

Le graphe $\Gamma$ est connexe et contient 2 sommets de degré impair, D et G, donc d'après le théorème d’Euler , il admet une chaîne eulérienne dont les extrémités sont D et G.\\
Par exemple : D - B - A - C - B - E - D - C - F - D - G - E - F - G

\item Le graphe $\Gamma$ contient 2 sommets de degré impair ; il n’admet pas de cycle eulérien.

\item Soit M la matrice associée au graphe $\Gamma$ :\\
$M=\begin{pmatrix}
0&1&1&0&0&0&0\\
1&0& 1& 1& 1& 0& 0\\
1&1&0&1&0&1&0\\
0&1& 1& 0& 1& 1& 1&\\
0&1& 0& 1& 0& 1& 1&\\
0& 0& 1& 1& 1& 0& 1\\
0&0&0&1&1&1&0 
\end{pmatrix}$
\end{enumerate}

\textbf{Partie B}

\begin{enumerate}
\item Pour déterminer le plus court chemin reliant la gare B à la gare G, on utilise l’algorithme de Dijkstra.

\begin{tabular}{|*{8}{c|}}\hline
B&A&C&D&E&F&G&\begin{minipage}{2cm}
Sommet sélectionné
\end{minipage}\\
\hline
0B&4B&7B&18B&21B&$\infty$&$\infty$&B\\
\hline
X&4B&7B car $12A>7B$&18B&21B&$\infty$&$\infty$&A\\
\hline
X&X&7B&17C&21B&32C&$\infty$&C\\
\hline
X&X&X&X&21B car $32D>21B$&29D&48D&D\\
\hline
X&X&X&X&21B&29D car $31E>29D$&38E car $48D>38E$&E\\
\hline
X&X&X&X&X&29D&36F car $38E>36F$&F\\
\hline
X&X&X&X&X&X&36F&G\\
\hline
\end{tabular}

Le sommet G étant marqué, pour lire la chaîne de poids minimal, on part de G et on \og{}remonte\fg{} la chaîne en suivant les prédécesseurs :
$G \leftarrow F\leftarrow D \leftarrow C \leftarrow B$.

Le chemin le plus court possible reliant la gare B à la gare G est B - C - D - F - G. 


\item La longueur en minutes de ce chemin est de 36 minutes.

\end{enumerate}


\label{fin}
\end{document}  