\documentclass[10pt] {article} \usepackage[T1]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,graphicx,multicol,mathrsfs, fancyhdr,enumerate,fourier,eurosym,alterqcm,enumerate,tabularx,variations,numprint,systeme}
\usepackage[normalem]{ulem}
\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 17cm \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}
%\tableofcontents

\begin{center}\section*{\textcolor{red}{Correction de l'exercice de spécialité}}\end{center}

La coopérative LAFRUITIERE collecte le lait de 7 exploitations de montagne. La situation géographique est représentée par le graphe ci-dessous, noté $G_L$. La coopérative est située au sommet A, les autres sommets B, C, D, E, F, G et H représentent les différentes exploitations; les arêtes représentent le réseau routier reliant ces exploitations.

\begin{center}
\psset{unit=0.5cm}
\begin{pspicture}(12,8)
\rput(0.75,7.5){\ovalnode{A}{\red \bf A}} \rput(7.2,7.5){\ovalnode{B}{B}} \rput(11.3,5.5){\ovalnode{C}{C}} 
\rput(10.3,2){\ovalnode{D}{D}} 
\rput(3.3,6.4){\ovalnode{E}{E}} \rput(0.3,2.7){\ovalnode{F}{F}} \rput(5.7,0.3){\ovalnode{G}{G}} \rput(6.7,4.3){\ovalnode{H}{H}} 
\ncline{A}{B} \ncline{A}{E} \ncline{A}{F} 
\ncline{B}{C} \ncline{B}{D} \ncline{B}{E} 
\ncline{B}{H} \ncline{C}{D} \ncline{D}{F} 
\ncline{D}{G} \ncline{D}{H} \ncline{E}{F} 
\ncline{E}{H} \ncline{F}{G} \ncline{F}{H} 
\end{pspicture}
\end{center}

%\medskip

\subsubsection*{\textcolor{red}{Partie A}}

%\medskip

\begin{enumerate}
\item 

	\begin{enumerate}

		\item% Le graphe $G_L$ est-il complet ? Justifier.
Un graphe est complet si chaque sommet est relié à tous les autres.

Dans le graphe $G_L$, le sommet A n'est pas relié au sommet G, donc le graphe $G_L$ n'est pas complet.\marginpar{0,5 pt}

		\item%  Le graphe $G_L$ est-il connexe ? Justifier.
Un graphe est connexe si deux sommets quelconques sont reliés par au moins une chaîne.

Le chemin A -- B -- C -- D -- H -- E -- F -- G relie tous les sommets entre eux, donc le graphe $G_L$ est connexe.\marginpar{0,5 pt}

	\end{enumerate}

\item% Est-il possible d'organiser une tournée de toutes les exploitations en partant de A et en terminant en A et en passant au moins une fois par chaque client, tout en empruntant une fois et une seule chaque route ? Justifier la réponse.
Organiser une tournée de toutes les exploitations en partant de A et en terminant en A et en passant au moins une fois par chaque client, tout en empruntant une fois et une seule chaque route, c'est chercher un cycle eulérien dans ce graphe.

Un graphe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair; or le degré de A (nombre d'arêtes sortant de A) est 3, donc ce graphe ne contient pas de cycle eulérien.

Donc on ne peut pas organiser une tournée de toutes les exploitations en partant de A et en terminant en A et en passant au moins une fois par chaque client, tout en empruntant une fois et une seule chaque route.\marginpar{0,75 pt}

\item On appelle $M$ la matrice d'adjacence associée au graphe $G_L$ (les sommets étant pris dans l'ordre alphabétique).
	
On donne la matrice $M^3 = \begin{pmatrix}
4 	&11 &3 &7 	&8 	&11 &3 &\boxed{\textcolor{red}{6}}\\
11 &8 	&7 &13 	&12 &8 	&6 &13\\
3 	&7 	&2 &7 	&5 	&6 	&2 &4\\
7	&13 &7 &8 	&8 	&13 &7 &12\\
8	&12 &5 &8 	&8 	&12 &5 &11\\
11 	&8 	&6 &13 	&12 &8 	&7 &13\\
3 	&6 	&2 &7 	&5 	&7 	&2 &4\\
6 	&13 &4 &12 	&11 &13 &4 &8
\end{pmatrix}$

%Déterminer, en justifiant, 

Le nombre de chemins de longueur 3 reliant A à H est le coefficient de la matrice $M^3$ situé sur la 1\iere{} ligne (pour A) et la 8\ieme{} colonne (pour H), c'est-à-dire 6.

Il y a donc 6 chemins de longueur 3 reliant A à H.

Ce sont:
AFEH -- AEFH -- ABEH -- AEBH -- AFDH -- ABDH\marginpar{0,75 pt}

%Indiquer ces chemins.
\end{enumerate}


\newpage


\subsubsection*{\textcolor{red}{Partie B}}

%\medskip

Les arêtes sont pondérées par les distances entre les exploitations, exprimées en kilomètres. La coopérative doit collecter du lait provenant de l'exploitation D.

\medskip

\begin{center}
\psset{unit=0.4cm}
\begin{pspicture}(12,8)
\cnodeput(0.75,7.5){A}{A} \cnodeput(7.2,7.5){B}{B} \cnodeput(11.3,5.5){C}{C} 
\cnodeput(10.3,2){D}{D} \cnodeput(3.3,6.4){E}{E} \cnodeput(0.3,2.7){F}{F} 
\cnodeput(5.7,0.3){G}{G} \cnodeput(6.7,4.3){H}{H} 
\ncline{A}{B}\ncput*{19} \ncline{A}{E}\ncput*{6}  \ncline{A}{F}\ncput*{10} 
\ncline{B}{C}\ncput*{13} \ncline{B}{D}\ncput*{20} \ncline{B}{E}\ncput*{7} 
\ncline{B}{H}\ncput*{7}  \ncline{C}{D}\ncput*{6}  \ncline{D}{F}\ncput*{25} 
\ncline{D}{G}\ncput*{15} \ncline{D}{H}\ncput*{13} \ncline{E}{F}\ncput*{5} 
\ncline{E}{H}\ncput*{14} \ncline{F}{G}\ncput*{12} \ncline{F}{H}\ncput*{8} 
\end{pspicture}
\end{center}

\medskip

L'algorithme de Dijkstra permet de déterminer les plus courts chemins partant du sommet A vers tous les autres sommets:

\medskip

\begin{center}
{\renewcommand{\arraystretch}{1.3}
\newcommand{\sur}[1]{\fcolorbox{yellow}{yellow}{#1}}
\begin{tabular}{|*{10}{c|}}
\hline 
\  A\   &  B  &  C  &  D  &  E   &   F   &   G   &   H    & {On garde} &Coefficient\\ 
\hline
\sur 0 & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ &  A&0\\
\hline 
 & 19 A & $\infty$ & $\infty$ & \sur{6 A} & 10 A & $\infty$ & $\infty$ &  E &6 \\
\hline
 & \sout{19 A} &          &          &  & \sur{10 A}  &          &  &   \\[-3pt]
 & 13 E        & $\infty$ & $\infty$ &  & \sout{11 E} & $\infty$ & 20 E &  F&10 \\ 
\hline
 & \sur{13 E} &          &      &  &   &      & \sout{20 E} &   \\[-3pt]
 &            & $\infty$ & 35 F &  &   & 22 F &   18 F      &  B &13 \\ 
\hline
 &  &      & \sout{35 F}&  &   & 22 F & \sur{18 F}  &   \\[-3pt]
 &  & 26 B & 33 B       &  &   &      & \sout{20 B} &  H& 18 \\ 
\hline
 &  & 26 B & \sout{33 B} &  &   & \sur{22 F} &   &   \\[-3pt]
 &  &      &  31 H       &  &   &            &   &  G &22 \\ 
\hline
 &  & \sur{26 B} &  31 H       &  &   &  &   &   \\[-3pt]
 &  &            & \sout{37 G} &  &   &  &   &  C &26 \\ 
\hline
 &  &            &  \sur{31 H}       &  &   &  &   &   \\[-3pt]
 &  &            & \sout{32 C} &  &   &  &   &  D&31 \\ 
\hline
\end{tabular} }
\end{center} 


Le chemin le plus court pour aller de A vers D est de longueur 31:
A $\stackrel{10}{\longrightarrow}$ 
F $\stackrel{8}{\longrightarrow}$ 
H $\stackrel{13}{\longrightarrow}$ D\marginpar{1 pt}

\subsubsection*{\textcolor{red}{Partie C}}
On considère le système :  S : \systeme{a+b+c=-2,-4a+b=0,9a+3b+c=3}\\

\begin{enumerate}
\item Ce système s'écrit matricielle ment : $A\times X=B$ où $A$, $X$ et $B$ sont les matrices :\\
$\begin{pmatrix}1&1&1\\-4&1&0\\9&3&1\end{pmatrix}$, $X=\begin{pmatrix}a\\b\\c\end{pmatrix}$ et $B=\begin{pmatrix}-2\\0\\0\end{pmatrix}$.\\
On calcule à la machine $A^{-1}$ ; alors, en multipliant par $A^{-1}$, on trouve :\\
$A^{-1}\times A\times X=A^{-1}\times B$ d'où $X=A^{-1}\times B$.\\
On trouve $a=0,125$~;~b=0,5~;~$c=-2,625$ donc $\boxed{\textcolor{red}{\mathscr{S}=\{(0,125~;~-0,5~;~2,625)\}}}$.\marginpar{0,75 pt}

\item $f$ est une fonction du second degré donc $f(x)=ax^2+bx+c$.\\
$A(1~;~2)\in\mathscr{C}\Leftrightarrow f(1)=2\Leftrightarrow a+b+c=2$.\\
$\mathscr{C}$ coupe l'ex des abscisses en 3, donc $f(3)=0$ d'où $9a+3b+c=0$.\\
La tangente $T$ à $\mathscr{C}$ en -2 est parallèle à l'axe des abscisses, donc $f'(-2)=0$.\\
Or $f'(x)=2ax+b$ donc $f'(-2)=0\Leftrightarrow -4a+b=0$.\\
$a$, $b$ et $c$ sont donc solutions du système précédent.\\
On en déduit que $\boxed{\textcolor{red}{f(x)=0,125x^2+0,5x-2,625}}$.\\
Remarque : $\boxed{\textcolor{red}{f(x)=\dfrac{1}{8}x^2+\dfrac{1}{2}x-\dfrac{21}{8}}}$\marginpar{0,75 pt}\end{enumerate}



\label{fin}
\end{document}  