\documentclass[10pt,a4paper]{article} 
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc} 

\usepackage{fourier}
\usepackage[scaled=0.875]{helvet}
\renewcommand{\ttdefault}{lmtt} 
\usepackage{amsmath,amssymb,makeidx} 
\usepackage{fancybox}
\usepackage{tabularx}
\usepackage{graphicx}  
\usepackage[normalem]{ulem} 
\usepackage{pifont}
\usepackage{array} 
\usepackage{textcomp} 
\newcommand{\euro}{\eurologo{}}
% Tapuscrit : Noël Debarle
% Corrigé : Noël Debarle et François Hache
\usepackage{ulem}
\usepackage{tabularx}
\usepackage{dcolumn}
\usepackage{textcomp}
\usepackage[dvips]{color}
\usepackage{pstricks,pst-plot,pst-text,pst-tree,pstricks-add}
\usepackage{colortbl}
\usepackage[body={15cm,24cm}]{geometry}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\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.}}
\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)$}

%\setlength{\voffset}{-1,5cm}

\usepackage{fancyhdr} 
\usepackage{graphicx}
%%%%   Commandes perso FH
\newcommand{\ds}{\displaystyle}%   displaystyle
\newcommand{\cg}{\texttt{]}}% crocher gauche
\newcommand{\cd}{\texttt{[}}% crochet droit
\renewcommand{\d}{\,\text{d}}%  le d de différentiation
\newcommand{\e}{\,\text{e}\,}%    le e de l'exponentielle
\renewcommand{\i}{\text{\,i\,}}%  le i des complexes
\newcommand{\pg}{\geqslant}%      plus grand ou égal
\newcommand{\pp}{\leqslant}%      plus petit ou égal
\newcommand{\ssi}{\Leftrightarrow}% équivalent
\newcommand{\limit}[2]{\lim\limits_{#1 \to #2}}% limite
\newcommand{\integ}[2]{\displaystyle\int_{#1}^{\,#2}}% intégrale
%\newcommand{\t}[1]{\text{#1}}
\newcommand*{\point}[4]{
\psdots(#1,#2)
\uput[#3](#1,#2){#4}
}
% permet de placer un point et de marquer son nom en même temps
% abscisse ordonnée emplacement et nom
\usepackage{fancyhdr}
\usepackage[frenchb]{babel}
\DecimalMathComma% pas d'espace après la virgule en mode mathématique
\usepackage[np]{numprint}
\setlength\parindent{0mm}

\begin{document}
\setlength\parindent{0mm}
\marginpar{\rotatebox{90}{\textbf{A. P{}. M. E. P{}.}}}
\rhead{\textbf{A. P{}. M. E. P{}.}}
\lhead{\small Baccalauréat ES/L }
\lfoot{\small{Amérique du Nord}}
\rfoot{\small 30 mai 2014} 
\renewcommand \footrulewidth{.2pt}
\pagestyle{fancy} 
\thispagestyle{empty} 

\begin{center}{\Large \textbf{\decofourleft~Corrigé du baccalauréat ES  Amérique du Nord~\decofourright\\[10pt]
27 mai 2014}} 
\end{center}

\subsection*{\textsc{Exercice 1} \hfill 4 points}

\textbf{Commun à tous les candidats}

\begin{enumerate}

\item
\textbf{Réponse b.}

%L'aire sous la courbe est supérieure à une unité d'aire. La fonction $f$ n'est donc pas une fonction densité de probabilité. La réponse a n'est pas correcte.

La courbe représentative de $f$ est située au dessus de l'axe des abscisses; la fonction $f$ est donc positive sur $\cd -5\,;\,5\cg$.

%On peut tracer la courbe représentative de $f$ en un seul coup de crayon. La fonction $f$ est donc continue sur $[-5;5]$. La réponse c n'est pas correcte.

%La fonction $f$ semble croissante sur $[-5;0]$ et décroissante sur $[0;5]$. La seule valeur pour laquelle la dérivée semble s'annuler est 0. La réponse d n'est pas correcte.

\item \textbf{Réponse c.}

La courbe $\mathcal C$ admet en 0 une tangente horizontale donc $f'(0)=0$. 

%Par lecture graphique, $f'(1)$ est un nombre négatif. Les réponses a et d ne sont donc pas correctes. $f'(0)=0$. La réponse c est correcte.

\item \textbf{Réponse c.}

Le nombre dérivé de $f$ en 4 est le coefficient directeur de la tangente au point d'abscisse 4; on a donc $f'(4)=-\dfrac{1}{e^2}$.

\item \textbf{Réponse c.}

Le nombre A est l'aire sous la courbe entre -2 et 2; cette aire est comprise entre 3 et 4 unités d'aires.
\end{enumerate}

\subsection*{\textsc{Exercice 2} \hfill 6 points}

\textbf{Commun à tous les candidats}

\subsubsection*{Partie A}

\begin{enumerate}
\item L'arbre pondéré décrivant la situation est :

{\small
\begin{center}
\pstree[linecolor=blue,treemode=R,nodesepA=0pt,nodesepB=3pt,levelsep=4cm,treesep=1cm]{\TR{}}
{
	\pstree[nodesepA=3pt]{\TR{$T$}\taput{0,35}}
	  { 
		  \TR{$R$}\taput{0,45}
		  \TR{$\overline{R}$}\tbput{$1-0,45=0,55$}	   
	  }
	\pstree[nodesepA=3pt]{\TR{$\overline{T}$}\tbput{$1-0,35=0,65$}}
	  {
		  \TR{$R$}\taput{0,30}
		  \TR{$\overline{R}$}\tbput{$1-0,30=0,70$}	
	  }
}
\end{center}
}

\bigskip

\item
D'après la formule des probabilités totales:

\[ p(R)= P(R\cap T)+ P(R \cap{\overline{T}}) = 0,35 \times 0,45 + 0,65 \times 0,3 = \np{0,3525} \]

La probabilité qu'un appartement loué soit rentable est bien égale à \np{0,3525}.

\item La probabilité que l'appartement soit de type T1 ou T2 sachant qu'il est rentable est $P_R(T)$.

$$ P_R(T) = \frac{P(R\cap T)}{P(R)} = \frac {0,35 \times 0,45}{\np{0,3525}} \approx \np{0,4468}$$

%La probabilité qu'un appartement soit de type $T1$ ou $T2$ sachant qu'il est rentable est d'environ \np{0,4468}.
\end{enumerate}

\subsubsection*{Partie B}

La variable aléatoire $X$ suit la loi normale de moyenne $\mu = 35$ et d'écart type $\sigma=5$.

\begin{enumerate}

\item À la calculatrice, on trouve:
$ P(25 \leqslant X \leqslant 35) \approx \np{0,4772}$.
\item La probabilité qu'au moins 45 appartements parmi les 100 appartements loués soient rentables est $P(X \pg 45) \approx \np{0,0228}$.
\end{enumerate}

\subsubsection*{Partie C}

\begin{enumerate}
\item La fréquence d'appartements rentables dans l'échantillon est 
$ \dfrac{120}{280} \approx \np{0,4286}$.
\item On suppose que l'affirmation du responsable de l'agence est vraie. On calcule l'intervalle de fluctuation asymptotique au seuil de 95\,\% pour un échantillon de 280 dossiers. 

Les conditions pour calculer l'intervalle de fluctuation asymptotique sont remplies car 

\hfill $n = 280 \pg 30$, $np  = 168 \pg 5$ et $n(1-p) = 112 \pg 5$\hfill\,

\medskip

Les bornes de l'intervalle sont :

\[p - 1,96 \frac{\sqrt{p(1-p)}}{\sqrt{n}} = 0,6 - 1,96 \frac{\sqrt{0,6 \times 0,4}}{\sqrt{280}} \approx \np{0,54261}\]

\[ p + 1,96 \frac{\sqrt{p(1-p)}}{\sqrt{n}} = 0,6 + 1,96 \frac{\sqrt{0,6 \times 0,4}}{\sqrt{280}} \approx \np{0,65738}\]

L'intervalle de fluctuation asymptotique est donc $\cd \np{0,5426} \,;\, \np{0,6574}\cg$.

On constate que la fréquence observée \np{0,4286} n'appartient pas à cet intervalle. 

On rejette donc l'affirmation du responsable de cette agence.
\end{enumerate}

\subsection*{\textsc{Exercice 3} \hfill 5 points}

\textbf{Commun à tous les candidats}

\subsubsection*{Partie A}

\begin{enumerate}
\item La valeur demandée correspond à l'image de 8; elle peut être estimée à 97 secondes.

La durée de chargement pour \np{8000} personnes connectées est donc d'environ 97 secondes.
\item
	\begin{enumerate}
		\item Un antécédent de 15 par $f$ est à peu près égal à 2.
		\item Lorsque le durée de téléchargement est de 15 secondes, il y a environ \np{2000} personnes connectées.
	\end{enumerate}
\end{enumerate}

\subsubsection*{Partie B}

La fonction $g$ est définie sur $\cd 0,5\,;\, +\infty\cd$ par $g(x)=10x-8\ln(x)$.

\medskip

\begin{enumerate}
\item
	\begin{enumerate}
		\item Sur l'intervalle $\cd 0,5\,;\, +\infty\cd$, $g'(x) = 10 - \dfrac{8}{x}$.
		\item
On étudie le signe de $g'$ sur $\cd 0,5\,;\, +\infty\cd$:
$ 10 - \dfrac{8}{x} > 0 \Longleftrightarrow 10 > \dfrac{8}{x} \Longleftrightarrow 10x>8 \Longleftrightarrow x>0,8$

On en déduit le tableau de signe de $g'$ et les variations de $g$:\\


\psset{nodesep=3pt,arrowsize=2pt 3}  % paramètres
{\renewcommand{\arraystretch}{1.4}
$\begin{array}{|c|l*3{c}r|}
\hline
x & 0,5 & \hspace*{2.5cm} & 0,8 & \hspace*{2.5cm} & +\infty\\ 
\hline
g'(x)& & \pmb{-} & \vline\hspace{-2.7pt}0 & \pmb{+} & \\
\hline
& \Rnode{max1}{5+8 \ln{2}} & & & & \Rnode{max2}{\hspace*{0.5cm}} \\
g & & & & & \\
& & & \Rnode{min}{8 - 8 \ln 0,8} & &
\ncline{->}{max1}{min}
\ncline{->}{min}{max2}
\\
\hline
\end{array}$
}

\medskip
	\end{enumerate}
\item La fonction $G$ est définie sur $\cd 0,5\,;\, +\infty\cd$ par $G(x)=5x^2 + 8x - 8x\ln(x)$.

On calcule la dérivée de $G$ sur $\cd 0,5\,;\, +\infty\cd$:

$G'(x) = 10x + 8 - 8 \ln(x) -8x \, \dfrac{1}{x} = 10 x + 8 - 8 \ln(x) - 8 = 10x - 8 \ln(x) = g(x)$

$G$ est donc une primitive de $g$ sur $\cd 0,5\,;\, +\infty\cd$.

\item On pose $I=\dfrac{1}{2} \ds\int_{2}^4 g(x) \d x$.
	\begin{enumerate}
		\item
$ I = \dfrac{1}{2} \ds\int_2^4 g(x) \d x = \dfrac{1}{2} \left( G(4) - G(2) \right) = \dfrac{1}{2} \left( (80 + 32 - 32 \ln 4) - (20 + 16 - 16 \ln 2) \right)$

$\phantom{I} =  \dfrac{1}{2} \left( 112 - 64 \ln 2 - 36 + 16 \ln 2 \right) = 38 - 24 \ln 2$
		\item

$I=\dfrac{1}{2} \ds\int_{2}^4 g(x) \d x = \dfrac{1}{4-2} \ds\int_{2}^4 g(x) \d x$

$I$ est donc la valeur moyenne de la fonction $g$ entre 2 et 4.
De plus $I \approx 21,36$.

On peut donc dire que lorsque le nombre de connectés est compris entre \np{2000} et \np{4000}, la durée du téléchargement est en moyenne proche de 21 secondes.

\end{enumerate}

\end{enumerate}

\subsubsection*{Partie C}

On a vu dans la partie A qu'avec le modèle exponentiel, la durée de chargement pour \np{8000} connectés serait d'environ 97 secondes.\\
$g(8)=80 - 8 \ln 8 \approx 63$. Avec le modèle logarithmique, on aurait environ 63 secondes de temps de téléchargement.\\
On constate que le modèle exponentiel est plus proche de la réalité pour cette valeur.

\subsection*{\textsc{Exercice 4} \hfill 5 points}

\textbf{Candidats de la série ES n'ayant pas suivi l'enseignement de la spécialité et candidats de la série L}

\begin{enumerate}
\item
	\begin{enumerate}
		\item $0,95 \times \np{50000} = \np{47500}$\\
En 2014, il restera 95\,\% des arbres de 2013, soit \np{47500} arbres.

On replante \np{3000} arbres. Il y a donc $\np{47500} + \np{3000} =\np{50500}$ arbres en 2014.
		\item En 2013, il y a \np{50000} arbres; on a donc bien $u_0=\np{50000}$.

Chaque année, on ne conserve que 95\,\% des arbres de l'année précédente. 

L'année $2013+(n+1)$, le nombre d'arbres conservé est donc $0,95 u_n$. 

En ajoutant les \np{3000} nouveaux arbres, on a donc, pour tout entier $n$,
$u_{n+1} = 0,95 u_n + \np{3000}$.
	\end{enumerate}
\item

On considère la suite $v$ définie pour tout $n$ de $\N$ par $v_n =\np{60000}- u_n$ ;  donc $u_n=\np{60000}-v_n$.
	\begin{enumerate}
		\item Pour tout entier naturel $n$,

$ v_{n+1}=\np{60000}-u_{n+1}
=\np{60000}-(0,95 u_n + \np{3000}) 
= \np{57000} - 0,95 u_n$

$\phantom{v_{n+1}} 
= \np{57000} - 0,95 \times (\np{60000} - v_n)
= \np{57000} - \np{57000} + 0,95 v_n$
 
$\phantom{v_{n+1}} = 0,95 v_n$

$v_0= \np{60000} - u_0 = \np{60000} - \np{50000} = \np{10000}$

$(v_n)$ est donc une suite géométrique de raison $q=0,95$ et de premier terme $v_0=\np{10000}$.
		\item Pour tout entier naturel $n$,
$ v_n = v_0\times q^n = \np{10000} \times 0,95^n$.
		\item Pour tout entier naturel $n$,
$ u_n = \np{60000} - v_n = \np{60000} - \np{10000} \times 0,95^n = \np{10000} \left(6-0,95^n\right)$
		\item Comme $-1 < 0,95 < 1$, on peut dire que $\ds\lim_{n \to +\infty} 0,95^n = 0$.

On en déduit que $\ds\lim_{n \to +\infty} \left (6 - 0,95^n\right ) = 6$
et donc que $\ds\lim_{n \to +\infty} u_n = \np{60000}$.

		\item Au fil des années, le nombre d'arbres dans cette forêt s'approchera de \np{60000}.
	\end{enumerate}
\item
	\begin{enumerate}
		\item On résout l'inéquation $u_n \pg \np{57000}$ :

$\begin{array}{@{} l @{\ \iff\ } l l }
u_n \geqslant \np{57000} & \np{10000} \left (6-0,95^n\right ) \geqslant \np{57000} & \\
 & 6-0,95^n \pg 5,7 &\\
 & 0,3 \pg 0,95^n &\\
 & \ln 0,3 \pg n \ln 0,95 & (\text{la fonction ln est strictement croissante sur } \R_+^*)\\
 & \dfrac{\ln 0,3}{\ln 0,95} \pp n & (\ln 0,95 <0)
\end{array}$


$\dfrac{\ln 0,3}{\ln 0,95} \approx 23,47 $ donc\\
les solutions de l'inéquation sont les nombres entiers supérieurs ou égaux à 24.
		\item $2013 + 24 = 2037$ donc à partir de 2037, le nombre d'arbres sera supérieur à \np{57000}.
	\end{enumerate}
\item
	\begin{enumerate}
		\item Le premier et le deuxième algorithme ne conviennent pas car ils affichent un seul nombre alors qu'on attend plusieurs valeurs de la suite; l'instruction \og{}Afficher\fg{} doit obligatoirement se trouver dans une boucle.

Le troisième algorithme convient. Il commence par demander la valeur de $n$ à l'utilisateur, puis il affiche $u_0$ puis les $n-1$ valeurs suivantes de la suite. L'instruction \og Afficher\fg{} qui se trouve en dehors de la boucle permet d'afficher la dernière valeur calculée $u_n$.
		\item On retrouve avec l'algorithme 1 le résultat de la question 3; c'est à l'issue de la 24\up{e} année que le nombre d'arbres dans la forêt aura atteint \np{57000}.
	\end{enumerate}
\end{enumerate}

\subsection*{\textsc{Exercice 4} \hfill 5 points}

\textbf{Candidats ayant  suivi l'enseignement de spécialité}

%\medskip
% 
%Lors d'une campagne électorale, un homme politique doit effectuer une tournée dans les villes A, B, C, D, E, F, G et H, en utilisant le réseau autoroutier. Le graphe $\mathcal{G}$ ci-dessous, représente les différentes villes de la tournée et les tronçons d'autoroute reliant ces villes (une ville est représentée par un sommet, un tronçon d'autoroute par une arête) :
%
%\begin{center}
%\psset{unit=1cm}
%\begin{pspicture}(10,6)
%\cnodeput(0.4,4.5){A}{A}
%\cnodeput(2,5.5){B}{B}
%\cnodeput(5,5){C}{C}
%\cnodeput(1.25,1){D}{D}
%\cnodeput(3.25,2.5){E}{E}
%\cnodeput(9.75,2.5){F}{F}
%\cnodeput(7.5,3.5){G}{G}
%\cnodeput(6,0.5){H}{H}
%\ncline{A}{B}\ncline{C}{B}\ncline{C}{G}\ncline{G}{F}
%\ncline{F}{H}\ncline{G}{H}\ncline{B}{E}\ncline{C}{E}
%\ncline{E}{G}\ncline{D}{E}\ncline{D}{H}\ncline{A}{D}
%\ncline{C}{H}
%\end{pspicture}
%\end{center}

%\textbf{Partie A}
%\medskip
 
\subsubsection*{Partie A} 
 
\begin{enumerate}
\item % Déterminer, en justifiant, si le graphe $\mathcal{G}$ est : 
Dans le graphe $\mathcal{G}$ donné dans le texte:
	\begin{enumerate}
		\item les sommets A et C ne sont pas reliés par une arête, donc le graphe $\mathcal{G}$ n'est pas complet;

		\item il existe un chemin reliant deux sommets quelconques, donc le graphe $\mathcal{G}$  est connexe.

	\end{enumerate} 
\item 
	\begin{enumerate}
		\item %Justifier qu'il est possible d'organiser la tournée en passant au moins une fois par chaque ville, tout en empruntant une fois et une seule chaque tronçon d'autoroute. 
Déterminons les degrés de chaque sommet:

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline 
Sommet & A & B & C & D & E & F & G & H \\ 
\hline 
Degré & 2 & 3 & 4 & 3 & 4 & 2 & 4 & 4 \\ 
\hline 
\end{tabular}
\end{center} 

Il y a exactement deux sommets de degrés impairs, B et D, donc le graphe $\mathcal G$ admet un chemin eulérien, c'est-à-dire un chemin qui part d'un des sommets de degré impair, qui passe une fois et une seule par chaque arête, et qui arrive à l'autre sommet de degré impair.
		\item Exemple de trajet empruntant une fois et une seule chaque tronçon d'autoroute: 
		
{\centering B -- A -- D -- E -- B -- C -- E -- G -- C -- H -- F -- G -- H -- D\par}		
	\end{enumerate}
\item On appelle $M$ la matrice d'adjacence associée au graphe $\mathcal{G}$ (les sommets étant pris dans l'ordre alphabétique). 
	\begin{enumerate}
		\item% Déterminer la matrice $M$.

La matrice d'adjacence $M$ associée au graphe est une matrice carrée d'ordre 8, ne contenant que des 0 et des 1. Si une arête relie le sommet numéro $i$ ($1 \leqslant i \leqslant 8$) au sommet numéro $j$ ($1 \leqslant j \leqslant 8$), on mettra un 1 à la ligne $i$ et la colonne $j$ de la matrice; sinon on mettra un 0.

\medskip

Donc la matrice d'adjacence est
$M =
\begin{pmatrix}
0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\%  ligne A
1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\%  ligne B
0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 \\%  ligne C
1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\%  ligne D
0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\%  ligne E
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\%  ligne F
0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\%  ligne G
0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\%  ligne H
\end{pmatrix}$
		\item On donne la matrice 

\hfill$M^3 = \begin{pmatrix}
0 &5 &3 &5 &1 &1 &4 &1\\ 
5 &2 &7 &2 &8 &3 &3 &5\\ 
3 &7 &6 &4 &9 &3 &9 &10\\ 
5 &2 &4 &0 &9 &2 &3 &8\\ 
1 &8 &9 &9 &4 &4 &10 &4\\ 
1 &3 &3 &2 &4 &2 &6 &6\\ 
4 &3 &9 &3 &10 &6 &6 &9 \\
1 &5 &10 &8 &4 &6 &9 &4\\
\end{pmatrix}$\hfill\,

La matrice $M^3$ donne le nombre de chemins de longueur 3 entre tous les sommets. Le sommet E est le numéro 5, le sommet H le numéro 8; le nombre de chemins de longueur 3 allant de E à H est le nombre situé dans la matrice à la ligne 5 et la colonne 8. 

Il y a donc 4 chemins de longueur 3 allant de E vers H. 
 
%Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant E à H. 

%Préciser ces chemins.

Ces chemins sont : E -- B -- C -- H; E -- C -- G -- H; E -- G -- F -- H et E -- G -- C -- H. 

	\end{enumerate}
\end{enumerate}

%\bigskip
%\textbf{Partie B}
%\medskip
 
\subsubsection*{Partie B} 
 
%Des contraintes d'organisation obligent cet homme politique à se rendre dans la ville F après la ville A. Le graphe $\mathcal{G}$ est complété ci-dessous par les longueurs en kilomètre de chaque tronçon d'autoroute.
%
%\begin{center}
%\psset{unit=1cm}
%\begin{pspicture}(10,6)
%\cnodeput(0.4,4.5){A}{A}
%\cnodeput(2,5.5){B}{B}
%\cnodeput(5,5){C}{C}
%\cnodeput(1.25,1){D}{D}
%\cnodeput(3.25,2.5){E}{E}
%\cnodeput(9.75,2.5){F}{F}
%\cnodeput(7.5,4){G}{G}
%\cnodeput(7,0.5){H}{H}
%\ncline{A}{B}\ncput*{\bf \sf 400}
%\ncline{C}{B}\ncput*{\bf \sf 600}
%\ncline{C}{G}\ncput*{\bf \sf 550}
%\ncline{G}{F}\ncput*{\bf \sf 200}
%\ncline{F}{H}\ncput*{\bf \sf 400}
%\ncline{G}{H}\ncput*{\bf \sf 300}
%\ncline{B}{E}\ncput*{\bf \sf 400}
%\ncline{C}{E}\ncput*{\bf \sf 350}
%\ncline{E}{G}\ncput*{\bf \sf 600}
%\ncline{D}{E}\ncput*{\bf \sf 300}
%\ncline{D}{H}\ncput*{\bf \sf 900}
%\ncline{A}{D}\ncput*{\bf \sf 600}
%\ncline{C}{H}\ncput*{\bf \sf 450}
%\end{pspicture}
%\end{center} 

Le graphe $\mathcal G$ est complété par des distances kilométriques entre les sommets.

On détermine, en utilisant l'algorithme de Dijkstra, le trajet autoroutier le plus court pour aller de A à F :

\begin{center}
{\renewcommand{\arraystretch}{1.3}
\small
\newcommand{\sur}[1]{\fcolorbox{yellow}{yellow}{#1}}
\begin{tabular}{|*{9}{c|}}
\hline 
\  A\   &  B  &  C  &  D  &  E   &   F   & G &   H   &  { On garde} \\ 
\hline 
\sur{0} & $\infty$ 		& $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$  & $\infty$  & A \\
\hline
 		& \sur{400 (A)} 	& $\infty$ 	& 600 (A) & $\infty$ & $\infty$ & $\infty$ & $\infty$ &  B (A) \\
\hline
 &  & 1000 (B) & \sur{600 (A)} & 800 (B) & $\infty$ & $\infty$ & $\infty$ & D (A)  \\
 \hline
 &  & 1000 (B)  & & \sur{800 (B)} & $\infty$ & $\infty$ & \np{1500} (D) &  \\[-3pt]
 &  &           & & \sout{900 (D)}&          &          &  & E (B) \\
\hline
 &  & \sur{\np{1000} (B)} &  &  & $\infty$ & \np{1400} (E)& \np{1500} (D) &  \\[-3pt]
 &  & \sout{\np{1150} (E)} &  &  &         &         &          & C (B) \\
\hline
 &  &  &  &  & $\infty$ & \sur{\np{1400} (E)} & \np{1450} (C)  &  \\[-3pt]
 &  &  &  &  &  & \sout{\np{1550} (C)} & & G (E) \\
\hline
 &  &  &  &  & \sur{\np{1600} (G)} &   & \sout{\np{1750} (G)} &  H(C) \\
\hline
 &	&  &  &	 &\sur{\np{1600} (G)}&		&						&F(G)\\ \hline
\end{tabular}
 }
\end{center} 

\normalsize

\medskip

Le trajet autoroutier le plus court pour aller de A à F est:
A $\stackrel{400}{\longrightarrow}$
B $\stackrel{400}{\longrightarrow}$
E $\stackrel{600}{\longrightarrow}$ 
G $\stackrel{200}{\longrightarrow}$ F

\medskip

Ce trajet a une longueur totale de \np{1600} kilomètres. 
\end{document} 