\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 25cm \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{fancy}
% pour le pied de page central
\cfoot{Page \thepage/\pageref{fin}}

\begin{document}
%\tableofcontents

\begin{center}\section*{\textcolor{red}{Exercices de bac (graphes) (3)}}\end{center}





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

\subsection{\textcolor{blue}{Centres étrangers juin 2016}}
Une compagnie aérienne utilise huit aéroports que l'on nomme A, B, C, D, E, F, G et H.

Entre certains de ces aéroports, la compagnie propose des vols dans les deux sens.

Cette situation est représentée par le graphe $\Gamma$ ci-contre, dans
lequel :

\setlength\parindent{8mm}
\begin{enumerate}
\item[$\bullet~~$] les sommets représentent les aéroports,
\item[$\bullet~~$] les arêtes représentent les liaisons assurées dans les deux
sens par la compagnie.
\end{enumerate}

\begin{center}
\psset{unit=1cm}
\begin{pspicture}(7,6)
\cnodeput(0.4,3.6){A}{A}\cnodeput(2,4){B}{B}
\cnodeput(4.5,3.5){C}{C}\cnodeput(3.4,2){D}{D}
\cnodeput(1,1){E}{E}\cnodeput(6,4.6){F}{F}
\cnodeput(6,2.6){G}{G}\cnodeput(4.8,0.6){H}{H}
\ncline{A}{B}\ncline{A}{D}\ncline{A}{E}
\ncline{B}{C}\ncline{D}{B}\ncline{B}{F}
\ncline{C}{D}\ncline{C}{G}\ncline{D}{E}
\ncline{F}{G}\ncline{G}{H}\ncline{E}{H}
\end{pspicture}

\end{center}

\medskip

\textbf{Partie A}

\medskip

\begin{enumerate}
\item 
	\begin{enumerate}
		\item Déterminer, en justifiant, si le graphe $\Gamma$ est complet. 
		\item Déterminer, en justifiant, si le graphe $\Gamma$ est connexe.
	\end{enumerate}
\item Déterminer, en justifiant, si le graphe $\Gamma$ admet une chaîne eulérienne. Si oui, donner une
telle chaîne.\index{chaîne eulérienne}
\item Donner la matrice d'adjacence $M$ du graphe $\Gamma$ en respectant l'ordre alphabétique des
sommets du graphe.\index{matrice}
\item Pour la suite de l'exercice, on donne les matrices suivantes : 
 
\[M^2= \begin{pmatrix}3&1& 2& 2& 1& 1& 0& 1\\
	1 &4 &1 &2 &2 &0 &2 &0\\
	2 &1 &3 &1 &1 &2 &0 &1\\
2 &2 &1 &4 &1 &1 &1 &1\\
1&2&1&1&3&0&1&0\\
1 &0 &2 &1 &0 &2 &0 &1\\
0 &2 &0 &1 &1 &0&3&0\\ 
1 &0 &1 &1 &0 &1 &0&2\end{pmatrix}\]
et \[M^3 = \begin{pmatrix}
 4 &8 &3 &7 &6 &1 &4 &1\\
 8 &4 &8 &8 &3 &6 & 1 & 4\\
 3 &8 &2 &7 &4 &1 &6 &1\\
7 &8 &7 &6 &7 &3 &3 &2\\
6 &3 &4 &7 &2 &3& 1 &4\\
1& 6 &1 &3 &3 &0 &5 &0\\
4 &1 &6&3 &1 &5 &0& 4\\
1 &4 &1 &2 &4 &0 &4 &0\end{pmatrix}\]

Un voyageur souhaite aller de l'aéroport B à l'aéroport H.
	\begin{enumerate}
		\item Déterminer le nombre minimal de vols qu'il doit prendre, Justifier les réponses à l'aide
des matrices données ci-dessus.
		\item Donner tous les trajets possibles empruntant trois vols successifs.
	\end{enumerate}
\end{enumerate}

\bigskip

\textbf{Partie B}

\medskip

Les arêtes sont maintenant pondérées par le coût de chaque vol, exprimé en euros.
\[\psset{unit=1.3cm}
\begin{pspicture}(7,6)
\cnodeput(0.4,3.6){A}{A}\cnodeput(2,4){B}{B}
\cnodeput(4.5,3.5){C}{C}\cnodeput(3.4,2){D}{D}
\cnodeput(1,1){E}{E}\cnodeput(6,4.6){F}{F}
\cnodeput(6,2.6){G}{G}\cnodeput(4.8,0.6){H}{H}
\ncline{A}{B}\ncput*[nrot=:U]{40}\ncline{A}{D}\ncput*[nrot=:U]{100}\ncline{A}{E}\ncput*[nrot=:U]{45}
\ncline{B}{C}\ncput*[nrot=:U]{110}\ncline{B}{D}\ncput*[nrot=:U]{50}\ncline{B}{F}\ncput*[nrot=:U]{120}
\ncline{D}{C}\ncput*[nrot=:U]{60}\ncline{C}{G}\ncput*[nrot=:U]{50}\ncline{E}{D}\ncput*[nrot=:U]{40}
\ncline{F}{G}\ncput*[nrot=:U]{55}\ncline{H}{G}\ncput*[nrot=:U]{80}\ncline{E}{H}\ncput*[nrot=:U]{90}
\end{pspicture}\]

Un voyageur partant de l'aéroport A doit se rendre à l'aéroport G.\\
En utilisant l'algorithme de Dijkstra, déterminer le trajet le moins cher.



\newpage


\subsection{\textcolor{blue}{Asie juin 2016}}
\subsubsection*{\textsc{Partie A}}On considère le graphe $\mathcal G$ ci-dessous\index{graphe}

\begin{center}
\psset{xunit=0.8cm,yunit=0.8cm}
\begin{pspicture}(-1,-3)(11,3)
%%% ligne du milieu
\cnodeput(0,0){A}{$A$} \cnodeput(2.5,0){C}{$C$} \cnodeput(5,0){F}{$F$}
\cnodeput(7.5,0){I}{$I$} \cnodeput(10,0){K}{$K$}
%%% ligne du bas
\cnodeput(2.5,-2.5){B}{$B$} \cnodeput(5,-2.5){E}{$E$} \cnodeput(7.5,-2.5){H}{$H$}
%%% ligne du haut
\cnodeput(2.5,2.5){D}{$D$} \cnodeput(5,2.5){G}{$G$} \cnodeput(7.5,2.5){J}{$J$}
%%% arêtes
\ncline{A}{B} \ncline{A}{C} \ncline{A}{D}
\ncline{C}{E} \ncline{C}{F} \ncline{C}{G} 
\ncline{F}{H} \ncline{F}{I} \ncline{F}{J}
\ncline{B}{E} \ncline{B}{F}
\ncline{D}{F} \ncline{D}{G}
\ncline{E}{I} \ncline{E}{H}
\ncline{H}{K} \ncline{I}{K} \ncline{J}{K}
\ncline{G}{J} 
\end{pspicture}
\end{center}

\begin{enumerate}
\item En justifiant la réponse, dire si ce graphe admet une chaîne eulérienne.\index{chaîne eulérienne} 

Si oui, donner une telle chaîne.

\item On considère la matrice $M$ ci-après ($a$, $b$, $c$ et $d$ sont des nombres réels).\index{matrice}


\[M=
\left(
\begin{array}{*{11}{c}}
0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 
1 & 0 & 0 & a & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 1 & b & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & c & 1 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & d & 0 & 0 & 1 & 1 & 1 & 0 
\end{array}
\right)
\]

\begin{enumerate}
\item Déterminer les réels $a$, $b$, $c$ et $d$ pour que la matrice $M$ représente la matrice d'adjacence associée au graphe $\mathcal G$, les sommets étant pris dans l'ordre alphabétique.

\columnbreak

\item On donne
\footnotesize
\[
M^3=
\left(
\begin{array}{ccccccccccc}
0 & 8 & 10 & 8 & 0 & 0 & 0 & 5 & 5 & 5 & 0 \\ 
8 & 0 & 0 & 0 & 10 & 13 & 6 & 0 & 0 & 0 & 5 \\ 
10 & 0 & 0 & 0 & 11 & 16 & 9 & 0 & 0 & 0 & 6 \\ 
8 & 0 & 0 & 0 & 7 & 12 & 8 & 0 & 0 & 0 & 4 \\ 
0 & 10 & 11 & 7 & 0 & 0 & 0 & 10 & 10 & 7 & 0 \\ 
0 & 13 & 16 & 12 & 0 & 0 & 0 & 13 & 13 & 12 & 0 \\ 
0 & 6 & 9 & 8 & 0 & 0 & 0 & 5 & 5 & 7 & 0 \\ 
5 & 0 & 0 & 0 & 10 & 13 & 5 & 0 & 0 & 0 & 8 \\ 
5 & 0 & 0 & 0 & 10 & 13 & 5 & 0 & 0 & 0 & 8 \\ 
5 & 0 & 0 & 0 & 7 & 12 & 7 & 0 & 0 & 0 & 7 \\ 
0 & 5 & 6 & 4 & 0 & 0 & 0 & 8 & 8 & 7 & 0
\end{array}
\right) 
\]
\normalsize

Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant $A$ à $J$. Préciser ces chemins.
\end{enumerate}
\end{enumerate}

\subsubsection*{\textsc{Partie B}}

On oriente et on pondère le graphe $\mathcal G$ ci-dessus pour qu'il représente un réseau d'irrigation. 

\begin{center}
\psset{xunit=0.8cm,yunit=0.8cm,arrowscale=1.5}
\begin{pspicture}(-1,-3)(11,3)
%%% ligne du milieu
\cnodeput(0,0){A}{$A$} \cnodeput(2.5,0){C}{$C$} \cnodeput(5,0){F}{$F$}
\cnodeput(7.5,0){I}{$I$} \cnodeput(10,0){K}{$K$}
%%% ligne du bas
\cnodeput(2.5,-2.5){B}{$B$} \cnodeput(5,-2.5){E}{$E$} \cnodeput(7.5,-2.5){H}{$H$}
%%% ligne du haut
\cnodeput(2.5,2.5){D}{$D$} \cnodeput(5,2.5){G}{$G$} \cnodeput(7.5,2.5){J}{$J$}
%%% arêtes
\ncline{->}{A}{B} \ncput*{2}
\ncline{->}{A}{C} \ncput*{5} 
\ncline{->}{A}{D} \ncput*{3}
\ncline{->}{C}{E} \ncput*[npos=0.75]{3}  
\ncline{->}{C}{F} \ncput*{2} 
\ncline{->}{C}{G} \ncput*[npos=0.75]{5}    
\ncline{->}{F}{H} \ncput*[npos=0.75]{3}   
\ncline{->}{F}{I} \ncput*{4} 
\ncline{->}{F}{J} \ncput*{5}
\ncline{->}{B}{E} \ncput*{6} 
\ncline{->}{B}{F} \ncput*[npos=0.75]{2}  
\ncline{->}{D}{F} \ncput*[npos=0.75]{4}   
\ncline{->}{D}{G} \ncput*{5}
\ncline{->}{E}{I} \ncput*[npos=0.75]{2}  
\ncline{->}{E}{H} \ncput*{1}
\ncline{->}{H}{K} \ncput*{2} 
\ncline{->}{I}{K} \ncput*{3} 
\ncline{->}{J}{K} \ncput*{3}
\ncline{->}{G}{J} \ncput*{5} 
\end{pspicture}
\end{center}

\begin{list}{\textbullet}{}
\item Le sommet $A$ correspond au départ d'eau, le sommet $K$ au bassin d'infiltration et les autres sommets représentent les stations de régulation.

\item Les arêtes représentent les canaux d'irrigation et les flèches, le sens du ruissellement. 

\item La pondération donne, en km, les distances entre les différentes stations du réseau.
\end{list}

Déterminer un chemin de longueur minimale entre le départ d'eau en $A$ et le bassin d'infiltration en $K$ et donner sa longueur.


\end{multicols}

\label{fin}
\end{document}  