\documentclass[a4paper,11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[french]{babel}
\usepackage{amsmath,amsfonts,amsthm,amssymb,amsbsy,amscd,mathrsfs}
\usepackage{lmodern}
\usepackage{fourier}
%\usepackage{times,mathptmx}
%\DeclareSymbolFont{lmodern}{U}{euex}{m}{n}
%\DeclareMathSymbol\infty \mathord{lmodern}{"31}
\usepackage[scaled=0.875]{helvet} % ss
\usepackage{textcomp}
\usepackage{dsfont} % pour les symboles des ensembles
\usepackage[left=2cm,right=2cm,top=2cm,bottom=2.5cm]{geometry}
\usepackage{fancyhdr} 
\fancyhf{}
\setlength{\headheight}{26pt}
\setlength{\footskip}{18pt}
\renewcommand {\headrulewidth}{0pt}
\renewcommand {\footrulewidth}{0pt}
\usepackage{lastpage}
%\usepackage{makeidx}
\usepackage{graphicx} % inclure le fichier graphique de pondichery 2010
\usepackage{hyperxmp}
\usepackage[colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\pagestyle{fancy}
\usepackage{array}
\usepackage{tabularx}
\usepackage{multirow}
\usepackage{hhline}
\usepackage[table]{xcolor}
\usepackage{mathtools} %pour l'alignement des termes d'une matrice
\usepackage{fltpoint}
\usepackage{xcolor,colortbl}
\usepackage{pstricks,pst-all,pst-plot,pstricks-add,pst-tree,pst-3dplot,pst-func}
\usepackage{ifthen}
\usepackage{calc}
\usepackage{esvect}
\usepackage{pifont}
\usepackage[np]{numprint}
\setlength{\parindent}{0mm}
\usepackage [alwaysadjust]{paralist}
\setdefaultenum {1.}{a)}{}{}
\hyphenpenalty=10000 
\tolerance=2000
\emergencystretch=1em
\widowpenalty=10000
\clubpenalty=10000
\raggedbottom
\renewcommand*{\tabularxcolumn}[1]{m{#1}} %centrage vertical des cellules d'un tableau tabularx
\newcommand{\Oij}{$\left( {{\mathrm{O}};\vec i,\vec j} \right)$}
\newcommand{\Oijk}{$\left( {{\mathrm{O}};\vec i,\vec j ,\vec k} \right)$}
\newcommand{\euro}{\texteuro{}}
\newcommand{\R}{\mathds {R}}
%\newcommand{\C}{\mathds {C}}
\newcommand{\N}{\mathds {N}}
\newcommand{\Z}{\mathds {Z}}
\newcommand{\Q}{\mathds {Q}}
\newcommand{\e}{\mathrm {e}}
\newcommand{\dd}{\,\mathrm{d}}
\DecimalMathComma

% en-tête
\lhead{\footnotesize{\textsf{Lycée JANSON DE SAILLY\\ 30 janvier 2018}}} %gauche
\chead{\textsf{\textcolor{red}{\textbf{\textsc{graphes : plus court chemin}}}}} %centre
\rhead{\footnotesize{\textsf{T\textsuperscript{le} ES 4}}}%droit
%pied de page                                              
\rfoot{\scriptsize{\textsf{Page~\thepage{}~sur~\pageref{LastPage}}}}
\lfoot{ \htmladdnormallink{\scriptsize{\textsf{\textsc{A. Yallouz (MATH@ES)}}}}{http://yallouz.arie.free.fr}}


\setcounter{secnumdepth}{3}
\makeatletter
\renewcommand\section{\@startsection {section}{1}{\z@}%
                                   {-3.5ex \@plus -1ex \@minus -.2ex}%
                                   {2.3ex \@plus.2ex}%
                                  {\reset@font\bfseries\red\sffamily\scshape}} 
                                 
\renewcommand\subsection{\@startsection {subsection}{2}{\z@}%
                                   {-3.5ex \@plus -1ex \@minus -.2ex}%
                                   {2.3ex \@plus.2ex}%
                                   {\reset@font\bfseries\sffamily\scshape\blue}}                                   
\renewcommand\subsubsection{\@startsection {subsubsection}{3}{\z@}%
	{-3.5ex \@plus -1ex \@minus -.2ex}%
	{2.3ex \@plus .2ex}%
	{\reset@font\bfseries\sffamily\scshape\small}}
\makeatother
\setcounter{secnumdepth}{2}

\renewcommand\thesection{\Roman {section}}
\renewcommand\thesubsection{\arabic {subsection}}
%%%% debut macro %%%%
\makeatletter
\renewcommand\theequation{\thesection.\arabic{equation}}
\@addtoreset{equation}{section}
\makeatother
%%%% fin macro %%%%

\newcounter{nexo}           % déclaration du numéro d'exo
\setcounter{nexo}{0}        % initialisation du numero

\newcommand{\exo}{
  \refstepcounter{nexo} 
  \par{\textsf{\textbf{\textcolor{blue}{{\small{EXERCICE \; \arabic{nexo}}}}}}}}
  
  \newcounter{nactivite}           % déclaration du numéro d'exo
\setcounter{nactivite}{0}        % initialisation du numero

\newcommand{\act}{
  \stepcounter{nactivite} 
  \par{\textsf{\textbf{\textcolor{blue}{{\small{\textsc{activité} \; \arabic{nactivite}}}}}}}}

%%%% debut macro %%%%
\makeatletter
\@addtoreset{nactivite}{section}
\makeatother
%%%% fin macro %%%%

\newrgbcolor{Rfond}{.995 0.945 .985}  
\newrgbcolor{Rougef}{.8 0.1 .2}
\newrgbcolor{Rbord}{.6 0.1 .4}

\newcommand{\cadreR}[1]{%
\psframebox[framesep=.8em,linecolor=black,linewidth=0.25pt,framearc=0.2,fillstyle=solid,fillcolor=Rfond]{\begin{minipage}{\linewidth-1.6em}%
#1\end{minipage}}}
\newcommand{\cadreB}[1]{%
\psframebox[framesep=.8em,linecolor=black,linewidth=0.25pt,framearc=0.2]{\begin{minipage}{\linewidth-1.6em}%
#1\end{minipage}}}

\newcommand{\dem}{
 \medskip
  \par{\textsf{\textsc{{\small{\ding{106}\: démonstration}}}}}%
   \medskip}
  

   \newcommand{\preuve}{
 \medskip
  \par{\textsf{\textsc{{\small{\ding{106}\: preuve}}}}}%
   \medskip} 
    

\newcommand{\encadrer}[1]{
{\setlength{\fboxsep}{2mm}
\fbox{#1}}}

  
\hypersetup{
pdftitle={Algorithme de Dijkstra}, 
pdfauthor={Arié Yallouz},   
pdfsubject={Graphes : plus court chemin}, 
pdfkeywords={Graphe pondéré, plus court chemin, algorithme de Dijkstra, cours, exercices.},
pdfcontacturl={http//yallouz.arie.free.fr/},
pdflang={fr},
baseurl={http://yallouz.arie.free.fr/terminale_cours/index_terminale_cours.php}
}

\begin{document}
 
 La recherche du meilleur itinéraire que ce soit en distance, en temps ou en coût d'un point à un autre peut être modélisée par la recherche du plus court chemin dans un graphe.
 
Dans ce paragraphe, on s'intéresse à la recherche d'un plus court chemin dans un graphe entre deux sommets donnés. 

   \section{graphe pondéré}
   
    \subsection{définition}
   
     \cadreB{
     On appelle \emph{graphe pondéré}, un graphe (orienté ou non) dont les arêtes ont été affectées d'un nombre appelé poids (ou coût).
}

  \medskip
   
Par analogie avec la matrice d'adjacence, on peut définir la matrice des poids $P\left( a_{i,j} \right)$ du graphe, dont les coefficients $a_{i,j}$ correspondent aux poids des arêtes (ou des arcs dans le cas d'un graphe orienté) :  \[a_{i,j} = \begin{cases}
0    & \text{si } i=j \\
\infty & \text{s'il n'existe pas d'arêtes ( ou d'arc) entre les sommets } x_i \text{ et } x_j \\
p_{ij} & \text{où } p_{ij}  \text{ est le poids de l'arête ( ou de l'arc) entre les sommets  } x_i \text{ et } x_j \\
\end{cases}
\]

On utilise le symbole $\infty$  pour indiquer qu'il n'y a pas d'arêtes entre deux sommets.
 
\medskip

\textsf {\textsc{\small{exemple}}}

\medskip


\begin{tabularx}{\linewidth}{@{}m{9cm} >{\raggedright \arraybackslash}X@{}}
\psset{xunit=2.5cm, yunit=2cm}
\begin{pspicture}(-.2,-.2)(3.2,2.5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.2,linewidth=0.75pt, linecolor=bleu}
\multido{\n=0+3,\i=1+1}{2}{\dotnode(\n,2){S\i}}
\multido{\n=3+-3,\i=3+1}{2}{\dotnode(\n,0){S\i}}
\multido{\n=1+1,\i=5+1}{2}{\dotnode(\n,1){S\i}}
\psset{linewidth=1pt,linecolor=bleu, ArrowInside=->,arrowscale= 1.8 1.2}
\ncarc[arcangle=10]{S1}{S2}\naput*{\footnotesize{\textsf{\prune{8}}}}
\ncline{S1}{S5}\naput*[nrot=:U]{\footnotesize{\textsf{\prune{3}}}}
\ncarc[arcangle=10]{S2}{S1}\naput*{\footnotesize{\textsf{\prune{7}}}}
\ncarc[arcangle=15]{S2}{S3}\naput*{\footnotesize{\textsf{\prune{7}}}}
\ncarc[arcangle=10]{S2}{S6}\nbput*[nrot=:D]{\footnotesize{\textsf{\prune{10}}}}
\ncarc[arcangle=15]{S3}{S2}\naput*{\footnotesize{\textsf{\prune{6}}}}
\ncline{S3}{S4}\naput*{\footnotesize{\textsf{\prune{3}}}}
\ncline{S4}{S1}\naput*{\footnotesize{\textsf{\prune{12}}}}
\ncarc[arcangle=-10]{S4}{S6}\nbput*[nrot=:U]{\footnotesize{\textsf{\prune{3}}}}
\ncline{S5}{S2}\naput*[nrot=:U]{\footnotesize{\textsf{\prune{6}}}}
\ncline{S5}{S4}\nbput*[nrot=:D]{\footnotesize{\textsf{\prune{11}}}}
\ncline{S6}{S3}\nbput*[nrot=:U]{\footnotesize{\textsf{\prune{1}}}}
\ncline{S6}{S5}\naput*{\footnotesize{\textsf{\prune{11}}}}
\uput[u](S1){\small{\bleu{$A$}}}
\uput[u](S2){\small{\bleu{$B$}}}
\uput[d](S3){\small{\bleu{$C$}}}
\uput[d](S4){\small{\bleu{$D$}}}
\uput[l](S5){\small{\bleu{$E$}}}
\uput[r](S6){\small{\bleu{$F$}}}
\end{pspicture} &   Les sommets du graphe étant rangés dans l'ordre alphabétique : \[P = \begin{pmatrix}
0 & 8 & \infty & \infty & 3 & \infty  \\ 
7 & 0 & 7 & \infty & \infty & 10  \\ 
\infty & 6 & 0 & 3 & \infty & \infty  \\ 
11 & \infty & \infty & 0 & \infty & 3  \\ 
\infty & 6 & \infty & 11 & 0 & \infty \\ 
\infty & \infty & 1 & \infty & 12 & 0  \\ 
\end{pmatrix}\]
   \end{tabularx}
   
\medskip
   
   \subsection{longueur d'un chemin}
   
  \cadreB{
   Soit $C(x, y)$ un chemin (ou une chaîne) dans un graphe pondéré $G$ du sommet $x$ vers le sommet $y$. La longueur de ce chemin est égale à la somme des poids de chacun arcs ( ou de chacune des arêtes) qui le constituent.
} 

\medskip

\textsf {\textsc{\small{remarque}}}

\medskip

Cette définition généralise la définition de la longueur d'une chaîne dans un graphe non pondéré, il suffit d'attribuer un poids égal à 1 à chaque arête du graphe.

\medskip

Dans l'exemple précédent, la longueur du chemin $AEBF$ est 19. 

Si on souhaite déterminer le plus court chemin du sommet A au sommet F, on peut essayer d'énumérer tous les chemins $ABF$, $AEBF$, $AEDF$, $ABCDF$, $AEBCDF$ et calculer leurs longueurs. Mais avec un graphe de taille plus importante, ceci risque de devenir rapidement impossible. 
 
Pour résoudre ce problème, on fait appel à des algorithmes.

\medskip

En terminale ES, on n'étudie que le cas particulier où \textbf{les poids de tous les arcs sont des réels positifs}.

\section{algorithme de dijkstra}

E. W. Dijkstra (1930-2002) a proposé en 1959 un algorithme qui permet de calculer le plus court chemin entre un sommet particulier et tous les autres dans un graphe pondéré dont tous les poids sont positifs.

L'algorithme comporte une phase d'initialisation. \`A chaque sommet on attribue un poids qui vaut 0 pour le sommet de départ et infini pour les autres sommets. 
 
Le traitement de l'algorithme consiste à examiner les sommets les uns après les autres et à sélectionner le sommet $x$ auquel on a affecté la plus petite distance du sommet de départ jusqu'à $x$.

On recommence tant qu'il reste des sommets à sélectionner. 

\medskip

Soit $G$ un graphe \emph{connexe} dont les arêtes sont pondérées par des nombres \emph{positifs}.

\bigskip

\textsf {\textsc{notations :}}
\begin{itemize}
\item[] $S$ la liste des sommets du graphe
\item[] $s_0$ le sommet du graphe à partir duquel on veut déterminer les plus courts chemins aux autres sommets
\item[] $l (x,y)$ le poids de l'arête entre deux sommets $x$ et $y$
\item[] $\delta_s (x)$ la longueur d'un chemin du sommets $s_0$ au sommet $x$
\item[] $V^+ (x)$ la liste des successeurs du sommet $x$
\item[] $p (x)$ le prédécesseur du sommet $x$
\item[] $X$ liste des sommets restant à traiter.
\item[] $E$ liste des sommets déjà traités.
\end{itemize}

\textsf {\textsc{initialisation :}}
\begin{itemize}
\item[]\textsf {\textsc{\small{Pour Chaque}}} $x \in S$ \textsf{\textsc{\small{Faire}}} $\delta_s (x)=\infty$ \hfill \emph{\footnotesize{On attribue un poids $\infty$ à chacun des sommets $x$ }}
 \item[]$\delta_s (s_0)=0$  \hfill \emph{\footnotesize{Le poids du sommet $s_0$ est nul}}
 \item[] $X=S$  \hfill \emph{\footnotesize{La liste des sommets restant à traiter est initialisée à $S$}}
 \item[]$E=\varnothing$  \hfill \emph{\footnotesize{La liste des sommets déjà traités vide}}
\end{itemize}

\textsf {\textsc{traitement :}}
\begin{itemize}
\item[]\textsf{\textsc{\small{Tant{\_}que}}} $X \ne \varnothing$ \textsf{\textsc{\small{Faire}}} \hfill {\footnotesize{\emph{Tant que la liste des sommets restant à traiter n'est pas vide }}}

\leftskip=1em

\vrule\hspace{.8em}\begin{minipage}{\linewidth-1.8em}
 Sélectionner dans la liste $X$ le sommet $x$ avec  $\delta_s (x)$ minimum
 
 Retirer le sommet $x$ de la liste $X$
 
 Ajouter le sommet $x$ à la liste $E$
 
 \textsf {\textsc{\small{Pour Chaque}}} $y \in V^+ (x) \cap X$ \textsf{\textsc{\small{Faire}}}  \hfill {\emph{\footnotesize{On examine tous les successeurs $y$ du sommet $x$ qui ne sont pas traités}}}

\leftskip=1em

\vrule\hspace{.8em}\begin{minipage}{\linewidth-2.8em}
 \textsf{\textsc{\small{Si}}} $\delta_s (y) > \delta_s (x) + l(x,y)$ \textsf{\textsc{\small{Alors}}}
 
 \begin{tabular}{l|l l}
& $\delta_s (y)$ prend la valeur $\delta_s (x) + l(x,y)$ & \footnotesize{\emph{La distance du sommet $s_0$ au sommet $y$ est minimale}}\\
& $p(y) = x$& \footnotesize{\emph{le sommet $x$ est le prédécesseur du sommet $y$}}
\end{tabular}

\medskip

\textsf{\textsc{\small{Fin Si}}}
\end{minipage} 

\leftskip=0em

\medskip

\textsf{\textsc{\small{Fin Pour}}}

\end{minipage}
 

\leftskip=0em

\medskip
\textsf{\textsc{\small{Fin Tant{\_}que}}} 
\end{itemize}

\pagebreak
\textsf {\textsc{\small{exemple}}}

\medskip

 Considérons le graphe suivant :  
 
\begin{center}
\psset{xunit=2.5cm, yunit=2.5cm}
\begin{pspicture}(-.2,-.2)(3.2,2.2)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.2,linewidth=0.75pt, linecolor=bleu}
\multido{\n=0+3,\i=1+1}{2}{\dotnode(\n,2){S\i}}
\multido{\n=3+-3,\i=3+1}{2}{\dotnode(\n,0){S\i}}
\multido{\n=1+1,\i=5+1}{2}{\dotnode(\n,1){S\i}}
\psset{linewidth=1pt,linecolor=bleu, ArrowInside=->,arrowscale= 1.8 1.2}
\ncarc[arcangle=10]{S1}{S2}\naput*{\footnotesize{\textsf{\prune{8}}}}
\ncline{S1}{S5}\naput*[nrot=:U]{\footnotesize{\textsf{\prune{3}}}}
\ncarc[arcangle=10]{S2}{S1}\naput*{\footnotesize{\textsf{\prune{7}}}}
\ncarc[arcangle=15]{S2}{S3}\naput*{\footnotesize{\textsf{\prune{7}}}}
\ncarc[arcangle=10]{S2}{S6}\nbput*[nrot=:D]{\footnotesize{\textsf{\prune{10}}}}
\ncarc[arcangle=15]{S3}{S2}\naput*{\footnotesize{\textsf{\prune{6}}}}
\ncline{S3}{S4}\naput*{\footnotesize{\textsf{\prune{3}}}}
\ncline{S4}{S1}\naput*{\footnotesize{\textsf{\prune{12}}}}
\ncarc[arcangle=-10]{S4}{S6}\nbput*[nrot=:U]{\footnotesize{\textsf{\prune{3}}}}
\ncline{S5}{S2}\naput*[nrot=:U]{\footnotesize{\textsf{\prune{6}}}}
\ncline{S5}{S4}\nbput*[nrot=:D]{\footnotesize{\textsf{\prune{11}}}}
\ncline{S6}{S3}\nbput*[nrot=:U]{\footnotesize{\textsf{\prune{1}}}}
\ncline{S6}{S5}\naput*{\footnotesize{\textsf{\prune{11}}}}
\uput[u](S1){\small{\bleu{$A$}}}
\uput[u](S2){\small{\bleu{$B$}}}
\uput[d](S3){\small{\bleu{$C$}}}
\uput[d](S4){\small{\bleu{$D$}}}
\uput[l](S5){\small{\bleu{$E$}}}
\uput[r](S6){\small{\bleu{$F$}}}
\end{pspicture}
\end{center}

On souhaite déterminer le plus court chemin du sommet A au sommet F. 

\medskip

\begin{tabularx}{\linewidth}{*{6}{|c}| >{\centering \arraybackslash}m{1.5cm}|>{\small}X}\cline{1-7}
A & B & C & D & E & F & \textsf{\footnotesize{Sommets sélectionnés}} & \\ \cline{1-7}
0 & $\infty$ & $\infty$ & $\infty$ &$\infty$ & $\infty$ & $A(0)$ & Initialisation ;

$\delta (A)=0$  $A$ est sélectionné.\\ \cline{1-7}
 \multicolumn{1}{c|}{} & $8 (A)$ & $\infty$ & $\infty$ & $\mathbf{3(A)}$ & $\infty$ & $E(3)$ & $B$ et $E$ sont les successeurs de $A$ qui ne sont pas traités ;
 
 $0+8 <\infty$ donc $\delta (B)=8$ et $p(B)=A$ ; 
 
 $0+3 <\infty$ donc $\delta (E)=3$ et $p(E)=A$ ;
 
$\delta_{min}=3$, Le sommet $E$ est sélectionné. \\ \cline{2-7}
 \multicolumn{1}{c|}{} & $\mathbf{8 (A)}$ & $\infty$ & $14(E)$ &  & $\infty$ & $B(8)$ & $B$ et $D$ sont les successeurs de $E$ qui ne sont pas traités ;

 $3+6 >8$ on ne change pas $\delta (B)=8$ et $p(B)=A$ ; 
 
 $3+11 <\infty$ donc $\delta (D)=14$ et $p(D)=E$ ;
 
$\delta_{min}=8$, Le sommet $B$ est sélectionné.\\ \cline{2-4}\cline{6-7}
 \multicolumn{2}{c|}{}   & $15 (B)$ & $\mathbf{14(E)}$ &  & $18(B)$ & $D(14)$ & $C$ et $F$ sont les successeurs de $B$ qui ne sont pas traités ;

 $8+7 <\infty$ donc $\delta (C)=15$ et $p(C)=B$ ; 
 
 $8+10 <\infty$ donc $\delta (F)=18$ et $p(F)=B$ ;
 
$\delta_{min}=14$, Le sommet $D$ est sélectionné.\\ \cline{3-4}\cline{6-7}

\multicolumn{2}{c|}{} & $\mathbf{15 (B)}$  &  \multicolumn{2}{c|}{}  & $17(D)$ & $C(15)$ & $F$ est le successeur de $D$ qui n'est pas traité ;

 $14+3 <18$ donc $\delta (F)=17$ et $p(F)=D$ ; 
 
 
$\delta_{min}=15$, Le sommet $C$ est sélectionné.\\ \cline{3-3}\cline{6-7}
\multicolumn{5}{c|}{}  & $\mathbf{17(D)}$ & $F(17)$ & le successeur de $C$ est déjà traité ;
 
 
Le sommet $F$ est le dernier sommet traité.\\\cline{6-7}
   \end{tabularx}
   
   \bigskip
   
  \cadreB {
\begin{itemize}
	\item L'algorithme de Dijkstra fournit les longueurs des plus courts chemins du sommet origine aux différents sommets.
	\item Pour déterminer le plus court chemin du sommet origine à un sommet $x$, il suffit de remonter la liste des prédécesseurs en partant de $x$. 	
\end{itemize}
} 

\bigskip

Ainsi, le plus court chemin de A à F est un chemin de longueur 17.

Dans la colonne F on lit que le prédécesseur de F est le sommet D. Le prédécesseur de D est E et, le prédécesseur de E est A.

Ainsi, la liste des prédécesseurs est  $\mathrm{F} \longleftarrow \mathrm{D} \longleftarrow \mathrm{E} \longleftarrow \mathrm{A}$.

Le plus court chemin de A à F est donc : A-E-D-F. 

\newpage

\addcontentsline{toc}{section}{Exercices}

\exo

 \medskip 


Le graphe ci-dessous indique les différentes liaisons entre plusieurs lieux. Le long de chaque arête figure la distance en kilomètres séparant les différents lieux.

En précisant la méthode utilisée, déterminer le plus court chemin possible pour aller de A à L.

\begin{center}
\scalebox{.8}{\psset{unit=3cm}
\begin{pspicture}(0,0)(3,2)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{linecolor=bleu,linewidth=1pt}
\cnodeput(0,2){A}{\textsf{\bleu A}}
\cnodeput(0,1){E}{\textsf{\bleu E}}
\cnodeput(0,0){I}{\textsf{\bleu I}}
\cnodeput(1,2){B}{\textsf{\bleu B}}
\cnodeput(1,1){F}{\textsf{\bleu F}}
\cnodeput(1,0){J}{\textsf{\bleu J}}
\cnodeput(2,2){C}{\textsf{\bleu C}}
\cnodeput(2,1){G}{\textsf{\bleu G}}
\cnodeput(2,0){K}{\textsf{\bleu k}}
\cnodeput(3,2){D}{\textsf{\bleu D}}
\cnodeput(3,1){H}{\textsf{\bleu H}}
\cnodeput(3,0){L}{\textsf{\bleu L}}
\ncline{-}{I}{E}\ncput*{\small{\textsf{\prune 1}}}
\ncline{-}{I}{J}\ncput*{\small{\textsf{\prune 2}}}
\ncline{-}{J}{E}\ncput*{\small{\textsf{\prune 4}}}
\ncline{-}{E}{A}\ncput*{\small{\textsf{\prune 2}}}
\ncline{-}{F}{J}\ncput*{\small{\textsf{\prune 2}}}
\ncline{-}{E}{F}\ncput*{\small{\textsf{\prune 6}}}
\ncline{-}{A}{B}\ncput*{\small{\textsf{\prune 10}}}
\ncline{-}{A}{F}\ncput*{\small{\textsf{\prune 8}}}
\ncline{-}{B}{F}\ncput*{\small{\textsf{\prune 3}}}
\ncline{-}{B}{C}\ncput*{\small{\textsf{\prune 2}}}
\ncline{-}{C}{D}\ncput*{\small{\textsf{\prune 5}}}
\ncline{-}{C}{G}\ncput*{\small{\textsf{\prune 1}}}
\ncline{-}{B}{G}\ncput*{\small{\textsf{\prune 5}}}
\ncline{-}{F}{G}\ncput*{\small{\textsf{\prune 3}}}
\ncline{-}{F}{J}\ncput*{\small{\textsf{\prune 2}}}
\ncline{-}{J}{G}\ncput*{\small{\textsf{\prune 6}}}
\ncline{-}{G}{K}\ncput*{\small{\textsf{\prune 8}}}
\ncline{-}{G}{H}\ncput*{\small{\textsf{\prune 10}}}
\ncline{-}{G}{D}\ncput*{\small{\textsf{\prune 3}}}
\ncline{-}{D}{H}\ncput*{\small{\textsf{\prune 2}}}
\ncline{-}{L}{G}\ncput*{\small{\textsf{\prune 9}}}
\ncline{-}{K}{L}\ncput*{\small{\textsf{\prune 3}}}
\ncline{-}{H}{L}\ncput*{\small{\textsf{\prune 3}}}
\end{pspicture}}
\end{center}

 \bigskip 
 
% \exo
% 
% \medskip
% 
%  Exécuter l'algorithme de Dijkstra sur le graphe suivant, à partir du sommet F, puis à partir du sommet A.
%  
% \begin{center}
%\psset{unit=1cm}
%\begin{pspicture}(8,4.2)
%\newrgbcolor{bleu}{0.1 0.05 .5}
%\newrgbcolor{prune}{.6 0 .48}
%\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
%\rput{0}(2,2){\multido{\n=90+60,\i=1+1}{6}{\dotnode(2;\n){S\i}}} 
%\dotnode(2,2){S8}\dotnode(8,1){S7}
%\psset{linewidth=1pt,linecolor=bleu, ArrowInside=->,arrowscale= 1.8 1.2}
% \ncline{S1}{S2}\nbput*[nrot=:D]{\footnotesize{\textsf{\prune{3}}}} \ncline{S2}{S3}\nbput*{\footnotesize{\textsf{\prune{5}}}} \ncline{S3}{S4}\nbput*[nrot=:U]{\footnotesize{\textsf{\prune{4}}}}  \ncline{S4}{S7}\nbput*[nrot=:U]{\footnotesize{\textsf{\prune{14}}}} \ncline{S4}{S5}\naput*[nrot=:U]{\footnotesize{\textsf{\prune{6}}}} \ncline{S4}{S8}\naput*{\footnotesize{\textsf{\prune{2}}}}
%\ncline{S6}{S1}\nbput*[nrot=:D]{\footnotesize{\textsf{\prune{19}}}}\ncline{S6}{S7}\naput*{\footnotesize{\textsf{\prune{26}}}} \ncline{S6}{S5}\naput*{\footnotesize{\textsf{\prune{5}}}} \ncline{S6}{S8}\nbput*[nrot=:D]{\footnotesize{\textsf{\prune{13}}}}
%\ncline{S5}{S7}\naput*{\footnotesize{\textsf{\prune{18}}}} \ncline{S5}{S8}\nbput*[nrot=:D]{\footnotesize{\textsf{\prune{7}}}}
% \ncline{S8}{S1}\naput*{\footnotesize{\textsf{\prune{5}}}}
%\uput[u](S1){\small{\bleu{$A$}}}
%\uput[l](S2){\small{\bleu{$B$}}}
%\uput[l](S3){\small{\bleu{$C$}}}
%\uput[d](S4){\small{\bleu{$D$}}}
%\uput[d](S5){\small{\bleu{$H$}}}
%\uput[u](S6){\small{\bleu{$F$}}}
%\uput[r](S7){\small{\bleu{$E$}}}
%\uput[l](S8){\small{\bleu{$G$}}}
%\end{pspicture}
%\end{center}
%
% \bigskip

 \exo

 \medskip 

On considère le graphe suivant :

 \begin{center}
\scalebox{.7}{\psset{unit=1cm}
\begin{pspicture}(0,0)(12,6)
\newrgbcolor{bleu}{0.1 0.05 .5}
\psset{linewidth=1pt,linecolor=bleu}
\cnodeput(2.5,0){A}{\small {\bleu {A}}} \cnodeput(7.5,4){B}{\small {\bleu {B}}} \cnodeput(3.5,4.2){C}{\small {\bleu {C}}} \cnodeput(0,6){D}{\small {\bleu {D}}} \cnodeput(6.8,1.5){E} {\small {\bleu {E}}}\cnodeput(12,0){F}{\small {\bleu {F}}} \cnodeput(9.5,6){G}{\small {\bleu {G}}}  
\ncline{C}{E} \ncline{E}{B}\ncline{B}{A}\ncline{A}{F}\ncline{F}{G} \ncline{G}{C}\ncline{C}{A} \ncline{A}{D}\ncline{D}{G} \ncline{G}{B}\ncline{B}{F} \ncline{F}{E} 
\end{pspicture}}
\end{center}

\begin{enumerate}
\item Existe-t-il des chaînes de longueur 2 partant du sommet $A$ et aboutissant au sommet $C$ ? 
\item  Le graphe admet-il des chaînes eulériennes ? Si oui,  en préciser une. 
 
\item Le graphe pondéré ci-dessous, donne en minutes, les durées moyennes des parcours entre $A$ et $C$ en tenant compte des sens uniques.

   \begin{center}
\scalebox{.8}{\psset{unit=1cm}
\begin{pspicture}(0,0)(12,6)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{linewidth=1pt,linecolor=bleu, arrowscale=2}
\cnodeput(2.5,0){A}{\small {\bleu {A}}} \cnodeput(7.5,4){B}{\small {\bleu {B}}} \cnodeput(3.5,4.2){C}{\small {\bleu {C}}} \cnodeput(0,6){D}{\small {\bleu {D}}} \cnodeput(6.8,1.5){E} {\small {\bleu {E}}}\cnodeput(12,0){F}{\small {\bleu {F}}} \cnodeput(9.5,6){G}{\small {\bleu {G}}}

\ncline{->}{A}{B}\mput*{\footnotesize{\textsf{\prune 28}}}
\ncline{->}{A}{D}\mput*{\footnotesize{\textsf{\prune 19}}}
\ncline{->}{A}{F}\mput*{\footnotesize{\textsf{\prune 10}}}
\ncline{->}{B}{G}\mput*{\footnotesize{\textsf{\prune 7}}}
\ncline{->}{C}{A}\mput*{\footnotesize{\textsf{\prune 38}}}
\ncline{->}{D}{G}\mput*{\footnotesize{\textsf{\prune 18}}} 
\ncline{->}{E}{B}\mput*{\footnotesize{\textsf{\prune 6}}}
\ncline{->}{E}{C}\mput*{\footnotesize{\textsf{\prune 27}}}
\ncline{->}{F}{B}\mput*{\footnotesize{\textsf{\prune 19}}}
\ncline{->}{F}{E}\mput*{\footnotesize{\textsf{\prune 11}}}
\ncline{->}{F}{G}\mput*{\footnotesize{\textsf{\prune 27}}}
\ncline{->}{G}{C}\mput*{\footnotesize{\textsf{\prune 8}}}
\end{pspicture}}
\end{center}

Un automobiliste doit se rendre de $A$ à $C$. En utilisant un algorithme, déterminer  le trajet le plus rapide pour aller de $A$ à $C$. 

Le retour sera-t-il plus rapide que l'aller ?
\end{enumerate}

 \bigskip 

\exo

\medskip

Dans le graphe ci-dessous, les sommets représentent différentes zones de résidence ou d'activités d'un quartier. Une arête reliant deux de ces sommets indique l'existence d'une voie d'accès principale entre deux lieux correspondants.

\begin{center}
\scalebox{.8}{
\psset{unit=2cm}
\begin{pspicture}(0,-2)(5,0)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{linecolor=bleu,linewidth=0.5pt}
\rput(0,0){\rnode{A}{\psframebox{\footnotesize{\textsf{A}}}}}
\rput(0,-2){\rnode{B}{\psframebox{\footnotesize{\textsf{B}}}}}
\rput(1,-1){\rnode{P}{\psframebox[linewidth=0.75pt]{\footnotesize{\textsf{\textbf{P}}}}}}
\rput(2,-2){\rnode{D}{\psframebox{\footnotesize{\textsf{D}}}}}
\rput(4,-2){\rnode{F}{\psframebox{\footnotesize{\textsf{F}}}}}
\rput(3,-1){\rnode{G}{\psframebox{\footnotesize{\textsf{G}}}}}
\rput(5,-1){\rnode{H}{\psframebox[linewidth=0.75pt]{\footnotesize{\textsf{\textbf{H}}}}}}
\rput(4,0){\rnode{E}{\psframebox{\footnotesize{\textsf{E}}}}}
\rput(2,0){\rnode{C}{\psframebox{\footnotesize{\textsf{C}}}}}
\psset{linewidth=1pt}
\ncline{-}{B}{D}\mput*{\footnotesize{\textsf{\prune 4}}}
\ncline{-}{D}{F}\mput*{\footnotesize{\textsf{\prune 5}}}
\ncline{-}{F}{G}\mput*{\footnotesize{\textsf{\prune 8}}}
\ncline{-}{G}{C}\mput*{\footnotesize{\textsf{\prune 10}}}
\ncline{-}{C}{E}\mput*{\footnotesize{\textsf{\prune 11}}}
\ncline{-}{E}{H}\mput*{\footnotesize{\textsf{\prune 9}}}
\ncline{-}{H}{G}\mput*{\footnotesize{\textsf{\prune 10}}}
\ncline{-}{G}{D}\mput*{\footnotesize{\textsf{\prune 9}}}
\ncline{-}{D}{P}\mput*{\footnotesize{\textsf{\prune 12}}}
\ncline{-}{P}{C}\mput*{\footnotesize{\textsf{\prune 11}}}
\ncline{-}{C}{A}\mput*{\footnotesize{\textsf{\prune 7}}}
\ncline{-}{A}{P}\mput*{\footnotesize{\textsf{\prune 4}}}
\ncline{-}{P}{B}\mput*{\footnotesize{\textsf{\prune 6}}}
\ncline{-}{B}{A}\mput*{\footnotesize{\textsf{\prune 3}}}
\end{pspicture}}
\end{center}

\begin{enumerate}
\item Pour sa campagne électorale, un candidat  souhaite parcourir toutes les voies d'accès principales de ce quartier  sans emprunter plusieurs fois la même voie.
\begin{enumerate}
	\item Montrer qu'un tel parcours est possible.
	\item Un tel parcours est-il possible pour ce candidat en partant de sa permanence électorale située en $P$ ? si oui le donner, sinon proposer un parcours possible en partant d'un autre endroit.
\end{enumerate}
\item Un candidat aux élections municipales se trouve dans sa permanence située en zone $P$ quand on lui rappelle qu'il a un rendez-vous avec le responsable de l'hôpital situé en zone $H$.
\begin{enumerate}
	\item Quel est le nombre minimal de voies d'accès principales que ce candidat devra emprunter pour arriver à son rendez-vous ?
	\item Le poids des arêtes du graphe précédent donne, en minutes, les durées moyennes des trajets existants entre les différents lieux :
	
En précisant la méthode utilisée, déterminer le plus court chemin que ce candidat devra emprunter pour arriver à son rendez-vous.
	
Combien de temps faut-il prévoir pour effectuer ce trajet ?
\end{enumerate} 
\end{enumerate}

 \bigskip  
\exo

 \medskip 

On considère le graphe ci-dessous :

\begin{center}
\scalebox{.6}{\newrgbcolor{bleu}{0.1 0.05 .5}
\psset{xunit=2cm,yunit=1cm, linecolor=bleu,linewidth=1pt}
\begin{pspicture}(0,0)(6,6)
\cnodeput(0,0){A}{\bleu{\footnotesize{\textsf{A}}}}
\cnodeput(5,1){B}{\bleu{\footnotesize{\textsf{B}}}}
\cnodeput(6,0){C}{\bleu{\footnotesize{\textsf{C}}}}
\cnodeput(3,6){D}{\bleu{\footnotesize{\textsf{D}}}}
\cnodeput(4,2){E}{\bleu{\footnotesize{\textsf{E}}}}
\cnodeput(3,4){F}{\bleu{\footnotesize{\textsf{F}}}}
\cnodeput(2,2){G}{\bleu{\footnotesize{\textsf{G}}}}
\ncline{-}{A}{B} \ncline{-}{A}{C} \ncline{-}{A}{D} \ncline{-}{A}{G} \ncline{-}{B}{C} \ncline{-}{B}{D}  \ncline{-}{B}{E} \ncline{-}{C}{D} \ncline{-}{D}{E}  \ncline{-}{D}{G} \ncline{-}{E}{F} \ncline{-}{E}{G} \ncline{-}{F}{G}
\end{pspicture}}
\end{center}

\begin{enumerate}

\item On appelle $M$ la matrice associée à ce graphe, les sommets étant pris dans l'ordre alphabétique. 

Une des trois matrices $R$, $S$ ou $T$ est la matrice $M^3$.
	
	\begin{center}
	 $R = {\begin{pmatrix}
   4 & 2 & 2 & 3 & 3 & 4 & 1  \\
   2 & 4 & 2 & 3 & 1 & 1 & 3  \\
   2 & 2 & 3 & 2 & 2 & 0 & 2  \\
   3 & 3 & 2 & 5 & 2 & 2 & 2  \\
   3 & 1 & 2 & 2 & 4 & 1 & 2  \\
   1 & 1 & 0 & 2 & 1 & 2 & 1  \\
   1 & 4 & 2 & 2 & 2 & 1 & 4  \\
 \end{pmatrix} }$
 \hfill
 $S = \left( {\begin{array}{*{20}r}
   8 & 12 & 9 & 12 & 7 & 4 & 11 \\
   12 & 8 & 9 & 12 & 11 & 4 & 7 \\
   9 & 9 & 6 & 11 & 6 & 4 & 6 \\
   12 & 12 & 11 & 12 & 12 & 4 & 12 \\
   7 & 11 & 6 & 12 & 6 & 6 & 10 \\
   4 & 4 & 4 & 4 & 6 & 2 & 6 \\
   11 & 7 & 6 & 12 & 10 & 6 & 6 \\
\end{array} } \right)$
 \hfill
$T = {\begin{pmatrix}
   4 & 1 & 2 & 2 & 3 & 4 & 1  \\
   2 & 4 & 2 & 3 & 1 & 2 & 3  \\
   1 & 2 & 3 & 2 & 2 & 1 & 2  \\
   3 & 3 & 2 & 6 & 3 & 2 & 3  \\
   2 & 1 & 2 & 3 & 4 & 2 & 2  \\
   2 & 2 & 1 & 2 & 2 & 3 & 2  \\
   2 & 3 & 2 & 3 & 2 & 2 & 4  \\
 \end{pmatrix} }$
	\end{center}
	
	Sans calculer la matrice $M^3$, indiquer quelle est la matrice $M^3$ en justifiant votre choix.
\item Ce graphe est-il complet ? Ce graphe est-il connexe ? 
\item Ce graphe admet-il une chaîne eulérienne ? Justifier la réponse. Si oui donner une telle chaîne. 

\item Un représentant, a modélisé à l'aide du graphe ci-dessous le réseau routier reliant différents clients notés A, B, C, D, E, F et G. Les arêtes sont pondérés par les distances en kilomètre à parcourir.

\begin{center}
	\newrgbcolor{bleu}{0.1 0.05 .5}
	
\scalebox{.8}{\psset{xunit=2cm,yunit=1cm, linecolor=bleu,linewidth=1pt}
\begin{pspicture}(0,0)(6,6.1)
\newrgbcolor{prune}{.6 0 .48}
\cnodeput(0,0){A}{\bleu{\footnotesize{\textsf{A}}}}
\cnodeput(5,1){B}{\bleu{\footnotesize{\textsf{B}}}}
\cnodeput(6,0){C}{\bleu{\footnotesize{\textsf{C}}}}
\cnodeput(3,6){D}{\bleu{\footnotesize{\textsf{D}}}}
\cnodeput(4,2){E}{\bleu{\footnotesize{\textsf{E}}}}
\cnodeput(3,4){F}{\bleu{\footnotesize{\textsf{F}}}}
\cnodeput(2,2){G}{\bleu{\footnotesize{\textsf{G}}}}
\ncline{-}{A}{B}\mput*{\prune{\textsf{30}}}
\ncline{-}{A}{C}\mput*{\prune{\textsf{35}}}
\ncline{-}{A}{D}\mput*{\prune{\textsf{9}}}
\ncline{-}{A}{G}\mput*{\prune{\textsf{8}}}
\ncline{-}{B}{C}\mput*{\prune{\textsf{6}}}
\ncline{-}{B}{D}\mput*{\prune{\textsf{38}}}
\ncline{-}{B}{E}\mput*{\prune{\textsf{8}}}
\ncline{-}{C}{D}\mput*{\prune{\textsf{43}}}
\ncline{-}{D}{E}\mput*{\prune{\textsf{29}}}
\ncline{-}{D}{G}\mput*{\prune{\textsf{18}}}
\ncline{-}{E}{F}\mput*{\prune{\textsf{6}}}
\ncline{-}{E}{G}\mput*{\prune{\textsf{11}}}
\ncline{-}{F}{G}\mput*{\prune{\textsf{5}}}
\end{pspicture}}
\end{center}

Après avoir visité le client C, ce représentant souhaite se rendre chez le client D.
\begin{enumerate}
\item En précisant la méthode utilisée, déterminer le trajet le plus court (en kilomètres) pour aller de C à D. Préciser la longueur en kilomètres de ce trajet. 
\item Existe-t-il un parcours de même distance permettant à ce représentant de visiter tous ses clients ? 
\end{enumerate}

\end{enumerate}

 \bigskip


  
\exo

 \medskip 
 
 \textsf{\textbf{{\textsc{partie a}}}}

On considère le graphe de sommets $A$, $B$, $C$, $D$, $E$ et $F$ dont la matrice associée est $ M= \begin{pmatrix}
0 & 1 & 1 & 1 & 0 & 0\\
1 & 0 & 0 & 1 & 1 & 1\\
1 & 0 & 0 & 1 & 0 & 1\\
1 & 1 & 1 & 0 & 0 & 1\\
0 & 1 & 0 & 0 & 0 & 1\\
0 & 1 & 1 & 1 & 1 & 0\\
 \end{pmatrix}$
 
 \begin{enumerate}
 \item Quel est le nombre d'arêtes de ce graphe ? 
\item Ce graphe est-il complet ? Ce graphe est-il connexe ? 
\item Ce graphe admet-il une chaîne eulérienne ? Justifier la réponse. Si oui donner une telle chaîne. 
\end{enumerate}
 
\medskip 
 
 \textsf{\textbf{{\textsc{partie b}}}}
 
  \medskip
  
  Après avoir chargé son camion à l'entrepôt noté $A$, un livreur  doit livrer cinq clients notés $B$, $C$, $D$, $E$ et $F$.
  
  Le graphe ci-dessous, modélise le réseau routier en tenant compte des sens de circulation et des temps de parcours en minutes.
 \begin{center}
 \scalebox{.8}{
 \psset{xunit=5cm,yunit=1.8cm}
\begin{pspicture}(0,-.4)(2,2.2)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{linewidth=1pt,linecolor=bleu,arrowscale=1.5}
\cnodeput(0,2){A}{\bleu \bf A}  \cnodeput(1,2){B}{\bleu \bf B}   \cnodeput(0,0){C}{\bleu \bf C}  \cnodeput(1,.75){D} {\bleu \bf D} \cnodeput(2,2){E}{\bleu \bf E}  \cnodeput(2,0){F} {\bleu \bf F} 
\ncarc[arcangle=15]{->}{B}{A}\mput*{\footnotesize{\textsf{\prune{32}}}}\ncarc[arcangle=15]{->}{A}{B}\mput*{\footnotesize{\textsf{\prune{32}}}} \ncarc[arcangle=15]{->}{B}{F} \mput*{\footnotesize{\textsf{\prune{16}}}} \ncarc[arcangle=-15]{->}{F}{E} \mput*{\footnotesize{\textsf{\prune{18}}}}  \ncarc[arcangle=-15]{->}{E}{F} \mput*{\footnotesize{\textsf{\prune{18}}}} \ncarc[arcangle=-15]{->}{E}{B} \mput*{\footnotesize{\textsf{\prune{24}}}}\ncarc[arcangle=-15]{->}{B}{D}  \mput*{\footnotesize{\textsf{\prune{8}}}}\ncarc[arcangle=-15]{->}{D}{B}  \mput*{\footnotesize{\textsf{\prune{8}}}}\ncarc[arcangle=15]{->}{D}{A}\mput*{\footnotesize{\textsf{\prune{16}}}} \ncarc[arcangle=-15]{->}{A}{C}\mput*{\footnotesize{\textsf{\prune{15}}}} \ncarc[arcangle=-15]{->}{C}{D}\mput*{\footnotesize{\textsf{\prune{7}}}}\ncarc[arcangle=-15]{->}{F}{D}\mput*{\footnotesize{\textsf{\prune{19}}}} \ncarc[arcangle=15]{->}{F}{C} \mput*{\footnotesize{\textsf{\prune{26}}}}
\end{pspicture}}
 \end{center}
 
 \begin{enumerate}
 \item Quel trajet permet de minimiser le temps de parcours pour effectuer les cinq livraisons ? 
\item Après avoir effectué ses livraisons, le livreur doit retourner l'entrepôt. Quel trajet lui permet de minimiser son temps de parcours pour le retour  ?

En ne tenant pas compte des arrêts nécessaires pour effectuer les livraisons, le trajet du retour est-il plus rapide que celui de l'aller ?
\end{enumerate}
 
 \bigskip 

\exo  

\medskip

 \textsf{\textsc{\textbf{partie a}}}

\medskip

Le graphe orienté ci-dessous modélise le plan de circulation des poids lourds entre différents villages d'une zone touristique.  Les arêtes sont pondérées par les distances entre deux villages, exprimées en kilomètres.

\begin{center}
\psset{xunit=6cm,yunit=1cm}
\begin{pspicture}(2,6)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{linewidth=1pt,linecolor=bleu, arrowscale=1.25}
\begin{footnotesize}
\cnodeput(1,6){A}{\bleu {A}} \cnodeput(0,4){B}{\bleu {B}} \cnodeput(1,4){C}{\bleu {C}} \cnodeput(2,4){D}{\bleu {D}} \cnodeput(2,1.5){E} {\bleu {E}}\cnodeput(1,0){F}{\bleu {F}} \cnodeput(0,1.5){G}{\bleu {G}} \cnodeput(1,2){H}{\bleu {H}}
\ncline{->}{A}{D}\ncput*{\textsf{\prune 20}} \ncline{->}{B}{A}\ncput*{\textsf{\prune 12}} \ncarc[arcangle=-12]{->}{B}{C}\ncput*{\textsf{\prune 18}} \ncarc[arcangle=-12]{->}{C}{B}\ncput*{\textsf{\prune 18}}\ncarc[arcangle=-12]{->}{C}{D}\ncput*{\textsf{\prune 15}} \ncarc[arcangle=-12]{->}{D}{C}\ncput*{\textsf{\prune 15}} \ncline{->}{D}{E}\ncput*{\textsf{\prune 9}} \ncline{->}{E}{F}\ncput*{\textsf{\prune 7}} \ncline{->}{F}{G}\ncput*{\textsf{\prune 8}} \ncline{->}{F}{H} \ncput*{\textsf{\prune 6}}\ncline{->}{G}{B}\ncput*{\textsf{\prune 10}} \ncline{->}{H}{B}\ncput*{\textsf{\prune 10}}\ncline{->}{H}{D}\ncput*{\textsf{\prune 16}}
\end{footnotesize}
\end{pspicture}
\end{center}

Un fournisseur dont le dépôt est situé dans le village D doit effectuer une livraison de produits frais, en camion frigorifique, à un client du village B.

\medskip

À l'aide d'un algorithme, déterminer l'itinéraire le plus court entre les villages D et B. Quelle est la distance parcourue ?

\medskip

 \textsf{\textsc{\textbf{partie b}}}

\medskip

Une agence de voyage propose un circuit touristique pour visiter les trois villages A, B et C. Le client peut choisir la durée du séjour dans chaque village. 

L'agence distingue deux périodes, la haute et la basse saison, et différencie ses tarifs selon la période.

Les tarifs dans les différents villages, en euro par personne et par jour, sont donnés dans le tableau suivant.

\begin{center}
\begin{tabularx}{.8\linewidth}{|l|*{3}{>{\centering \arraybackslash}X|}}\cline{2-4}
\multicolumn{1}{l|}{}&Village A &Village B &Village C\\ \hline
Nombre de jours& 1 &1 &1\\ \hline
Tarif haute saison &160 &220 &140\\ \hline
Tarif basse saison &130 &180 &110\\ \hline
\end{tabularx}
\end{center}

On note $P$ la matrice $\begin{pmatrix}
1&1&1\\160&220&140\\130&180&110\end{pmatrix}$.

\medskip

 Un client souhaite effectuer un circuit qui comprend quatre jours dans le village A, six jours dans le village B et deux jours dans le village C. On associe à ce choix la matrice $S = \begin{pmatrix}4\\6\\2\end{pmatrix}$.
	\begin{enumerate}
		\item Calculer le produit matriciel $P \times S$. Que représentent les termes de la matrice obtenue ?
		\item Ce client dispose d'un budget de \np{2000}~\euro. Pourra-t-il réaliser son voyage ?
	\end{enumerate}
	
\medskip

 \textsf{\textsc{\textbf{partie c}}}

\medskip

Dans le village C se trouve un camping dont le plan est schématisé par le graphe ci-dessous. 

Les arêtes sont les allées du camping et les sommets les carrefours.

\medskip

\begin{center}
 \scalebox{.8}{
\psset{xunit=2.4cm,yunit=.6cm}
\begin{pspicture}(5,6)
\newrgbcolor{bleu}{0.1 0.05 .5}
\psset{linecolor=bleu,linewidth=1pt}
\begin{footnotesize}
\cnodeput(0,3){1}{\bleu {1}} \cnodeput(.5,0){2}{\bleu {2}} \cnodeput(2,0){3}{\bleu {3}} \cnodeput(3.5,0){4}{\bleu {4}} \cnodeput(3.5,2){5} {\bleu {5}}\cnodeput(5,2){6}{\bleu {6}} \cnodeput(5,4){7}{\bleu {7}} \cnodeput(3.5,4){8}{\bleu {8}}\cnodeput(4.5,6){9}{\bleu {9}}\cnodeput(3.25,6){10}{\bleu {10}}\cnodeput(1.5,3){11}{\bleu {11}}\cnodeput(2,6){12}{\bleu {12}}\cnodeput(.5,6){13}{\bleu {13}}
\end{footnotesize}
\ncline{1}{3}\ncline{3}{11}\ncline{11}{5}\ncline{5}{8}\ncline{8}{10}\ncline{10}{12}\ncline{12}{1}\ncline{1}{13}\ncline{13}{12}\ncline{12}{11}\ncline{11}{10}\ncline{10}{9}\ncline{9}{8}\ncline{8}{7}\ncline{7}{6}\ncline{6}{5}\ncline{5}{4}\ncline{4}{3}\ncline{3}{2}\ncline{2}{1}
\end{pspicture}
}
\end{center}


Afin d'optimiser le nettoyage des allées, le gestionnaire du camping souhaite établir un parcours qui passe une seule fois par chaque allée.

Un tel parcours est-il possible ?
\end{document}

