\thumb

% QCM1

\begin{vf}{Graphe non orienté}{5}
Dire si chacune des affirmations suivantes est vraie ou fausse.

Le graphe $\mathcal{G}$ ci-dessous a pour sommets les points A,B,C,D et E.

\begin{center}
\includegraphics{011_ex1enonce-p301_074}
\end{center}
\begin{questions}
\item Le graphe $\mathcal{G}$ est d'ordre 5.
\item Le diamètre de $\mathcal{G}$ est 3.
\item $\mathcal{G}$ admet une chaîne eulérienne issue de D.
\item $\mathcal{G}$ admet un cycle eulérien.
\item La chaîne BCADCED est eulérienne.
\end{questions}
\end{vf}

%% CORR QCM1

\begin{corrige}
\begin{center}
\includegraphics{011_ex1corrige-p311_075}
\end{center}
\begin{questions}
\item Vrai. L'ordre d'un graphe est le nombre de sommets du graphe donc le graphe $\mathcal{G}$ est d'ordre 5.
\item Faux. Le diamètre d'un graphe est la plus grande des distances entre deux sommets quelconques du graphe.

On a : d(A,B)=1, d(A,C)=1, d(A,D)=1, d(A,E)=2, d(B,C)=1, d(B,D)=2,\\
d(B,E)=2, d(C,D)=1, d(C,E)=1 et d(D,E)=1.

Le diamètre du graphe est donc 2.

\item Vrai. Déterminons le degré de chacun des sommets.

\begin{center}
 \begin{tabularx}{\linewidth}{|L|*5{>{\centering\arraybackslash}X|}}
  \hline
    Sommet & A & B & C & D & E\\\hline
    Degré &  3 & 2 & 4 & 3 & 2\\\hline
 \end{tabularx}
\end{center}

Le graphe $\mathcal{G}$ est connexe, il a exactement deux sommets A et D de degré impair, il admet donc une chaîne eulérienne d'origine l'un de ces deux
sommets, donc $\mathcal{G}$ admet une chaîne eulérienne issue de D.

\item Faux. Le graphe $\mathcal{G}$ n'admet pas de cycle eulérien car il a des sommets de degré impair.

\item Faux. B n'est pas un des sommets de degré impair, la chaîne BCADCED n'est donc pas eulérienne.
\end{questions}

\begin{Remarque}vous pouviez aussi compter le nombre d'arêtes de la chaîne BCADCED. Il y a 6 arêtes alors que le graphe admet 7 arêtes, le nombre d'arêtes étant égal à la moitié de la somme des degrés des sommets du graphe.
\end{Remarque}
\end{corrige}

% QCM2

\begin{vf}{Matrice d'un graphe non orienté}{5}
Dire si chacune des affirmations suivantes est vraie ou fausse.

Les matrices $M$ et $M^3$ ci-dessous sont telles que $M$ soit la matrice associée à un graphe $\mathcal{G}$ non orienté de sommets A,B,C,D et E dans cet ordre :

\[
M= \begin{pmatrix}0&1&1&1&1\\1&0&1&0&0\\1&1&0&1&0\\1&0&1&0&0\\1&0&0&0&0\end{pmatrix} \qquad
 M^3=
\begin{pmatrix}4&6&6&6&4\\6&2&5&2&1\\6&5&4&5&2\\6&2&5&2&1\\4&1&2&1&0\end{pmatrix}
\]

\begin{questions}
\item Le graphe $\mathcal{G}$ a 12 arêtes.
\item Il y a 6 chaînes de longueur 3 reliant A à D.
\item Il n'y a pas de cycle de longueur 3.
\item Il est toujours possible de joindre deux points quelconques par une chaîne de longueur 3.
\item Il y a 16 chaînes de longueur 3 d'origine B.
\end{questions}
\end{vf}

%% CORR QCM2

\begin{corrige}
\begin{questions}
\item Faux. La matrice d'un graphe non orienté est symétrique ; le nombre de 1 est donc le double de celui des arêtes : le graphe comporte donc 6 arêtes.
\item Vrai. Le nombre situé à l'intersection de la 1\iere{} ligne et de la 4\ieme{} colonne de la matrice $M^3$ indique le nombre de chaînes de longueur 3 reliant A à D soit 6 chaînes de longueur 3 reliant A à D.
\item Faux. Il y a par exemple 4 cycles de longueur 3 reliant A à A car le nombre 4 figure à l'intersection de la 1\iere{} ligne et de la 1\iere{} colonne.
\item Faux. Il y a un 0 dans la matrice $M^3$, il n'est donc pas toujours possible de joindre deux points quelconques par une chaîne de longueur 3.
\begin{Remarque}il n'y a pas de cycle de longueur 3 reliant E à E.
\end{Remarque}
\item Vrai. Le nombre de chaînes de longueur 3 d'origine B est la somme des nombres situés sur la 2\ieme{} ligne de la matrice $M^3$.

Il y a donc $6+2+5+2+1=16$ chaînes de longueur 3 d'origine B.
\end{questions} 
\end{corrige}

% EX3

\begin{vf}{Graphe orienté}{5}
Dire si chacune des affirmations suivantes est vraie ou fausse.

Le graphe $\mathcal{G}$ suivant a pour sommets
les points A,B,C,D et E.

\begin{center}
\includegraphics{011_ex3enonce-p302_076}
\end{center}
\begin{questions}
\item La matrice associée à $\mathcal{G}$ est symétrique.
\item Il existe 2 chemins de longueur 3 reliant A à C.
\item Le chemin ADBC a pour poids 16.
\item Il n'existe pas de cycle de longueur 4 issu de A.
\item Le chemin de poids minimum reliant A à C a pour poids 7.
\end{questions}
\end{vf}

%% CORR EX3

\begin{corrige}
\begin{questions}
\item  Faux. La matrice associée au graphe $\mathcal{G}$ de sommets A, B, C, D et E dans cet ordre est :
\begin{center}
\includegraphics{011_ex3corrige-p312_077}
\end{center}

\item Vrai. On a $M^3=\begin{pmatrix}
1 & 2 & 2 & 2 & 2\\
1 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 0  &0\\
1 & 1 & 2 & 2 & 1\\
0 & 1 & 1 & 1 & 2
\end{pmatrix}$. 

Il y a donc bien deux chemins de longueur 3 allant de A à C.


\item Vrai. Le chemin ADBC a pour poids $7+1+8=16$.

\item Faux. $M^4=\begin{pmatrix}
2 & 3 & 4 & 3 & 3\\
0 & 1 & 1 & 1 & 2\\
0 & 0 & 0 & 0 & 0\\
2 & 3 & 3 & 2 & 2\\
1 & 1 & 2 & 2 & 1
\end{pmatrix}$. 

Il y a donc deux cycles de longueur 4 issus de A.


\item Faux. Pour déterminer le chemin de poids minimum reliant A à C, appliquons l'algorithme de Dijkstra (voir sur la page suivante).
\newpage
\begin{center}
\includegraphics{011_ex3corrige-p313_080}
\end{center}

Pour déterminer le chemin de poids minimum, on remonte le chemin\linebreak C${\rightarrow}$D${\rightarrow}$E${\rightarrow}$A (les points entourés), le chemin de poids minimum a pour poids 6, c'est le chemin AEDC.
\end{questions}
\end{corrige}

% ex4

\begin{vf}{Graphe probabiliste}{5}
Dire si chacune des affirmations suivantes est vraie ou fausse.

A et B sont deux événements complémentaires d'un univers (c'est-à-dire\linebreak $B=\bar{A}$). Soit $n$ un entier naturel.
\begin{itemize}
\item $a_n$ est la probabilité que l'événement A soit réalisé à l'étape $n$;
\item $b_n$ est la probabilité que l'événement B soit réalisé à l'étape $n$.
\end{itemize}
La matrice $P_n =\begin{pmatrix}a_n & b_n\end{pmatrix}$ traduit l'état probabiliste à l'étape $n$.

On a $P_0=\begin{pmatrix}1 & 0\end{pmatrix}$.

$M= \begin{pmatrix}0,8&0,2\\0,5&0,5\end{pmatrix}$ est la matrice de transition de l'étape $n$ à l'étape $n+1$.

On a $M^2=\begin{pmatrix}0,74 & 0,26 \\ 0,65 & 0,35\end{pmatrix}$.

La matrice $P=\begin{pmatrix} x & y\end{pmatrix}$ représente l'état stable associé à l'évolution.

\begin{questions}
\item Si A est réalisé à l'étape $n$, la probabilité que B soit réalisé à l'étape $n+1$ est égale à 0,5.
\item Si B est réalisé à l'étape $n$, la probabilité que A soit réalisé à l'étape $n+$1 est égale à 0,2.
\item $b_2=0,35$.
\item $x=0,8x+0,5y$.
\item À long terme, la probabilité que A soit réalisé est $\dfrac{5}{7}$.
\end{questions}
\end{vf}

%% CORR EX4

\begin{corrige}
\begin{questions}
\item Faux. Soit $M=\begin{pmatrix}0,8&0,2\\0,5&0,5\end{pmatrix}$ la matrice de transition.

La 1\iere{} ligne donne la probabilité sachant $A_n$:
\begin{itemize}
\item 0,8 indique la probabilité de $A_{n+1}$ sachant $A_n$.
\item 0,2 indique la probabilité de $B_{n+1}$ sachant $A_n$.
\end{itemize}
La 2\ieme{} ligne donne la probabilité sachant $B_n$ :
\begin{itemize}
\item  0,5 indique la probabilité de $A_{n+1}$ sachant $B_n$.
\item 0,5 indique la probabilité de $B_{n+1}$ sachant $B_n$.
\end{itemize}
La probabilité que B soit réalisé à l'étape $n+1$ sachant que A est réalisé à l'étape $n$ est donc égale à 0,2.

\item Faux. La probabilité que A soit réalisé à l'étape $n+1$ sachant que B est réalisé à l'étape $n$ est égale à 0,5.

\item Faux. On a
  ${P_{{2}}=\left(\begin{matrix}a_{{2}}&b_{{2}}\end{matrix}\right)=P_{{0}}\times
    M^{{2}}=\left(\begin{matrix}1&0\end{matrix}\right)\times
    \left(\begin{matrix}0,\text{74}&0,\text{26}\\0,\text{65}&0,\text{35}\end{matrix}\right)}$
  donc
  ${P_{{2}}=\left(\begin{matrix}0,\text{74}&0,\text{26}\end{matrix}\right)}$
  et $b_2=0,26$.

\item Vrai. La matrice $P$ qui représente l'état stable associé à l'évolution est telle que $P=P\times M$.
\begin{align*}
P=P\times M & \iff \begin{pmatrix}x&y\end{pmatrix}
=\begin{pmatrix}x&y\end{pmatrix}\times
\begin{pmatrix}0,8&0,2\\0,5&0,5\end{pmatrix}\\
& \iff \begin{pmatrix}x&y\end{pmatrix}=\begin{pmatrix}0,8x+0,5y&0,2x+0,5y\end{pmatrix}
\end{align*}
D'où $x=0,8x+0,5y$.

\item Vrai. $x$ et $y$ sont solutions du système :

${\left\{\begin{matrix}x=0,8x+0,5y\\x+y=1\end{matrix}\right.\Leftrightarrow
\left\{\begin{matrix}0,2x=0,5y\\x+y=1\end{matrix}\right.\Leftrightarrow
\left\{\begin{matrix}x=2,5y\\2,5y+y=1\end{matrix}\right.\Leftrightarrow
\left\{\begin{matrix}x=\dfrac{5}{7}\\[8pt]y=\dfrac{2}{7}\end{matrix}\right.}$

La matrice $M$ ne comportant pas de 0, l'état probabiliste à l'étape $n$ converge vers l'état stable $P$, cet état étant indépendant de l'état \mbox{initial $P_0$}.

Donc, à long terme, la probabilité que A soit réalisé est ${\dfrac{5}{7}}$.
\end{questions}
\end{corrige}

%% EX5 (new 2015)

\begin{vf}{Vocabulaire}{10}
On donne la matrice A d'un graphe $\mathcal{G}$ de sommets A, B, C, D et E, utilisés dans l'ordre alphabétique dans la matrice.
\[
A=\begin{pmatrix}
0 & 0 & 1 & 0 & 1\\
0 & 0 & 1 & 1 & 1\\
1 & 1 & 0 & 1 & 0\\
0 & 1 & 1 & 0 & 0\\
1 & 1 & 0 & 0 & 0
\end{pmatrix}.
\]
En utilisant uniquement la matrice, répondre par Vrai ou Faux aux affirmations suivantes en justifiant :
\begin{questions}
\item L'ordre du graphe est 5.
\item Le graphe $\mathcal{G}$ est non orienté.
\item Le graphe $\mathcal{G}$ comporte 12 arêtes.
\item Le sommet D est de degré 3.
\item Le graphe $\mathcal{G}$ admet une chaîne eulérienne.
\item Le graphe $\mathcal{G}$ admet un cycle eulérien.
\item Il y a 8 chemins de longueur 3 partant de B et arrivant à D.
\end{questions}
\end{vf}

%% CORR EX5

\begin{corrige}
\begin{questions}
\item Vrai puisqu'il y a 5 sommets.
\item Vrai car la matrice est symétrique par rapport à la diagonale des coefficients $a_{ii}$.
\item Faux. Il comporte 6 arêtes (il faut diviser le nombre de 1 par deux).
\item Faux, il y a seulement deux 1 dans la ligne 4.
\item Vrai. Il y a deux sommets de degré impair, B et C, donc le graphe admet bien une chaîne eulérienne.
\item Faux. Il aurait fallu qu'il n'y ait pas de sommet de degré impair.
\item Faux. On calcule : $A^3=\begin{pmatrix}
0 & 1 & 5 & 2 & 4\\
1 & 2 & 6 & 4 & 5\\
5 & 6 & 2 & 4 & 1\\
2 & 4 & 4 & 2 & 2\\
4 & 5 & 1 & 2 & 0
\end{pmatrix}$.

Il y a 4 chemins de longueur 3 partant de B pour arriver à D.
\end{questions}
\end{corrige}

% ex6

\sectionnn{Graphes non orientés}
\enlargethispage*{2em}
\begin{exo}{Propriétés}{Lyc\'ee Albert Schweitzer, Le Raincy}{1}{20} 
\begin{questions}
\item Les  graphes  ci-dessous sont-ils susceptibles de d\'ecrire la m\^eme
situation?
\begin{center}
\includegraphics{011_ex5enonce-p303_081} 
\end{center}

\item Le graphe $\mathcal{G}_2$ ci-dessus repr\'esente les rues d'un quartier d'une ville et les carrefours qui sont \`a leur intersection.
\begin{questions}
\item Comment sont repr\'esent\'es les rues et les carrefours dans  $\mathcal{G}_2$?
\item Calculer le degr\'e de chaque sommet de  $\mathcal{G}_2$.
\item Montrer qu'il existe un parcours dans la ville empruntant une fois et une seule chaque rue. Donner un tel parcours.
\end{questions}
\end{questions}
\end{exo}

% CORR EX6

\begin{corrige}
\begin{questions}
\item Les graphes ont tous les deux: 7 ar\^etes,  1 sommet de degr\'e 4, 2 sommets de degr\'e 3 et 2 sommets de degr\'e 2. Pour  qu'ils repr\'esentent la
m\^eme situation, ils faut apparier leurs ensembles de sommets et ensembles
d'ar\^etes.
Si on modifie les emplacements  des sommets $U$ et $Y$ dans la repr\'esentation de $\mathcal{G}_1$ (en \'echangeant les places)  on obtient un nouveau dessin (dessin 2).
Les dessins  $1$ et $2$ donnent deux repr\'esentations diff\'erentes du graphe
$\mathcal{G}_1$: dans les deux cas il y a le  m\^eme ensemble de sommets et le m\^eme
ensemble d'ar\^etes.
\Par
\hspace*{-1.5em}\includegraphics{011_ex5corrige-p315_082}
\Par
Gr\^ace au deuxi\`eme dessin, on voit  que les graphes $\mathcal{G}_1$ et  $\mathcal{G}_2$ sont isomorphes, c'est-\`a-dire qu'on peut renommer leurs sommets de fa\c{c}on \`a les rendre identiques. Par exemple:

\begin{center}
\begin{tabular}{|L|*5{Sc}|}
\hline
Num\'ero & 1 & 2& 3 &4 &5  \\
\hline
Sommet de $\mathcal{G}_2$ & A & B &C &D& E \\
\hline
Sommet de $\mathcal{G}_1$ & V & Y & U  & X & W\\
\hline
\end{tabular}
\end{center}

Avec  cette num\'erotation,  $\mathcal{G}_1$ et $\mathcal{G}_2$ ont la m\^eme matrice associ\'ee $M$ :

\begin{center}
\begin{tabular}{|L|*5{Sc}|}
\tabulartitle
\multicolumn{1}{l|}{\cellcolor{LG}}& \psline(-0.236,0.35)(3.265,0.35) V&Y&U& X&W \\ \hline
V& 0&1&1& 0&1\\
Y& 1&0&1&0&0 \\
U&1&1&0&1&1\\
X&0&0&1&0&1 \\
W&1&0&1&1&0\\
\hline
\end{tabular} 
\qquad
\begin{tabular}{|L|*5{Sc}|}
\tabulartitle
\multicolumn{1}{l|}{\cellcolor{LG}}& \psline(-0.236,0.36)(3.118,0.36) A&B&C& D&E \\ \hline
A& 0&1&1& 0&1\\
B&1&0&1&0&0 \\
C&1&1&0&1&1\\
D&0&0&1&0&1 \\
E&1&0&1&1&0\\
\hline
\end{tabular}
\end{center}

\begin{Remarques}
\begin{itemize}
\item Si on  ordonne les sommets de chaque graphe par ordre alphab\'etique, les  matrices sont diff\'erentes.
\item $\mathcal{G}_2$ est un graphe \og planaire\fg, c'est-\`a-dire qu'on peut le dessiner
de sorte que deux ar\^etes ne se croisent pas.
\end{itemize}
\end{Remarques}

\item \enlargethispage*{3em}
\begin{questions}
\item Une rue  est repr\'esent\'ee dans  $\mathcal{G}_2$ par une ar\^ete et un carrefour par un sommet.

\item Degr\'e de chaque sommet de $\mathcal{G}_2$:
\Par
\begin{center}
\begin{tabular}{|L|*5{Sc|}}
\hline
Sommet de $\mathcal{G}_2$ & A & B &C &D& E \\
\hline
Degr\'e & 3 & 2 & 4  & 2 & 3\\
\hline
\end{tabular}
\end{center}
\Par
\item Le parcours recherch\'e correspond \`a une cha\^ine eul\'erienne dans le graphe $\mathcal{G}_2$.
Or, $\mathcal{G}_2$ a exactement deux sommets de degr\'e impair, donc,  d'apr\`es le th\'eor\`eme d'Euler (théorème \ref{thm:11-euler}), il existe une solution.  Une cha\^ine eul\'erienne  a n\'ecessairement  pour
extr\'emit\'es les sommets de degr\'e impair, ici  A et E. Par exemple si l'on part de $A$, on a la cha\^ine eul\'erienne: (A,B,C,A,E,C,D,E).
\end{questions}
\end{questions}
\end{corrige}

% ex7

\begin{exo}{Cycle eulérien et chaîne eulérienne}{Lyc\'ee Galil\'ee, Gennevilliers}{1}{15}

Un voyageur  veut visiter les cinq pays d'Asie indiqu\'es sur le
sch\'ema ci-dessous.

\begin{minipage}{6cm}
\begin{questions}
\item  S'il  arrive et repart de Bangkok, peut-il visiter les cinq pays :
	\begin{questions}
	\item  sans passer deux fois par une m\^eme fronti\`ere ?
	\item  en traversant exactement une fois toutes les fronti\`eres ?
	\end{questions}

\item Reprendre la question 1 en rajoutant une fronti\`ere maritime entre la Thailande et la Chine  (travers\'ee par bateau).
\item Si le voyageur peut arriver dans un pays et repartir de n'importe quel autre, peut-il visiter les cinq pays, en passant une seule fois par toutes les fronti\`eres, et sans prendre le bateau ?
\end{questions}
\end{minipage}\hfill
\begin{minipage}{5cm}
\centering
\includegraphics{011_ex6enonce-p303_083}
\end{minipage}

\begin{tabularx}{\linewidth}{p{0.2em}X}
 & Sachant que les demandes de visas pour le Laos et le Vietnam doivent pr\'eciser le nombre d'entr\'ees dans le pays, que devra-t-il demander ?
\end{tabularx} 
\end{exo}

%% CORR EX7

\begin{corrige}
Commen\c{c}ons par dessiner le graphe de voisinage
entre pays : un sommet repr\'esente un pays ; deux sommets sont adjacents
s'ils ont une fronti\`ere terrestre commune.
Le graphe n'est pas orient\'e (les fronti\`eres se traversent dans les deux
sens).

\begin{center}
\includegraphics{011_ex6corrige-p316_084}
\end{center}
\begin{questions}
\item
\begin{questions}
\item\label{ch11ex7q1a} Sachant que Bangkok est en Thailande, on cherche un cycle
passant par tous les sommets - pays (on dit que c'est
\emph{un cycle hamiltonien}) et l'on obtient:
\begin{center}
(Thailande, Cambodge, Vietnam, Chine, Laos, Thailande)
\end{center}
On ne passe pas deux fois par la m\^eme ar\^ete (fronti\`ere)
donc ce cycle est une solution.

\item La question pos\'ee est celle d'un cycle eul\'erien: on doit passer par
toutes les ar\^etes (fronti\`eres) une fois et une seule. Or, on a deux sommets de degr\'e impair (Cambodge et Vietnam de degr\'e $3$).
D'apr\`es le th\'eor\`eme d'Euler (théorème \ref{thm:11-euler}), il n'existe donc aucun cycle eul\'erien.
\end{questions}

\item On rajoute une ar\^ete dans le graphe pr\'ec\'edent :
\begin{center}
\includegraphics{011_ex6corrige-p316_085}
\end{center}
\begin{questions}
\item La premi\`ere r\'eponse est-elle  modifi\'ee?
Non, car on n'a  pas chang\'e les sommets, donc le cycle  donné à la question \ref{ch11ex7q1a} est toujours solution.

\item Le degr\'e des sommets a chang\'e puisqu'on a une nouvelle ar\^ete. Malheureusement, on a $4$  sommets de degr\'e impair. Il n'y a toujours pas de cycle eul\'erien.
\end{questions}
\newpage
\item Il s'agit de trouver une cha\^ine eul\'erienne (points de d\'epart et
d'arriv\'ee diff\'erents).
Il y a exactement deux sommets de degr\'e impair, donc on sait qu'il en
existe une d'apr\`es le th\'eor\`eme d'Euler, et que ses
extr\'emit\'es sont n\'ecessairement les sommets de degr\'e impair.  On trouve par
exemple :
\begin{center}
\scalebox{0.95}{(Cambodge, Thailande, Laos, Cambodge, Vietnam, Chine, Laos, Vietnam).}
\end{center}
Cela fait deux entr\'ees au Laos et deux entr\'ees au Vietnam.
\end{questions}
\end{corrige}

%% EX8 (new 2015)

\begin{exo}{Transports interplanétaires}{Lycée Albert de Mun, Nogent-sur-Marne}{2}{25}
Nous sommes en 2951. Il existe un transport interplanétaire entre les planètes du système solaire que l'Homme a fini de coloniser depuis un siècle.
Des nefs spatiales assurent les liaisons régulières suivantes :
\begin{center}
Terre-Mercure ; Pluton-Vénus ; Terre-Pluton ; Pluton-Mercure ; Mercure-Vénus ; Uranus-Neptune ; Neptune-Saturne ; Saturne-Jupiter ; Jupiter-Mars ; Mars-Uranus.
\end{center}

\begin{questions}
\item Construire un graphe (non orienté car les liaisons existent dans les deux sens) représentant ces liaisons. Chaque sommet sera nommé à l'aide des deux premières lettres de la planète considérée.
\item Rappeler la définition d'un graphe connexe. Ce graphe est-il connexe ? Peut-on aller de la Terre vers Mars ?
\item La SITS (Société Interplanétaire des Transports Spatiaux) décide de réorganiser ses liaisons. Une liaison Pluton-Uranus est ajoutée, tandis que la ligne Mars-Uranus est abandonnée, faute d'une rentabilité suffisante. Par ailleurs une liaison Mars- Mercure est ajoutée.

Construire le nouveau graphe après cette réorganisation.
\item Ce graphe est-il connexe ? Peut-on désormais aller de la terre vers Mars ? Donner dans ce cas le chemin comportant le moins d'escales.
\item Préciser les degrés de tous les sommets et le nombre d'arêtes. Vérifier le théorème liant ces deux notions.
\item Existe-t-il un cycle eulérien qui permet d'effectuer le tour des planètes du système solaire à partir de la Terre ? Si oui, donner un tel cycle.
\item Les sommets du second graphe sont numérotés comme suit :

1 : Terre ; 2 : Mercure ; 3 : Mars ; 4 : Vénus ; 5 : Pluton ; 6 : Uranus ;\\
7 : Jupiter ; 8 : Neptune ; 9 : Saturne.

\Par

Donner la matrice $M$ associée à ce second graphe. Calculer $M²$. Que signifie l'élément $a_{25}$ de $M²$ ? Donner les chaînes correspondantes.
\end{questions}
\end{exo}

%% CORR EX8

\begin{corrige}
\begin{questions}
\item Un graphe possible est :
\begin{center}
\includegraphics{11_fig_01}
\end{center}

\item Un graphe est connexe s'il existe toujours une chaîne entre deux sommets distincts. 

Or, il est évident que ce graphe est composé de deux sous graphes disjoints. Donc, entre autre, on ne peut aller de la Terre à Mars.

\item Le nouveau graphe est :
\begin{center}
\includegraphics{11_fig_02}
\end{center}

\item Cette fois-ci le graphe est connexe.

Pour trouver le chemin le plus court, on étudie les différentes possibilités pour aller de la Terre à Mars : on ne peut pas y aller sans étape intermédiaire car il n'y a pas de liaison entre la Terre et Mars. En revanche, en passant par Mercure, on a rejoint Mars depuis la Terre en seulement deux trajets. Donc le chemin le plus court est Terre-Mercure-Mars.\enlargethispage*{3em}

\item \raisebox{-0.7em}{\begin{tabularx}{\linewidth}{|L|*9{>{\centering\arraybackslash}X|}}
\hline
Planète & Te & Me & Ma & Ve & Pl & Ur & Ju & Ne & Sa\\
\hline
Degré & 2 & 4 & 2 & 2 & 4 & 2 & 2 & 2 & 2\\
\hline
\end{tabularx}}

\Par

Il y a 11 arêtes, et la somme des degrés est 22, donc ceci correspond bien au théorème \ref{thm-somme-degres}.

\item D'après les degrés donnés par le tableau de la question 5, il n'y a pas de sommet de degré impair, donc d'après le théorème 3, il existe un cycle eulérien.

Pour trouver un tel cycle, on utilise l'algorithme d'Euler :

On peut commencer par exemple par le cycle : Te -- Me -- Pl -- Te.

Puis en partant de Mercure, on peut créer le cycle :
\begin{center}
Me -- Ma -- Ju -- Sa -- Ne -- Ur -- Pl -- Ve -- Me,
\end{center}
ce qui donne finalement :
\begin{center}
Te -- Me -- Ma -- Ju -- Sa -- Ne -- Ur -- Pl -- Ve -- Me -- Pl -- Te.
\end{center}
\Par
\item $M=\begin{pmatrix}
0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0
\end{pmatrix}$
\Par
$M^2 = \begin{pmatrix}
2 & 1 & 1 & 2 & 1 & 1 & 0 & 0 & 0\\
1 & 4 & 0 & 1 & 2 & 1 & 1 & 0 & 0\\
1 & 0 & 2 & 1 & 1 & 0 & 0 & 0 & 1\\
2 & 1 & 1 & 2 & 1 & 1 & 0 & 0 & 0\\
1 & 2 & 1 & 1 & 4 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 1 & 0 & 2 & 0 & 0 & 1\\
0 & 1 & 0 & 0 & 0 & 0 & 2 & 1 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 1 & 2 & 0\\
0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 2
\end{pmatrix}$.
\Par
$a_{25} = 2$ signifie qu'il y a deux chaînes de longueur 2 pour se rendre de Mercure à Pluton. Ces deux chaînes sont Mercure -- Terre -- Pluton et  Mercure --Vénus -- Pluton.
\end{questions}
\end{corrige}

% ex9

\begin{exo}{Raisonnement combinatoire}{Lyc\'ee Marie-Curie, Sceaux}{2}{30} 

On doit former des couples d'\'equipiers (pilote et copilote)
pour un rallye automobile de plusieurs jours.

\begin{center}
\begin{tabular}{|l|l|}
\hline\tabulartitle
Pilote  & Nation     \\
\hline
Paul & UK         \\
Brian &  US        \\
John & A        \\
Marl\`ene & F     \\
Charles & UK    \\
Olfa & B    \\
\hline
\end{tabular}
\qquad
\begin{tabular}{|l|l|}
\hline\tabulartitle
 Copilotes & Nation  \\
\hline
   Thomas & F  \\
  Karim & Ma  \\
   Victor & Ca  \\
  Eva &   US  \\
  Alain & B  \\
Fiona & Ca\\
\hline
\end{tabular}
\end{center}

Les nationalit\'es sont : Australie (A), Canada (Ca), France (F),
Grande Bretagne (UK), \'Etats Unis (US), Maroc (Ma) et Belgique (B).
Les marocains, les belges et les français sont uniquement francophones. Les canadiens sont anglophones et francophones, et les autres ne parlent qu'anglais.

\begin{questions}
\item  On veut que les \'equipiers  aient une  langue commune.
 Proposer une composition possible des \'equipes.

Quel nombre maximum d'\'equipes peut-on former ?

De combien de fa\c{c}ons diff\'erentes peut-on  former les \'equipes ?

\item  On d\'ecide de former les \'equipes ind\'ependamment du
crit\`ere des langues.
De combien de fa\c{c}ons diff\'erentes peut-on les s\'electionner ?
\end{questions}

\emph{Indications:}  Un graphe bien sûr, mais repr\'esent\'e par
le tableau donnant pour chaque sommet la liste de ses sommets
adjacents. Trouver une fa\c{c}on d'\'enum\'erer les choix
possibles en raisonnant avec le tableau.
\end{exo}

%% CORR EX9

\begin{corrige}
Cet exercice donne des exemples de raisonnement \og combinatoire\fg.
Il s'agit de d\'enombrer des choix possibles, en trouvant une strat\'egie pour
les compter car les choix sont trop nombreux pour \^etre \'enum\'er\'es explicitement.

L'exercice montre aussi que dessiner un graphe n'est pas toujours la panac\'ee,
et qu'il faut savoir exploiter d'autres modes de repr\'esentation d'un graphe,
en l'occurence le tableau des sommets adjacents par sommet.
\newpage
\begin{questions}
\item On trace un graphe \og bipartite\fg: d'un c\^ot\'e les sommets repr\'esentant
les pilotes, de l'autre les sommets repr\'esentant les copilotes; une ar\^ete va d'un
sommet pilote \`a un sommet copilote s'ils ont une langue commune.  En th\'eorie des graphes, le probl\`eme pos\'e ici est de trouver un
\emph{couplage maximal des sommets} (trouver un ensemble d'ar\^etes dont les
extr\'emit\'es recouvrent un nombre maximum de sommets).

\begin{center}
\includegraphics{011_ex7corrige-p317_086}
\end{center}

Ce graphe est plut\^ot embrouillé. Repr\'esentons les possibilit\'es de faire \'equipe sous forme de tableau.

\begin{center}
	\begin{tabular}{|Sl|Sl|}
	\hline\tabulartitle
	Pilotes & Copilotes\\
	\hline
	Paul & Victor, Eva, Fiona \\
	Brian &  Victor, Eva, Fiona   \\
	John &    Victor, Eva, Fiona \\
	Marl\`ene&  Thomas, Karim , Victor , Alain,  Fiona    \\
	Charles &  Victor, Eva, Fiona   \\
	Olfa &  Thomas, Karim , Victor , Alain,  Fiona    \\
	\hline
	\end{tabular}
\end{center}

Proc\'edons par ordre  :
\begin{itemize}
	\item  on affecte Paul \`a un copilote, par exemple Victor,
	puis on raye Victor partout dans la colonne des copilotes ;
	\item on affecte Brian \`a Eva  et on raye Eva ;
	\item on affecte alors John n\'ecessairement \`a Fiona,
	puis Marl\`ene \`a Thomas ;
	\item pour Charles, plus aucun copilote anglophone n'est libre.
\end{itemize}
On obtient ainsi cinq \'equipes avec deux \'equipiers non affect\'es:

\begin{center}
(Paul, Victor), (Brian, Eva), (John, Fiona),
(Marl\`ene, Thomas),\\ (Olfa , Karim).
\end{center}

\emph{Aurait-on pu former davantage d'\'equipes?}

En parcourant diff\'eremment les sommets pilotes et en modifiant les choix
des copilotes, on constate que non.
En commen\c{c}ant par les pilotes de degr\'e 5 on obtient par exemple :

\begin{center}
(Marl\`ene , Victor), (Olfa ,  Fiona) et (Paul , Eva)
\end{center}

et il restera trois pilotes sans \'equipier.
Intuitivement, on con\c{c}oit que pour trouver un maximum d'\'equipes, on a int\'er\^et
\`a affecter en premier les pilotes les moins sociables (c'est-\`a-dire de degr\'e
le plus petit).

\begin{Remarque}l'algorithme pr\'esent\'e ici permet de trouver  un couplage maximal des sommets
si l'on examine les sommets par ordre  de degr\'e croissant. (Graphes, Claude
Berge, Dunod 1970).
\end{Remarque}

\emph{D\'enombrons toutes les affectations possibles:}

Il n'y que trois copilotes anglophones pour quatre pilotes anglophones
donc un  pilote ne pourra pas courir et il y a quatre fa\c{c}ons de le choisir.
Supposons qu'il s'agisse de Charles :
\begin{itemize}
\item  Paul  a alors le choix entre trois copilotes ;
\item Brian a ensuite le choix entre deux copilotes
(l'un n'\'etant plus libre car affect\'e \`a Paul) ;
\item  Le troisi\`eme pilote John n'a plus qu'un seul choix.
\end{itemize}

Le pilote exclu \'etant choisi, il y a donc $(3\times 2\times1)=6$ choix pour
les \'equipes anglophones.
Or il y quatre choix possibles pour exclure un pilote anglophone,
il y a donc en tout $4\times 6 =24$ fa\c{c}ons de former les trois \'equipes
anglophones.

Pour les \'equipes francophones, les deux pilotes francophones choisissent parmi
trois copilotes : on a $3\times2=6$ choix d'\'equipes diff\'erentes.

Les choix des \'equipes anglophones et francophones se multiplient
(car ils sont ind\'ependants)  : on obtient $144$ fa\c{c}ons possibles
de former les cinq \'equipes.

\item Tous les liens entre  pilotes et  copilotes sont maintenant autoris\'es.
Le graphe a donc $6 \times 6 = 36 $ ar\^etes.
On d\'enombre les choix comme pr\'ec\'edemment :
\begin{itemize}
\item  Paul a le choix entre les six copilotes :  il en choisit un,
il en reste cinq libres ;
\item Brian a  le choix entre les $5$ copilotes libres ;
il en choisit un, il en reste  quatre libres ;
\item John a donc le choix entre $4$ copilotes, puis Marl\`ene entre  $3$,
etc.
\end{itemize}

Au final, on voit qu'on peut toujours former six \'equipes, et qu'on a:
\[
6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720
\]
fa\c{c}ons diff\'erentes de le faire (ce nombre s'appelle
\og factorielle\fg{} $6$, not\'e~$6!$).
\end{questions}
\newpage
\end{corrige}


% ex10

\sectionnn{Graphes orientés}

\begin{exo}{Construction d'un graphe orienté}{Lyc\'ee Albert Schweitzer, Le Raincy}{1}{5} 

Construire un graphe $\mathcal{G}$ d\'efini par le tableau ci-dessous.

\begin{center}
\begin{tabular}{|L|c|c|c|c|c|}
\hline
Sommet & A & B & C & D & E \\
\hline
Successeur & B, D & A, C, E & A  & C & C \\
\hline
\end{tabular}
\end{center}
\end{exo}

%% CORR EX10

\begin{corrige}
  Le tableau de successeurs sugg\`ere un graphe orient\'e.
On r\'epartit les cinq sommets en cercle, et on trace les ar\^etes
orient\'ees selon les indications du tableau.

\begin{center}
\includegraphics{011_ex8corrige-p319_087}
\end{center}
\end{corrige}

% ex11

\begin{exo}{Nombre d'arêtes d'un graphe}{Lyc\'ee Hoche, Versailles}{2}{20} 
On note $\mathcal{K}_n$ le graphe simple non orienté complet à $n$ sommets.
\label{11-exo3(Kn)}
\begin{questions}
\item \begin{questions}
\item Repr\'esenter les graphes simples non orient\'es complets $\mathcal{K}_5$ et $\mathcal{K}_6$.
\item Montrer que le nombre  d'ar\^etes de $\mathcal{K}_n$ est \'egal \`a $\dfrac{n(n-1)}{2}$.
\item Combien un graphe simple \emph{orient\'e} complet poss\`ede-t-il d'ar\^etes ?
\end{questions}

\item Applications:
\begin{questions}
\item Un tournoi d'escrime  r\'eunit dans une salle d'armes 4 \'equipes durant un
week-end. Chaque \'equipe rencontre une et une seule fois toutes les autres.
Combien de matchs dispute chaque \'equipe ?\\
Combien de matchs seront disput\'es au cours du week-end?

\item  Les douze membres d'une famille f\^etent No\"el. Ils veulent tous chanter
en duo, tous les couples possibles de chanteurs devant chanter une fois
exactement. Combien y aura-t-il de duos ?

\item  Les douze membres de la famille pr\'ec\'edente, au lieu de se faire des
cadeaux \`a  No\"{e}l, d\'ecident de jouer l'argent \'equivalent au loto (ils
esp\`erent gagner le gros lot). Sachant que la d\'epense
moyenne par cadeau est de $20$~\euro{} et que chacun fait un
cadeau \`a tous les autres, sauf lui-m\^eme, combien  vont-ils jouer ?
\end{questions}
\end{questions}
\end{exo}

%% CORR EX11

\begin{corrige}
\begin{questions}
\item
\begin{questions}
\item ~

\begin{minipage}[b][3.5cm][b]{5cm}
\begin{center}
\includegraphics{011_ex9corrige-p320_088}

$\mathcal{K}_5$
\end{center}
\end{minipage}\hfill
\begin{minipage}[b][3.5cm][b]{5cm}
\begin{center}
\includegraphics{011_ex9corrige-p320_089}

$\mathcal{K}_6$
\end{center}
\end{minipage}

\item \emph{Premi\`ere d\'emonstration}:
num\'erotons les sommets de $1$ \`a $n$. Toute paire de sommets $\{i, j\}$
avec $i \neq j$   d\'etermine une ar\^ete. Pour faciliter le d\'enombrement,
on  convient de la repr\'esenter par une paire $(i, j)$ avec $i < j$ .
Il suffit de compter le nombre de  ces couples:
\Par
\begin{tabularx}{\linewidth}{|Sc|>{\centering\arraybackslash}X|}
\hline\tabulartitle
Valeur de $j$ &  Nombre de couples $(i,j)$ avec $i < j$ \\
  \hline
  $2$ & 1 \\
  $3$ & 2 \\
  \vdots & ~\vdots~  \\
  $n-1$ & $n-2$ \\
  $ n$ & $n-1$  \\ \hline
  Nombre d'ar\^etes &
 $\begin{aligned}[t]
  = &\; 1 + 2 + 3 + \cdots + (n-2) + (n-1)\\
  = &\; \dfrac{n(n-1)}{2\strut}
  \end{aligned}$ \\
  \hline
\end{tabularx}

\newpage

\emph{Deuxi\`eme d\'emonstration}: tout sommet de $\mathcal{K}_n$ est de degr\'e $(n -1)$, donc la somme des degr\'es   vaut $n (n-1)$.

Cette somme est le double du nombre d'ar\^etes, donc le nombre d'ar\^etes vaut : $\dfrac{n(n-1)}{2}$.


\item Si l'on consid\`ere maintenant un graphe $\mathcal{K}'_n$ \emph{orient\'e} simple
complet d'ordre $n$ : pour chaque couple de sommets distincts $(i,j)$
il y a deux ar\^etes (l'une de $i$ vers $j$ et l'autre de $j$ vers $i$).
Il n'y a pas de boucle. Autrement dit le graphe $\mathcal{K}'_n$ s'obtient en d\'edoublant
toutes les ar\^etes de $\mathcal{K}_n$. Il poss\`ede donc:
\[
\frac{2\times n(n-1)}{2} = n(n-1) \ \text{ ar\^etes. }
\]
\end{questions}
\item Applications:
\begin{questions}
\item Supposons qu'on ait donn\'e un num\'ero \`a chaque \'equipe \mbox{(de 1 \`a 4)}.
Le graphe des rencontres est $\mathcal{K}_4$ : un sommet repr\'esente une \'equipe et
une ar\^ete (non orient\'ee) entre les sommets $i$ et $j$ $(i \neq j)$ repr\'esente
le match entre les \'equipes $i$ et $j$.
Le degr\'e de chaque sommet donne le nombre de matchs par \'equipe : c'est 3.
Le nombre d'ar\^etes donne le nombre de matchs:
\[
\frac{4(4-1)}{2} = 6.
\]

\item On associe \`a chaque membre de la famille un num\'ero et on le repr\'esente
par un sommet.
On repr\'esente un duo par une ar\^ete (non orient\'ee) reliant le membre $i$ et
le membre $j$.
Le graphe des duos   est donc  $\mathcal{K}_{12}$ et  le nombre de duos est le nombre
d'ar\^etes de $\mathcal{K}_{12}$, soit:
\[
\frac{12\times 11 }{ 2 }= 66 .
\]

\item Les \'echanges de cadeaux sont asym\'etriques (contrairement aux duos) donc
se repr\'esentent par un graphe orient\'e. Une ar\^ete de $i$  vers  $j$
repr\'esente le  cadeau de $i$  \`a $j$ et l'ar\^ete orient\'ee dans l'autre sens
repr\'esente le cadeau de $j$ \`a $i$.
On obtient donc un graphe simple (personne ne se fait de cadeau) orient\'e
complet d'ordre 12 : il y a $12\times 11 = 132$ ar\^etes.
La famille jouera:
\[
20 \times 132 = \numprint{2640} \text{ \euro.}
\]
\end{questions}
\end{questions}
\end{corrige}

% ex12

\begin{exo}{Longueur de chemins}{Lyc\'ee Saint-Rosaire, Sarcelles}{1}{20}

On donne le graphe $\mathcal{G}$ ci-dessous qui repr\'esente un r\'eseau routier.
Soit $M$ la matrice associ\'ee au graphe, les sommets \'etant num\'erot\'es
par ordre alphab\'etique.
\Par
\begin{minipage}[5.5cm]{8cm}
\begin{questions}
\item Avant d'écrire $M$ explicitement, expliquer pourquoi $M$ comporte :
\begin{itemize}
\item uniquement des   0 ou des 1 ;
\item  une ligne ne comportant que des z\'eros ;
\item  une colonne de z\'eros ;
\item  une colonne  comportant 4 fois le nombre 1.
\end{itemize}
\item \'Ecrire la matrice $M$.
\end{questions}
\end{minipage}\hfill
\begin{minipage}{3.5cm}
\begin{center}
\includegraphics{011_ex10enonce-p306_090}
\end{center}
\end{minipage}

\begin{questions}
\setcounter{enumi}{2}
\item Calculer $M^2$ et en d\'eduire le nombre de chemins de longueur 2 allant
de A \`a E.
\item Combien y a-t-il  de chemins de longueur 4 ? Existe-t-il des
chemins de longueur sup\'erieure ou \'egale \`a 6 ?
\end{questions}
\end{exo}

% CORR EX12

\begin{corrige}
\begin{questions}
\item $M$ ne comporte que des 0 et des 1 car il y a au plus une ar\^ete allant d'un sommet $i$ donn\'e \`a un autre $j$.

Le sommet C de num\'ero 3 n'est l'origine d'aucune ar\^ete (aucune ar\^ete ne sort de C) donc la troisi\`eme ligne de $M$ ne comportera que des 0. 

Mais C est l'extr\'emit\'e de quatre ar\^etes (d'origine  A, B, D et E respectivement) donc
la troisi\`eme colonne comporte quatre 1.

Aucune ar\^ete n'arrive en $A$ donc la premi\`ere colonne ne comporte que des
z\'eros.

\item On en d\'eduit l'\'ecriture de la matrice $M$:
\[
	M=\begin{pmatrix}
		0&1&1& 1&0&0 \\
		0&0&1&1&1&0  \\
		0&0&0&0&0&0  \\
		0&0&0&0&1&0  \\
		0&0&1&0&0& 1 \\
		0&0&1&0&0&0
	\end{pmatrix}
\]

\item Le nombre
de chemins de longueur 2 allant du sommet A au sommet E est donn\'e par le
coefficient d'indices (1,5) de la matrice $M^2$.
\[
	M^2=\begin{pmatrix}
		0&0&1& 1&\fbox{2}&0\\
		0&0&1&0&1&1 \\
		0&0&0&0&0&0\\
		0&0&1&0&0&1 \\
		0&0&1&0&0& 0 \\
		0&0&0&0&0&0
	\end{pmatrix}
\]
Il y a deux solutions, qu'on   peut ici  lister : (A,B,E) et (A,D,E).
\item On calcule $M^4$ (\`a la calculatrice).
\[
	M^4=\begin{pmatrix}
		0&0&3& 0&0&1\\
		0&0&1&0&0&0 \\
		0&0&0&0&0&0\\
		0&0&0&0&0&0 \\
		0&0&0&0&0& 0 \\
		0&0&0&0&0&0
	\end{pmatrix}
\]
Le coefficient $M^4_{i,j}$ donne le nombre de chemins de longueur 4 allant
du sommet de num\'ero $i$ au sommet de num\'ero $j$. La somme de tous ces
coefficients donne le nombre total de chemins de longueur 4 dans le graphe.

Il en existe cinq : trois chemins allant de A \`a C, un chemin de A \`a F et un chemin de B \`a C.

On calcule maintenant $M^6$ et on constate que tous les coefficients de la
matrice sont nuls. Il n'y a donc aucun chemin de longueur 6 dans le graphe.
Par suite, il n'y a aucun chemin de longueur sup\'erieure strictement \`a 6
(puisqu'un chemin de longueur $n$ o\`u $n>6$ contient n\'ecessairement un
sous-chemin de longueur 6).
\end{questions}
\end{corrige}


% ex13

\begin{exo}{Recherche de chemins}{Lyc\'ee Galil\'ee, Gennevilliers}{2}{30} 

\emph{Cet exercice est une variante de probl\`emes tr\`es
connus (\og les missionnaires et les cannibales\fg{},
\og le loup,  la ch\`evre et le chou\fg{}) qui sont
utilis\'es pour tester des algorithmes d'exploration dans les
graphes.}

Les porte-parole de quatre partis politiques, les partis Bleu,
Jaune, Rouge et Vert, doivent se rendre du S\'enat \`a l'\'Elys\'ee.
Il y a des divergences d'opinion tr\`es fortes, si bien qu'on ne peut
absolument pas laisser en t\^ete \`a t\^ete  les couples de
personnes suivants :
\begin{itemize}
\item le repr\'esentant Vert et le repr\'esentant Bleu;
\item le repr\'esentant Jaune et le repr\'esentant Rouge;
\end{itemize}

On met une voiture sans chauffeur \`a leur disposition. La voiture
ne peut prendre que deux passagers \`a la fois ; il faut pr\'evoir
plusieurs allers et retours pour les transporter tous. Comment
organiser les voyages successifs  en ne laissant jamais en t\^ete \`a
t\^ete deux personnes qui ne s'entendent pas ?

\emph{Indications:} D\'efinir un  graphe orient\'e dont les  sommets
repr\'esentent les groupes  de personnes pouvant se trouver ensemble au
S\'enat \`a un moment donn\'e, et dont les successeurs d'un sommet sont les
groupes possibles apr\`es un voyage.
Repr\'esenter le tableau des successeurs par sommet du graphe.
Trouver un chemin  reliant le sommet de d\'epart au sommet arriv\'ee.
\end{exo}

% CORR EX13

\begin{corrige}
Nommons B, V, J et R les repr\'esentants des partis politiques Bleu,
Vert, Jaune et Rouge respectivement.

Un sous-groupe de personnes restant \`a un moment donn\'e au S\'enat est
un mot d'au plus quatre lettres parmi (B,J,V,R), rang\'ees par ordre
alphab\'etique. Les \'etats impossibles sont JR et BV. L'\'etat initial
est BJVR (tous les quatre sont au S\'enat). L'\'etat final recherch\'e est
$\emptyset$ (plus personne au S\'enat). Le probl\`eme revient \`a
\emph{chercher un chemin dans le  graphe des \'etats menant de l'\'etat
initial BJVR \`a l'\'etat final} $\emptyset$.

Les  sommets du graphes sont tous les \'etats possibles au S\'enat,
c'est-\`a-dire tous les mots sauf JR et BV.
Expliquons sur quelques exemples comment d\'eterminer les successeurs
possibles d'un \'etat.

BJVR a comme \'etats successeurs possibles : RV, BR, VJ, BJ, puisque
deux personnes partent n\'ecessairement en voiture et deux autres restent
au S\'enat.

RV a comme successeurs :  BRV, JRV, BJRV, ou $\emptyset$. En effet, si V
et R sont encore  au s\'enat et la voiture \`a
l'\'Elys\'ee, la voiture doit revenir pour en chercher un :
elle peut revenir avec une personne ou deux ; dans le dernier  cas
on revient \`a l'\'etat initial. Si la voiture est au
S\'enat, alors les deux  partent et c'est termin\'e.  Cette
transition n'est possible que si c'est la $(2n+1)$\ieme  car il
faut un nombre impair d'allers et retours.

L'\'etat BRV a comme successeurs B ou V (si deux partent) ou BR
ou RV (si un seul part, sachant que B et V ne peuvent rester
ensemble).

Enfin, V a pour successeurs : RV, JV, BRV, BJV (selon que la
voiture revienne avec une ou deux personnes, et sachant que B ne
peut revenir chercher V). L'\'etat final n'est pas accessible,
car quand une personne reste seule au S\'enat, c'est que
d'autres personnes ont \'et\'e transport\'ees juste avant ;
la voiture est \`a l'Elys\'ee.

On obtient le tableau de successeurs suivant :

\begin{center}
\begin{multicols}{2}
\begin{tabular}{|c|c|}
\hline\tabulartitle
Sommet & Sommets successeurs \\ 
\hline
  BJRV & RV, BR, JV , BJ \\
  JVR &  R , V , JV , RV \\
  BRV & B, V , BR , RV \\
  BJR & R , J , BR , BJ \\
  BJV & B , V , JV , BJ \\
  RV &  BRV , JRV , $\varnothing$\\
  BR & BRV , BJR ,  $\varnothing$\\
\hline
\end{tabular}

\columnbreak

\begin{tabular}{|c|c|}
\hline\tabulartitle
Sommet & Sommets successeurs \\ 
\hline
  JV & BJV , JRV ,$\varnothing$\\
  BJ &  BJV , BJR ,$\varnothing$  \\
  B  &   BJ ,BR , BJV , BRV \\
  J &   BJ , JR , BJR , JRV \\
  R &   BR , RV ,  BJR , JRV \\
  V &   JV , RV , BRV, BJV \\\hline
\end{tabular}
\end{multicols}
\end{center}

On cherche un chemin de \emph{longueur impaire}  car il   doit
traduire les aller et retour de la voiture. 
\newpage
Une solution est par
exemple :

\begin{center}
\begin{tabular}{|*3{c|}}
\hline\tabulartitle
    (0) &   Au s\'enat &  A l'\'Elys\'ee \\\hline
     (1) &     BJRV &    $\varnothing$\\
     (2) &     RV   &    JB \\
     (3) &     BRV  &    J \\
     (4) &     V   &    BRJ \\
     (5) &     JV   &   BR \\
     (6) &  $\varnothing$& BJRV\\
     \hline
\end{tabular}
\end{center}

\begin{Remarque} il n'est pas n\'ecessaire de  dessiner le graphe (qui est assez compliqu\'e), car on peut d\'eterminer un chemin en \og suivant les liens\fg{}  dans le tableau.
\end{Remarque}
\end{corrige}


% ex14

\sectionnn{Recherche de la plus courte chaîne}

\begin{exo}{Distance minimale}{Lycée Virlogeux, Riom}{1}{20}
Le technicien d'une coopérative agricole prépare sa tournée.  Sur le graphe ci-dessous, les lettres représentent les exploitations agricoles des membres de la coopérative, les arêtes représentent les routes, pondérées par la distance à parcourir (en kilomètres).
\begin{center}
\includegraphics{011_ex12enonce-p307_091}
\end{center}
Il lui faut absolument commencer par l'exploitation  $A$ et terminer par l'exploitation $E$. Par quelles autres exploitations peut-il passer tout en réalisant le trajet le plus court? Quelle est alors la distance parcourue ?
\end{exo}

% CORR EX14

\begin{corrige}
On peut utiliser l'algorithme de Dijkstra.

Voici une façon de le présenter :

\begin{tabularx}{\linewidth}{|Sc|X|}
\hline\tabulartitle
\'Etape & Tâches à effectuer \\\hline
1 & \vspace*{-1em}
\begin{itemize}
\item Placer tous les sommets du graphe dans la 1\iere{} ligne d'un tableau.
\item Sur la 2\ieme{} ligne du tableau, écrire le poids 0 sous le point de départ A et le poids $\infty$ sous les autres sommets.\vspace*{-1em}
\end{itemize}
\\\hline
2 & \vspace*{-1em}
\begin{itemize}
\item Repérer le sommet X de poids minimal. Commencer une nouvelle ligne et rayer toutes les cases vides sous X.\vspace*{-1em}
\end{itemize}
\\\hline
3 & \vspace*{-1em}
\begin{itemize}
\item Pour chaque sommet Y adjacent à X, calculer la somme $p$ du poids de X et du poids de l'arête reliant X à Y. On ne passe jamais deux fois sur une arête.
\item Si $p$ est strictement inférieur au poids de Y, inscrire $p$ et X  dans case correspondante de la colonne \og Y \fg ;
\item Sinon, inscrire le poids de Y.
\item Pour les sommets non adjacents à X, compléter la ligne par les poids de la ligne précédente.\vspace*{-1em}
\end{itemize}
\\\hline
4 & \vspace*{-1em}
\begin{itemize}
\item S'il reste des sommets non sélectionnés, retourner à l'étape 2 
\item Sinon, passer à l'étape 5.\vspace*{-1em}
\end{itemize}
\\\hline
5 & \vspace*{-1em}
\begin{itemize}
\item La longueur minimale est le nombre lu sur la dernière ligne. On retrouve le chemin en ordre inverse en remontant les lettres écrites dans le tableau.\vspace*{-1em}
\end{itemize}
\\\hline
\end{tabularx}


\begin{tabularx}{\linewidth}{|*7{c|}>{\centering\arraybackslash}X|}
\hline\tabulartitle
A & B & C & D & E & F & G & Sommet choisi \\\hline
0 & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & A \\\hline
 & 12 A & 20 A & 9 A & $\infty$ & $\infty$ & $\infty$ & D \\\hline 
 & 12 A & 17 D &  & $\infty$ & 30 D & $\infty$ & B \\\hline 
 &  & 17 D &  & $\infty$ & 30 D & 25 B & C \\\hline 
 &  &  &  & $\infty$ & 28 C & 24 C & G\\\hline 
 &  &  &  & 33 G & 28 C &  & F\\\hline 
 &  &  &  & 31 F &  &  & E\\\hline 
\end{tabularx}
\Par
On en conclut que la distance minimale est 31 kilomètres.

Le parcours est le suivant :  A-D-C-F-E.
\end{corrige}

% ex15

\begin{exo}{Recherche de durée minimale}{Lyc\'ee Flora Tristan, Noisy-le-Grand}{2}{20} 

Le Kougelhof est un d\'elice mais un casse-t\^ete \`a pr\'eparer.
Il faut :
\begin{itemize}
\item Pr\'eparer d'abord le levain et laisser fermenter 30~minutes.

\item Tremper les raisins secs dans de l'eau additionn\'ee de rhum au moins
15~minutes.

\item M\'elanger farine, \oe ufs, beurre et sucre et p\'etrir la
p\^ate pendant 15~minutes.

\item Incorporer le levain \`a la p\^ate et la faire lever
pendant  3~heures (premi\`ere \og pouss\'ee\fg{}).

\item Rompre la p\^ate pour y incorporer les raisins secs.
Laisser  pousser la p\^ate dans son moule pendant 2~heures.

\item Enfourner pendant 1~heure.

\item Laisser refroidir deux heures minimum.

\item Entre temps, il faut pr\'eparer les asperges strasbourgeoises :
les \'eplucher prend 15~minutes, les cuire 30~minutes, les
laisser refroidir 2~heures.

\item La cuisson du r\^oti prend une heure.

\item L'ordre de cuisson est d'abord le kougelhof, puis les asperges,
puis le r\^oti.
\end{itemize}
\begin{questions}

\item Repr\'esenter sous forme d'un graphe pond\'er\'e $\mathcal{G}$ les contraintes d'ordre entre ces t\^aches.

\item  Quelle est la cha\^ine de poids maximal du graphe ? Quelle est la cha\^ine la plus longue ?

\item En regroupant des t\^aches pouvant \^etre men\'ees en parall\`ele, proposer une planification \og optimale\fg{} des pr\'eparatifs du repas
(minimisant la dur\'ee totale de pr\'eparation).
\`A quelle heure au plus tard doit-on commencer les pr\'eparatifs si le repas
est pr\'evu \`a 20~h?
\end{questions}
\end{exo}

% CORR EX15

\begin{corrige}
\begin{minipage}{0.45\linewidth}
\begin{questions}
\item On d\'efinit ici le graphe d\'erivant l'ordre des t\^aches. On \'etablit une ar\^ete orient\'e $A \longrightarrow B$ si la t\^ache $A$ doit se d\'erouler  \emph{en totalit\'e avant}
la t\^ache~$B$.

Pour  tenir compte des contraintes
de dur\'ee de chaque t\^ache,  on donne \`a l'arc $A
\longrightarrow B$ un poids qui correspond \`a la dur\'ee
minimale \emph{en unit\'es d'heure} s'\'ecoulant entre le
d\'ebut de la t\^ache $A$ et le d\'ebut de la t\^ache~$B$.

Par exemple, l'\'epluchage des asperges prend $15$ minutes:\\
l'ar\^ete \mbox{A$_2 \longrightarrow$ A$_3$} est pond\'er\'ee
par $0,25$.
\end{questions}
\end{minipage}
\hfill
\begin{minipage}{0.5\linewidth}
\begin{tabular}{|R|l|}
\hline \text{\Large\strut}
Asperges & A$_1$ : \'epluchage \\ \text{\Large\strut}
         & A$_2$ : cuisson  \\ \text{\Large\strut}
			& A$_3$ : refroidissement\\
\hline \text{\Large\strut}
P\^ate & P$_1$ : p\'etrissage\\ \text{\Large\strut}
	    & P$_2$ : 1\up{\`ere} pouss\'ee  \\  \text{\Large\strut}
	    & P$_3$ : 2\up{\`eme} pouss\'ee  \\  \text{\Large\strut}
	    & P$_4$ : cuisson \\ \text{\Large\strut}
		 & P$_5$ : refroidissement  \\
\hline
\text{\Large\strut}Levain & L : fermentation \\
\hline
\text{\Large\strut}Raisins  &T : Trempage \\
\hline
\text{\Large\strut}R\^oti& R : cuisson\\
\hline
\end{tabular}
\vspace*{2em}~\par 
\end{minipage}
\Par
\begin{center}
\includegraphics{011_ex13corrige-p326_092}
\end{center}
\newpage
\begin{questions}
\setcounter{enumi}{1}
\item La cha\^ine de poids maximal est (L, P$_2$, P$_3$, P$_4$, P$_5$, Repas);
elle est de poids 8,5.
La cha\^ine la plus longue  est (L, P$_2$, P$_3$, P$_4$, A$_2$, $R$, Repas)
mais elle de poids inf\'erieur (8).
On en d\'eduit que le temps de pr\'eparation minimum est \emph{au moins de huit
heures et demi}, car quelle que soit
la planification des t\^aches il faudra r\'ealiser la s\'equence de t\^aches
correspondant \`a la cha\^ine de poids maximal.

\item Chaque groupe de t\^aches doit \^etre un sous graphe stable (sans ar\^ete) du graphe pr\'ec\'edent. Un groupe $G_1$ pr\'ec\'edera un autre $G_2$
\`a condition qu'il contienne  une t\^ache $T_1$ de $G_1$ pr\'ec\'edant une t\^ache
$T_2$ de $G_2$, mais qu'aucune t\^ache $T_2$ de $G_2$ ne pr\'ec\`ede une t\^ache
$T_1$ de $G_1$. La dur\'ee de r\'ealisation d'un groupe  est la dur\'ee maximale
de ses t\^aches. La figure ci-dessous fournit une solution avec une
dur\'ee totale minimale de 9 heures.

\begin{center}
\includegraphics{011_ex13corrige-p326_093}
\end{center}

Est-ce optimal en terme de temps ? Pourrait-on pr\'eparer le repas en huit
heures et demi?

La cha\^ine (L, P$_2$, P$_3$, P$_4$, P$_5$, Repas) de poids maximal de la question~2. doit  figurer dans la solution.
La question est de savoir si l'on peut lui \og greffer\fg{} les autres
t\^aches, sans allonger la cha\^ine.  Il se trouve que non, car les t\^aches
$A_2$ et $R$ doivent s'intercaler apr\`es $P_4$. On  obtient n\'ecessairement
une solution \'equivalente en temps de pr\'eparation, \`a celle de la figure
pr\'ec\'edente (on peut cependant modifier certains groupes).

\begin{Remarque} si l'on accepte de cuire les asperges d'abord, on trouve un temps de pr\'eparation minimal de huit heures et demi.
\end{Remarque}

\begin{center}
\includegraphics{011_ex13corrige-p327_094}
\end{center}

La préparation doit donc commencer à 11\,h\,30.
\end{questions}
\newpage
\end{corrige}

%% EX16 (new 2015)

\begin{exo}{Recherche de distance minimale}{Lycée Jean-Pierre Vernant, Sèvres}{2}{25}
Une grande ville a mis en place un système de locations de bicyclettes en libre service.

Un abonné peut ainsi louer une bicyclette dans une station puis la déposer dans n'importe quelle station de son choix.

La ville compte 7 stations nommées A, B, C, D , E , F et G.

Les stations sont reliées entre elles (ou pas) par une piste cyclable et les temps de parcours en minutes sont indiqués sur le graphe suivant :
 \begin{center}
\includegraphics{11_fig_03}
\end{center}
\begin{questions}
\item Philippe, cycliste très prudent, décide de visiter cette ville en n'empruntant que des pistes cyclables.
\begin{questions}
\item A-t-il la possibilité d'effectuer un parcours empruntant une fois et une seule toutes les pistes cyclables ?
\item \`A la fin de ce parcours, si cela est possible, pourra-t-il rendre sa bicyclette dans la station de départ ?
\end{questions}
\newpage
\item On appelle $M$ la matrice associée à ce graphe.
\begin{questions}
\item Parmi les deux matrices ci-dessous, dire sans aucun calcul celle qui peut être la matrice $M^3$. Justifier la réponse.

\[
N = \begin{pmatrix}
4 & 9 & 8 & 5 & 5 & 9 & 2\\
9 & 6 & 10 & 7 & 10 & 6 & 4\\
8 & 10 & 8  &5 & 10 & 9 & 4\\
5 & 7 & 5 & 2 & 8 & 4 & 5\\
5  &10 & 10 & 8 & 6 & 11 & 2\\
9 & 6 & 9 & 4 & 11 & 4 & 6\\
2 & 4 & 4 & 5 & 2 & 6 & 0
\end{pmatrix}
\]
\Par
\[
T = \begin{pmatrix}
4 & 9 & 8 & 5 & 5 & 9 & 1\\
9 & 6 & 10 & 7  &10 & 6 & 4\\
8 & 10 & 8 & 5 & 10 & 9 & 4\\
5 & 7 & 5 & 2 & 8 & 4 & 5\\
5 & 10  &10 & 8 & 6 & 11 & 0\\
9 & 6 & 9 & 4 & 11 & 4 & 6\\
1 & 4 & 4 & 5 & 0 & 6 & 0
\end{pmatrix}
\]
\item Philippe a loué une bicyclette à la station~F et l'a rendue à la\linebreak station~E. Au cours de son trajet, il est passé par exactement deux autres stations.
Combien de trajets différents a-t-il pu suivre ?\\ Justifier.
\end{questions}
\item Le lendemain, il envisage de rejoindre le plus rapidement la station G en partant de la station A. \`A l'aide d'un algorithme, déterminer le parcours adéquat et donner le temps nécessaire pour l'effectuer.
\end{questions}
\end{exo}

%% CORR EX16

\begin{corrige}
\begin{questions}
\item 
\begin{questions}
\item \raisebox{-0.7em}{\begin{tabularx}{\linewidth}{|L|*7{>{\centering\arraybackslash}X|}}
\hline
Sommet & A & B & C & D & E & F & G\\
\hline
Degré & 3  &4 & 4 & 3 & 4 & 4 & 2\\
\hline
\end{tabularx}}
\Par
D'après le théorème d'Euler, puisqu'il y a exactement deux sommets de degré impair, on peut réaliser une chaîne eulérienne ; donc Philippe peut parcourir chaque piste cyclable une fois et une seule.
\item En revanche, d'après le même théorème, il ne peut revenir à son point de départ, puisque pour avoir un cycle eulérien, il faut qu'il n'y ait aucun sommet de degré impair.
\end{questions}
\item
\begin{questions}
\item La bonne matrice ne peut être que N car il existe deux trajets (au moins) de longueur 3 permettant d'aller de G à E : G D B E et \mbox{G F C E}. Donc il ne peut y avoir un zéro pour le terme de ligne 7 et de colonne 5, ce qui est le cas dans T.
\item Philippe a donc effectué un trajet de longueur 3 de F à E. La matrice $M^3$ nous précise qu'il y a 11 trajets possibles : il suffit de lire le terme de ligne 6 et de colonne 5.
\end{questions}
\item Il nous faut trouver un trajet minimal ; on va donc utiliser l'algorithme de Dijkstra. On réalise le tableau suivant :
\Par
\begin{tabularx}{\linewidth}{|L|*7{>{\centering\arraybackslash}X|}}
\hline\tabulartitle
Sommet & A & B & C & D & E & F & G\\
\hline
Étape 1 & 0 & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$\\
\hline
Étape 2 & X & 7A & 11A & $\infty$ & $\infty$ & 13A& $\infty$\\
\hline
Étape 3 & X & X & 11A & 23B & 21B & 13A & $\infty$\\
\hline
Étape 4 & X & X & X & 23B & 19C & 13A & $\infty$\\
\hline
Étape 5 & X & X & X & 23B & 19C & X & 31F \\
\hline
Étape 6 & X & X & X & 23 B & X & X & 31F\\
\hline
Étape 7 & X & X & X & X & X & X & 28D\\
\hline
\end{tabularx}
\Par
D'après cet algorithme, et en remontant le tableau, le parcours de temps minimal entre A et G est A-B-D-G, et il est de durée 28 min.
\end{questions}
\end{corrige}



% ex17

\sectionnn{Graphes probabilistes}

\begin{exo}{Graphe probabiliste, état stable}{Lyc\'ee Gaston Bachelard, Chelles}{1}{30} 

Une soci\'et\'e de location de voitures \`a la semaine poss\`ede une agence \`a Lyon et une autre \`a Paris.
A l'ouverture des deux agences, le parc automobile comprenait 300 voitures \`a Lyon et 500 \`a Paris.
On a constat\'e qu'\`a la fin de chaque semaine, 70\,\% des voitures lou\'ees \`a Paris retournaient dans l'agence parisienne, les autres \'etant rendues \`a
Lyon, et que 60\,\% des voitures lou\'ees \`a Lyon retournaient dans l'agence lyonnaise, les autres \'etant rendues \`a Paris.

On choisit une voiture au hasard dans le parc automobile. 

On note $l_n$ (resp. $p_n$) la probabilit\'e que la voiture soit rendue  \`a Lyon
(resp. \`a Paris) \`a la fin de la $n$-i\`eme semaine.
\begin{questions}
\item Traduire les donn\'ees par un graphe probabiliste $\mathcal{G}$, dont vous donnerez
la matrice de transition $M$ et  l'\'etat probabiliste initial $E_0$.

\item Calculer l'\'etat probabiliste du graphe $\mathcal{G}$ : au bout d'une semaine,
au bout de 10 semaines.

\item D\'eterminer l'\'etat stable du graphe $\mathcal{G}$.

\item Au bout d'un grand nombre de semaines, comment se r\'epartira le parc automobile entre les deux agences ?
\end{questions}
\end{exo}

% CORR EX17

\begin{corrige}
\enlargethispage*{2em}
On mod\'elise le probl\`eme par un graphe probabiliste \`a deux \'etats:
$L$ (la voiture se trouve \`a Lyon) et $P$ (la voiture se trouve \`a Paris).

En notant $L_n$ (resp. $P_n$) l'\'ev\'enement \og la voiture se trouve \`a Lyon (resp. Paris) \`a la fin de $n$-ième semaine\fg, l'\'enonc\'e donne les
probabilit\'es conditionnelles suivantes :
\begin{itemize}
\item $P_{P_n}(P_{n+1}) = 0,7$,  ce que l'on traduit par une boucle sur $P$ pond\'er\'ee par~0,7 ;
\item $P_{L_n}(L_{n+1}) = 0,6$ : une boucle sur $L$  pond\'er\'ee par 0,6 ;
\end{itemize}
On en d\'eduit:
\begin{itemize}
\item $P_{P_n}(L_{n+1}) = 0,3$  : une ar\^ete de $P$ vers $L$  pond\'er\'ee par  0,3;
\item et $P_{L_n}(P_{n+1}) = 0,4$ : une ar\^ete de $L$ vers $P$ pond\'er\'ee par 0,4.
\end{itemize}

\begin{questions}
\item Les sommets \'etant list\'es par ordre alphab\'etique, on obtient le graphe $\mathcal{G}$ et sa matrice de transition $M$ suivants:

\begin{minipage}{5.75cm}
\begin{center}
\includegraphics{011_ex14corrige-p327_095}
\end{center}
\end{minipage}\hfill
 \begin{minipage}{5.75cm}
\[
M =  \begin{pmatrix}0,6 &0,4 \\0,3 & 0,7 \end{pmatrix}
\]
\end{minipage}

La voiture \'etant choisie au hasard, on ne sait pas si elle se trouve \`a Lyon
ou \`a Paris. Mais on conna\^it la loi de probabilit\'e de son lieu initial.
\[
l_0=p(L_0)=\dfrac{300}{800}=\dfrac{3}{8}
\quad;\quad
p_0=p(P_0)=\dfrac{500}{800}=\dfrac{5}{8}.
\]
L'\'etat initial du graphe est repr\'esent\'e par la matrice ligne $E_0$:
\[
E_0 = \begin{pmatrix}\dfrac{3}{8} &  \dfrac{5}{8}\end{pmatrix}.
\]

\item L'\'etat du graphe $E_1$ apr\`es une transition est d\'efini par:
$E_1 = E_0 \times M$.

L'\'etat du graphe $E_{10}$ apr\`es  dix  transitions est d\'efini par:\\
$E_{10}= E_0 \times M^{10}$.

On peut calculer $E_1$ manuellement;  on calcule $E_{10}$ avec la calculatrice.

On obtient : $E_{1}= \begin{pmatrix}\dfrac{33}{80}& \dfrac{47}{80} \end{pmatrix}$ et $E_{10}= \begin{pmatrix} 0,429  & 0,571\end{pmatrix}$.

\item Le graphe admet un \'etat stable.
Posons:
\[
E_s = \begin{pmatrix}l & p\end{pmatrix} \ \text{ avec } l+p=1,  \  l\geq 0  \  \text{ et } p\geq 0.
\]
D\'eterminer $E_s$ (par calcul alg\'ebrique) \'equivaut \`a r\'esoudre les \'equations
suivantes dans $\R_+ \times \R_+$:
\[
(1) \quad E_s = E_s \times M
\qquad \qquad
(2) \quad l+p=1.
\]
Calculons le produit matriciel $E_s \times M $ en fonction de $l$ et $p$ :
\[
E_s\times M = \begin{pmatrix}l & p\end{pmatrix}\times
	\begin{pmatrix}
	0,6 &0,4 \\
	0,3 & 0,7
	\end{pmatrix} = \begin{pmatrix}0,6l+0,3p & 0,4l+0,7p \end{pmatrix}.
\]
On traduit  l'\'equation  (1) par un syst\`eme d'\'equations dont les inconnues
sont $l$ et $p$:
\begin{align*}
E_s\times M =  E_s
	& \iff \begin{pmatrix}0,6l+0,3p & 0,4l+0,7p\end{pmatrix} =\begin{pmatrix}l & p\end{pmatrix} \\
	& \iff \left\{
		\begin{aligned}
		0,6l+0,3p = l \\
		0,4l+0,7p = p
		\end{aligned}\right.
\end{align*}
R\'esoudre (1) et (2)  \'equivaut \`a r\'esoudre le syst\`eme d'\'equations lin\'eaires:
\begin{align*}
	\left\{
		\begin{aligned}
		-0,4l+0,3p = 0 \\
		0,4l-0,3p = 0 \\
		l+p=1
		\end{aligned}\right. \iff
%% Par combinaison lin\'eaire $(L_1+0,4L_3)$ :
	\left\{
		\begin{aligned}
		0,7p = 0,4  \\
		l+p= 1
		\end{aligned}\right.
	\iff \left\{
		\begin{aligned}
		p = \frac{4}{7}  \\
		l = \frac{3}{7}
		\end{aligned}\right.
\end{align*}
L'\'etat stable $E_s$ est : $\begin{pmatrix} \dfrac{3}{7} &  \dfrac{4}{7} \end{pmatrix}$.

\item Les \'etats $E_n$  convergent vers  $E_s$, c'est-\`a-dire:
\[
\lim_{n \to+\infty} p_n = \dfrac{4}{7}
\quad \text{ et } \quad
\lim_{n \to+\infty} l_n = \dfrac{3}{7}.
\]
En interpr\'etant ces probabilit\'es comme des fr\'equences, on  d\'eduit qu'\`a tr\`es
long terme le parc automobile se r\'epartira de fa\c{c}on stable entre les deux
agences, environ  42,9\,\% des voitures \'etant \`a Lyon et 57,1\,\% des voitures \`a
Paris (\`a 0,1\,\% pr\`es).
Soit, \`a la voiture pr\`es, 343 voitures \`a Lyon et 457 \`a Paris.
\end{questions}
\end{corrige}

% ex18

\begin{exo}{Graphe probabiliste, état stable}{Lyc\'ee Jacques Monod, Clamart}{3}{45} 

On s'int\'eresse au trafic a\'erien long courrier entre trois a\'eroports,
not\'es A, B et C.
Le graphe ci-dessous d\'ecrit les liaisons a\'eriennes entre ces a\'eroports
(les autres liaisons sont ignor\'ees).
Un vol durant plusieurs heures, un avion vole une fois par jour exactement.

\begin{minipage}{7.2cm}
On note $a_n$ (resp. $b_n$, $c_n$) le nombre d'avions partis de A (resp. B, C)
le jour donn\'e $n$. La capacit\'e  totale des trois a\'eroports est constante, donc pour tout $n$,\\ 
$a_n + b_n + c_n= 600$.

On d\'efinit $E_n$, l'\'etat du trafic le jour  $n$, par la\linebreak matrice ligne:
$E_n = \begin{pmatrix}a_n &b_n &c_n \end{pmatrix}$.

On suppose comme trafic initial (au jour not\'e 0) :
\[
E_0= \begin{pmatrix}200 & 200& 200 \end{pmatrix}.
\]
\end{minipage}
\hfill
\begin{minipage}{3.3cm}
\begin{center}
\includegraphics{011_ex15enonce-p309_096}
\end{center}
\end{minipage}

\subsubsectionnn{Partie A}

Les fr\'equences de destinations au d\'epart d'un a\'eroport sont donn\'ees ci-dessous.
Ainsi, 40\,\% des avions partant de $A$ volent vers
B et  60\,\% vers C.

\begin{center}
\begin{tabular}{|L|*3{Sc|}}
\tabulartitle
\multicolumn{1}{l|}{\cellcolor{white}} &
\psline(-0.231,0.36)(3.99,0.36)  Vers A &  Vers B & Vers C\\
\hline
De  A  &  0   &  40\, \%& 60\, \% \\\hline
De  B  & 40\,\% & 0 &  60\, \% \\\hline
De  C  & 40\,\% &  60\, \% &  0\\
\hline
\end{tabular}
\end{center}

\begin{questions}
\item \`A l'aide des donn\'ees pr\'ec\'edentes, d\'efinir le graphe probabiliste  $\mathcal{G}$
repr\'esentant le trafic a\'erien entre ces trois a\'eroports. D\'eterminer sa matrice de transition  $M$ (les sommets seront num\'erot\'es par ordre alphab\'etique).

\item Quel est l'\'etat du  trafic le jour suivant ? deux jours plus tard ?

\item Si $E_n$ est l'\'etat du trafic un jour donn\'e $n$, montrer que l'\'etat du
trafic le jour suivant v\'erifie:
$
E_{n+1} = E_n \times M.
$
En d\'eduire que l'\'etat du trafic le jour $n$ est d\'efini par
$E_n = E_0\times M^n$.

\item \`A l'aide d'une calculatrice, calculer $M^{10}$ puis $M^{20}$ (arrondir les coefficients \`a $10^{-3}$ pr\`es) et les \'etats du trafic $E_{10}$
puis $E_{20}$ (\`a un avion pr\`es). Conjecturer l'\'etat du trafic \`a long terme.

\item Montrer par le calcul alg\'ebrique qu'il existe un unique \'etat  du trafic
$E= \begin{pmatrix}a  & b &c \end{pmatrix}$ v\'erifiant :
\[
	E = E \times M \quad \text{ et } \quad a + b + c = 600.
\]

\item  En admettant que  la suite des \'etats ($E_n$) converge vers l'\'etat
$E$ d\'efini pr\'ec\'edemment,
comment se r\'epartira le trafic entre les trois a\'eroports \`a long terme ?
\end{questions}

\subsubsectionnn{Partie B}

On veut \'equilibrer \`a long terme le trafic entre les trois a\'eroports. On con\c{c}oit que cela doit se traduire par un \'etat stable du trafic
$E=\begin{pmatrix}a & b & c\end{pmatrix}$ v\'erifiant :
\[
	E = E \times M \quad \text{ et } \quad a = b = c = 200.
\]
Comment modifier les probabilit\'es du  graphe probabiliste $\mathcal{G}$ pr\'ec\'edent pour  satisfaire cette condition d'\'equilibre ?
\end{exo}

% CORR EX18

\begin{corrige}
\subsubsectionnn{Partie A}

\begin{questions}
\item En ordonnant les sommets par (A, B, C), la matrice de transition
du graphe $\mathcal{G}$ est :
\[
	M = \begin{pmatrix}
	0 & 0{,}4 & 0{,}6\\
	0{,}4  &  0 & 0{,}6  \\
	0{,}4  & 0{,}6  & 0
\end{pmatrix}
\]
On obtient donc le graphe suivant :

\begin{center}
  \includegraphics{011_ex15corrige-p329_097}
\end{center}
\newpage
\item Le premier (jour $0$), $200$ avions  partent de chaque a\'eroport.
Les avions arriv\'es au soir du jour $0$  \`a l'a\'eroport $A$  sont au nombre de :
$0,4\times 200$ (venant de B)  plus $0,4\times 200$ (venant de C), soit 160.
Aucun avion ne reste au sol ; ces 160 avions partent de A le lendemain
(jour $1$).
\begin{center}
\begin{tabular}{|C|*3{Sc|}}
\hline\tabulartitle
Jour  &   0 &  1&   2\\  \hline
A &  200  &  $80 + 80 = 160$   &    $ 80+ 96 = 176$
\\
B &  200 &    $80+ 120 = 200$  &  $ 64+ 144 = 208$
\\
C &  200 &  $120+ 120 = 240$  &  $96 + 120  = 216$\\
\hline
\end{tabular}
\end{center}

\item Soit un \'etat $E_n$ quelconque :
$\begin{pmatrix}a_n & b_n &c_n \end{pmatrix}$.
Le jour suivant $(n+1)$, les nombres d'avions partant de chaque a\'eroport sont
d\'efinis par :
\[
\left\{
\begin{aligned}
a_{n+1} & = 0{,}4\times b_n + 0{,}4 \times c_n   \\
b_{n+1} & = 0{,}4\times a_n + 0{,}6 \times c_n \\
c_{n+1} & = 0{,}6\times a_n + 0{,}6 \times b_n
\end{aligned}
\right.
\]

On obtient le m\^eme r\'esultat  en effectuant le produit matriciel $E_n \times M$:
\begin{multline*}
	\begin{pmatrix}
	a_n & b_n &c_n
	\end{pmatrix}
	\times
	\begin{pmatrix}
	0 & 0{,}4 & 0{,}6\\
	0{,}4  &  0 & 0{,}6  \\
	0{,}4  & 0{,}6  & 0
	\end{pmatrix} \\
	= \begin{pmatrix}
	0{,}4b_n + 0{,}4  c_n
	& 0{,}4 a_n + 0{,}6  c_n
	&0{,}6a_n + 0{,}6 b_n
	\end{pmatrix}
\end{multline*}
Ainsi, $E_{n+1}= E_n \times M$.

On reconnaît ici une relation de récurrence qui définit une suite géométrique ; ainsi, $E_n=E_0\times M^n$.
%On d\'eduit la formule $E_{n}= E_0\times M^n$ par r\'ecurrence : 
%\begin{itemize}
%\item La formule est vraie pour $n=0$ puisque $E_{1}= E_0\times M$.
%\item Supposons la formule vraie au rang $k$, c'est-\`a-dire  $E_{k}= E_0\times M^k$.

%On sait que  $E_{k+1}= E_k\times M$, donc  $E_{k+1}= (E_0\times M^k)\times M$.

%Par associativit\'e,
%\[ (E_0\times M^k)\cdot M = E_0\times (M^k \times M) = E_0 \times (M^{k+1}). \]

%Ce qui prouve $E_{k+1}= E_0 \times M^{k+1}$ et donc que la formule est vraie au rang $k+1$.
%\end{itemize}

\item Gr\^ace la calculatrice :
\begin{align*}
&  M^{10} =
	\begin{pmatrix}
	0{,}286 & 0{,}341 & 0{,}373 \\
	0{,}286 & 0{,}342 & 0{,}373 \\
	0{,}286 & 0{,}336 & 0{,}379
	\end{pmatrix}
&; &\qquad   E_{10} =  \begin{pmatrix}171& 204& 225 \end{pmatrix}.\\
&  M^{20} =
	\begin{pmatrix}
	0{,}286 & 0{,}339  &  0{,}375\\
	0{,}286 & 0{,}339  &  0{,}375 \\
	0{,}286 & 0{,}339  &  0{,}375
	\end{pmatrix}
&  ;   &\qquad   E_{20}=  \begin{pmatrix} 171 & 204 & 225\end{pmatrix}.
\end{align*}
On  conjecture  qu'\`a long terme, le nombre d'avions par jour  partant de chaque a\'eroport est respectivement 171, 204   et  225.
\enlargethispage*{3em}

\item On r\'esout le syst\`eme form\'e par les  deux \'equations
$E = E\times M$ et\\ $a+b+c=600$ :
\begin{align*}
\begin{cases}
\begin{pmatrix} a & b & c \end{pmatrix} = \begin{pmatrix} a & b & c \end{pmatrix} \times M 
\\
a+b+c=600
\end{cases}
& \iff
\begin{cases}
a = 0{,}4b + 0{,}4c \\
b = 0{,}4a+0{,}6c\\
c = 0{,}6a + 0{,}6b \\
 a + b + c = 600
\end{cases}\\
& \iff
	\begin{cases}
	 -10 a + 4b + 4c =0\\
	 4a -10b +6c=0\\
 6a + 6b -10c=0 \\
	a + b + c = 600
	\end{cases}
\end{align*}
On supprime la troisi\`eme \'equation qui est redondante (elle \'equivaut \`a la
somme  des deux premi\`eres). En simplifiant par 2, on obtient :
\begin{align*}
\left\{
	\begin{aligned}
	& -5 a + 2b + 2c =0\\
	&  2a -5b +3c=0\\
	& a + b + c = 600
	\end{aligned}
\right.
&\iff \left\{
	\begin{aligned}
	& - 5a + 2b + 2(600 - a - b) =0\\
	&  2a -5b + 3(600 - a - b)=0\\
	&  c = 600 - a - b
	\end{aligned}
\right. \\
& \iff  \left\{
	\begin{aligned}
	& - 7a  + \numprint{1200} =0\\
	&  -a -8b + \numprint{1800}=0 \\
	&  c = 600 - a - b
	\end{aligned}
\right.   \iff
\left\{
	\begin{aligned}
	& a  =  \frac{\numprint{1200}}{7}  \\
	& b =  \frac{\numprint{1425}}{7}  \\
	&  c = 225
	\end{aligned}\right.
\end{align*}
En arrondissant les valeurs \`a l'unité, on confirme la conjecture pr\'ec\'edente:
\[
E = \begin{pmatrix}171 & 204 & 225\end{pmatrix}.
\]
\end{questions}

\subsubsectionnn{Partie B}

\begin{minipage}[c]{5.5cm}
On modifie les probabilit\'es du graphe comme indiqu\'e dans la figure  ci-contre. La somme des poids des ar\^etes issues d'un sommet doit \^etre \'egale \`a 1.  Il suffit d'introduire trois inconnues:
$p$, $q$ et $r$ telles que :
\[
0\leq p \leq 1,
\ \
\leq q \leq 1
\ \text{ et } \ 0
\leq r \leq 1.
\]
La matrice de transition est alors  :
 \[
M' = \begin{pmatrix}
 	0 & p & 1-p\\
	q  &  0 & 1-q  \\
	r  & 1-r  & 0
\end{pmatrix}.
\]
\end{minipage}
\hfill
\begin{minipage}[c]{4.5cm}
\includegraphics{011_ex15corrige-p331_098}
\end{minipage}

On r\'esout l'\'equation d\'efinissant l'\'etat stable avec pour inconnues
$p$, $q$ et $r$  :
\begin{gather*}
\begin{pmatrix} 200 & 200 & 200\end{pmatrix} = \begin{pmatrix} 200 & 200 & 200\end{pmatrix} \times
	\begin{pmatrix}
	0 & p & 1-p\\
	q  &  0 & 1-q  \\
	r  & 1-r  & 0
	\end{pmatrix}   \\
\begin{aligned}
	\iff &   \left\{
		\begin{aligned}
   	& 200q+200r  =200\\
		& 200p+200(1-r)=200 \\
		&200(1-p)+200(1-q)=200
		\end{aligned}\right.
	 \\
	 \iff &   \left\{
		\begin{aligned}
   	& q+r  =1\\
		& p+(1-r)=1 \\
		&(1-p)+(1-q)=1
		\end{aligned}\right.
	\iff
	 \left\{
		\begin{aligned}
	   & q+r  =1\\
		& p-r=0 \\
		&p+q=1
		\end{aligned}\right.
	\iff  \left\{
		\begin{aligned}
   	& p=r \\
		&p+q=1
		\end{aligned}\right.
	\end{aligned}
\end{gather*}
Tout triplet  $(p,q,r)$ satisfaisant les conditions suivantes est une solution :
\[
0\leq p \leq 1 \quad,\quad 0\leq q \leq 1
\quad,\quad 0\leq r \leq 1 \quad,\quad r = p \quad,\quad q = 1-p.
\]
Par exemple, on peut choisir : $p= r = 0{,}35$ et  $q= 0{,}65$.

\end{corrige}

%% EX19 (new 2015)

\begin{exo}{Exercice de synthèse}{Lycée  Jean-Pierre Vernant, Sèvres}{3}{30}
Chaque mois, un institut de sondage donne la cote de popularité d'une personnalité politique dans l'opinion publique.

Les personnes sondées sont soit favorables, soit défavorables à cette personnalité.

Initialement, il y a 80\,\% de personnes favorables à cette personnalité.

De chaque mois au suivant, on considère que :
\begin{itemize}
\item 30\,\% des personnes qui étaient favorables à cette personnalité ne le sont plus.
\item 10\,\% des personnes qui n'étaient pas favorables à cette personne le deviennent.
\end{itemize}
On note, pour tout entier naturel $n$ :
\begin{itemize}
\item $a_n$ la probabilité qu'une personne interrogée au hasard au bout de $n$ mois soit favorable à cette personnalité.
\item $b_n$ la probabilité qu'une personne interrogée au bout de $n$ mois ne soit pas favorable à cette personnalité.
\item $P_n = \begin{pmatrix}a_n & b_n\end{pmatrix}$ la matrice traduisant l'état probabiliste au bout de $n$ mois.
\end{itemize}

\newpage

\subsubsectionnn{Partie A}

\begin{questions}
\item Déterminer la matrice $P_0$ donnant l'état probabiliste initial.
\item Déterminer le graphe probabiliste correspondant à la situation.
\item 
\begin{questions}
\item Déterminer la matrice de transition $M$.
\item Déterminer la matrice $P_2$.
\end{questions}
\item Déterminer l'état stable et interpréter ce résultat.
\end{questions}

\subsubsectionnn{Partie B}

\begin{questions}
\item Montrer que $a_{n+1} = 0,6 a_n + 0,1$ pour tout entier naturel $n$.
\item On considère la suite $w$ telle que $w_n=a_n-0,25$ pour tout entier naturel $n$.
\begin{questions}
\item Démontrer que la suite $w$ est géométrique.
\item En déduire que $a_n = 0,25 + 0,55 × 0,6^n$ pour tout entier naturel $n$.
\item Calculer la limite de $a_n$ quand $n$ tend vers $+\infty$.

Comment interpréter cette limite ?
\item Déterminer après combien de mois la popularité de la personnalité sera inférieure à 25,1\,\%.
\end{questions}
\end{questions}
\end{exo}

% CORR EX19

\begin{corrige}
\subsubsectionnn{Partie A}
\begin{questions}
\item $P_0=\begin{pmatrix}0,8  &  0,2\end{pmatrix}$ d'après l'énoncé.
\item On note F l'état \og favorable à la personnalité \fg{} et NF l'état \og non favorable à la personnalité \fg.

Le graphe est alors :
\begin{center}
\includegraphics{11_fig_04}
\end{center}

\item
\begin{questions}
\item D'après l'énoncé et le graphe ci-dessus, $M = \begin{pmatrix}
0,7 & 0,3\\
0,1 & 0,9
\end{pmatrix}$.
\item $P_2 = P_0 × M² = \begin{pmatrix}0,448 & 0,552\end{pmatrix}$.
\end{questions}

\item L'état stable $P = \begin{pmatrix}x & y\end{pmatrix}$ vérifie : $P × M = P$. On a donc :
\begin{align*}
\begin{cases}
0,7x+0,1y=x\\
0,3x+0,9y=y\\
x+y=1
\end{cases} & \iff \begin{cases}
0,3x=0,1y\\
x+y=1
\end{cases} \\ & \iff \begin{cases}
y=3x\\
x=\dfrac{1}{4}
\end{cases} \\ & \iff \begin{cases}
x=\dfrac{1}{4}\\[8pt]
y = \dfrac{3}{4}
\end{cases}
\end{align*}
L'état stable est donc $P=\begin{pmatrix}0,25 & 0,75\end{pmatrix}$.

On en déduit qu'au bout d'un grand nombre de mois, il y aura 25\,\% de personnes favorables à la personnalité et 75\,\% de personnes défavorables à la personnalité.
\end{questions}

\subsubsectionnn{Partie B}

\begin{questions}
\item On a $P_{n+1} = P_n × M$.

Donc $a_{n+1} = 0,7a_n + 0,1b_n$. De plus, $a_n + b_n = 1$.

On a donc $a_{n+1} = 0,7a_n + 0,1(1 - a_n) = 0,6a_n + 0,1$.

\item \enlargethispage*{2em}
\begin{questions}
\item  $\begin{aligned}[t]
w_{n+1} & = a_{n+1}-0,25\\
& = 0,6a_n + 0,1 - 0,25\\
& = 0,6(w_n + 0,25) - 0,15 \\
&= 0,6w_n.
\end{aligned}$ 

Donc $w$ est une suite géométrique de raison 0,6.

\item $w$ étant géométrique, on a $w_n = w_0\times q^n$, $q$ étant la raison, ici 0,6.

$w_0 = a_0 - 0,25 = 0,55$.

On a donc, pour tout entier naturel $n$, $w_n = 0,55 × 0,6^n$.

Par conséquent, $a_n = w_n + 0,25 = 0,25 + 0,55 × 0,6^n$.

\item $0 < 0,6 < 1$ donc $\lim\limits_{n\to+\infty}0,6^n=0$, donc $\lim\limits_{n\to+\infty} a_n=0,25$.

Cela signifie qu'au bout d'un grand nombre de mois, le pourcentage de personnes favorables à la personnalité sera 25\,\%. On retrouve le résultat obtenu par la recherche de l'état stable.

\item $\begin{aligned}[t]
a_n<25,1\% & \iff 0,25+0,55\times0,6^n<0,251\\
& \iff 0,55\times0,6^n<0,001\\
& \iff 0,6^n<\dfrac{1}{550}\\
& \iff n\ln0,6<\ln\left(\dfrac{1}{550}\right)\\
& \iff n>\dfrac{\ln\left(\frac{1}{550}\right)}{\ln0,6}\quad\text{car }\ln0,6<0.
\end{aligned} $

Ceci est réalisé si $n$, nombre entier, est au moins égal à 13. Il faudra donc 13 mois pour que la popularité soit inférieure à 25,1\,\%.
\end{questions}
\end{questions}
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\thumb
\AfficheCorrige

\endinput
