\thumb

\begin{qcm}{Vérification de connaissances}{5} % titre , temps
\label{exo:05-qcm1}
On considère le graphe $\cal G$ dont la représentation sagittale est la suivante:
\begin{figure}
\begin{center}
\includegraphics{150_04-graphe-exo-qcm1}
\figcaption{Représentation sagittale du graphe $\cal G$}
\end{center}
\end{figure}

\Par

Pour chacune des questions suivantes, plusieurs propositions de réponses sont faites dont une seule est correcte. Laquelle ?

\begin{questions}
\item L'ordre de $\cal G$ est égal à:

\begin{tabularx}{\linewidth}{@{}XX@{}}
\choix 9 & \choix 8
\end{tabularx}

\item Le graphe $\cal G$ est:\resetchoix

\begin{tabularx}{\linewidth}{@{}XX@{}}
\choix orienté & \choix non orienté
\end{tabularx}

\item Le graphe $\cal G$ est:\resetchoix

\begin{tabularx}{\linewidth}{@{}XX@{}}
\choix cyclique & \choix non cyclique
\end{tabularx}

\item Le graphe $\cal G$ est:\resetchoix

\begin{tabularx}{\linewidth}{@{}XX@{}}
\choix connexe & \choix non connexe
\end{tabularx}

\item La matrice d'adjacence de $\cal G$ est:\resetchoix
\end{questions}

\begin{minipage}{0.5\linewidth}
\begin{center}
\NiceMatrixOptions{code-for-first-row=\color{DB}\scriptstyle,code-for-last-col=\color{DB}\scriptstyle}
$M = \begin{pNiceMatrix}[first-row,last-col=9]
A  & B & C & D & E & F & G & H\\
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & A\\
1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & B\\
1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & C\\
0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & D\\
0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & E\\
0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & F\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & G\\
0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & H
\end{pNiceMatrix}$

\choix
\end{center}
\end{minipage}
\begin{minipage}{0.5\linewidth}
\begin{center}
\NiceMatrixOptions{code-for-first-row=\color{DB}\scriptstyle,code-for-last-col=\color{DB}\scriptstyle}
$M = \begin{pNiceMatrix}[first-row,last-col=9]
A  & B & C & D & E & F & G & H\\
0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & A\\
1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & B\\
1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & C\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & D\\
0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & E\\
0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & F\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & G\\
0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & H
\end{pNiceMatrix}$

\choix
\end{center}
\end{minipage}
\end{qcm}

\begin{corrige}
\begin{questions}
\item Réponse \choix[b]. L'ordre d'un graphe est le nombre de sommets qu'il\linebreak comporte. Donc ici, c'est 8.

\item Réponse \choix[b]. Le graphe est en effet non orienté car aucun sens n'est spécifié pour passer d'un sommet à un autre.

\item Réponse \choix[b]. Le graphe n'est en effet pas cyclique car il n'existe aucun chemin reliant le sommet D, par exemple, à lui-même. Il en est de même pour le sommet G.

\item Réponse \choix[a]. Le graphe est en effet connexe car il n'existe pas de\linebreak sommets isolés (non reliés à au moins l'un des autres sommets).

\item Réponse \choix[b]. La seule chose qui change entre les deux matrices\linebreak proposées est la diagonale principale, qui ne comporte que des \og 1 \fg{} pour la 1\iere{} et que des \og 0 \fg{} pour la 2\up{nde}. Dans la mesure où le graphe ne \linebreak comporte pas de boucle, il ne doit pas y avoir de \og 1 \fg{} sur cette diagonale. La première matrice ne convient donc pas.\end{questions}
\end{corrige}

\newpage

\sectionnn{Théorie}

%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Le plan de ville}{Lycée André Theuriet, Civray}{1}{15} 
Voici le plan simplifié du centre ville d'Aix-en-Provence:

\begin{figure}
\begin{center}
\includegraphics{151_04-graphe-exo-ville-01}
\figcaption{Plan du centre ville d'Aix-en-Provence}
\end{center}
\end{figure}

Représenter ce centre ville sous forme de graphe en considérant que chaque sens giratoire et chaque intersection de rues est un sommet, et que chaque route est une arête.

On supposera qu'il n'y a pas de rue à sens unique et que le graphe peut être par conséquent non orienté.

Quelles caractéristiques a ce graphe ?

\Par

Donner un chemin pour aller du point marqué \og Vous êtes ici \fg{} à la sortie indiquée par la flèche afin de passer par le moins d'intersections possible ?
\end{exo}

\begin{corrige}
Il n'y a rien de bien compliqué dans ce que l'on nous demande ici. Le travail est juste long...

D'abord, on doit repérer tous les sommets :

\Par\enlargethispage*{\baselineskip}

\begin{figure}
\begin{center}
\includegraphics{162_04-graphe-exo-ville-02}
\figcaption{Marquage des intersections}
\end{center}
\end{figure}

\Par

Nous avons ici nommé les sommets par des nombres car il y en a plus de 26, mais nous aurions pu les nommer $S_1$, $S_2$, etc.

Ensuite, nous simplifions le plan en mettant les arêtes:

\Par

\begin{figure}
\begin{center}
\includegraphics{163_04-graphe-exo-ville-03}
\figcaption{Ajout des arêtes}
\end{center}
\end{figure}

\Par

On peut dire de ce graphe qu'il est :
\begin{itemize}
\item connexe (car aucun sommet n'est isolé);
\item acyclique (il n'y a pas de cycle pour le sommet 1 par exemple);
\item les sommets 30 et 20, ainsi que les sommets 54 et 55, sont reliés par deux arêtes et ce sont les seuls sommets dans ce cas.
\end{itemize}

Pour ce qui est d'un chemin pour rejoindre la sortie, nullement besoin d'un programme : on peut voir que le chemin:
\begin{center}
\ttfamily 1 -- 2 -- 11 -- 33 -- 34 -- 41 -- 49 -- 54 -- 55 -- 57
\end{center}
convient, avec seulement 8 intersections entre les sommets 1 et 57.

Ce n'est pas le seul car on peut remplacer 34 par 35, mais ce sont les deux seuls chemins qui répondent à notre exigence.
\end{corrige}

%%%%%%%%%%%%%%%%%%%%

\begin{exo}{La maison piégée}{Lycée Jean Macé, Niort}{2}{20} 
\label{exo:05-maison}
Une maison comporte quatre entrées et est composée de plusieurs pièces, certaines sans danger et d'autres qui sont piégées. Dans l'une des pièces sans danger se trouve une récompense (voir schéma page suivante).
\begin{questions}
\item Représenter cette maison à l'aide d'un graphe le plus simple possible,  permettant de trouver l'entrée la plus optimisée et le chemin le plus court pour aller à la pièce \og récompense \fg{} en évitant tous les pièges.

\item Trouver ce chemin optimal.
\end{questions}

\begin{figure}
\begin{center}
\includegraphics{152_04-graphe-exo-maison-01}
\figcaption{Carte de la maison piégée}
\end{center}
\end{figure}
\end{exo}

\begin{corrige}
\begin{questions}
\item Il semble assez évident de représenter ici les pièces par des sommets et les couloirs par des arêtes. La seule question éventuellement épineuse est de savoir comment représenter les pièces piégées. Dans la mesure où l'on souhaite un graphe le plus simple possible, et comme il ne faut pas aller dans ces pièces, il suffit de les ignorer : le graphe ne va donc pas contenir de sommets représentant les pièces piégées.

De plus, le graphe est non orienté car nullement question de sens dans les déplacements à l'intérieur de cette maison.

\Par

Avant de construire le graphe, enlevons donc les pièces piégées.
\Par
\begin{figure}
\begin{center}
\includegraphics{164_04-graphe-exo-maison-02}
\figcaption{Carte simplifiée de la maison}
\label{graphe-maison}
\end{center}
\end{figure}

\Par

Nous voyons alors que l'on peut encore simplifier le problème car\linebreak plusieurs pièces se trouvent sur un même chemin non ramifié, pièces que l'on a réunies sur la figure \ref{graphe-maison} en orange en \og groupes \fg{} : A, E, G, F et H.

L'idée ici est de regrouper les pièces n'ayant qu'une entrée et une sortie : par exemple, la pièce B comporte trois connexions, donc elle ne fait pas partie d'un groupe.  La pièce C comporte bien deux connexions mais aucune de ses deux pièces adjacentes (B et D) n'est, comme elle, limitée à deux connexions. C ne peut donc pas faire partie d'un groupe car elle ne peut pas en constituer un avec ses voisins.

Le problème peut donc se représenter par le graphe suivant :

\Par
\begin{figure}
\begin{center}
\includegraphics{164_04-graphe-exo-maison-03}
\figcaption{Graphe représentant la maison}
\end{center}
\end{figure}

\newpage

\item On déduit du graphe précédent que le chemin le plus court pourrait être  :

\begin{center}
A -- B -- C -- D -- F \quad ou  \quad G -- B -- C -- D -- F
\end{center}
\enlargethispage*{3em}

mais en regardant sur le schéma original de la maison, seul le chemin\linebreak A -- B -- C -- D -- F convient, ce qui correspond au chemin page ci-contre dans la maison.
\Par
\begin{figure}
\begin{center}
\includegraphics{165_04-graphe-exo-maison-04}
\figcaption{Chemin le plus court}
\label{graphe-maison}
\end{center}
\end{figure}
\end{questions}
\end{corrige}

%%%%%%%%%%%%%%%%%%%

\subsectionnn{Plus court chemin}

\begin{exo}{Le loup et compagnie...}{Lycée François Villon, Les Mureaux}{1}{15} 
\label{exo:05-loup}
Sur la rive d'un fleuve se trouvent un loup, une chèvre, un chou et un passeur.

Le problème consiste à faire tous les faire passer sur l'autre rive à l'aide d'une barque, menée par le passeur, en respectant les règles suivantes:
\begin{itemize}
\item la chèvre et le chou ne peuvent pas rester sur la même rive sans le passeur,
\item de même pour la chèvre et le loup,
\item le passeur ne peut mettre qu'un seul \og passager \fg{} avec lui.
\end{itemize}

On décide de représenter le passeur par la lettre $P$, la chèvre par $C$, le loup par $L$ et le chou par $X$.

\begin{questions}
\item Représenter ce problème à l'aide d'un graphe où les sommets sont tous les états possibles sur la rive de départ (par exemple, \og $PLCX$ \fg est un sommet représentant le fait que tous sont sur la rive de départ).
\item Trouver alors une solution au problème en indiquant chacun des\linebreak déplacements.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item 
\begin{methode}
Dans ce genre de problème, il est bon d'énumérer tous les états qui font intervenir \og P \fg{}:
\begin{center}
\og PLCX \fg{} , \og PLC \fg{} , \og PLX \fg{} , \og PCX \fg{} et \og PC \fg.
\end{center}
et sans \og P \fg (en tenant compte des contraintes):
\begin{center}
\og LX \fg{} , \og L \fg{} , \og C \fg{} , \og X \fg{}  et \og vide \fg.
\end{center}
Ce dernier état signifie que la rive est vide, et donc que le problème est résolu.
\end{methode}

Le graphe doit traduire les différents déplacements possibles entre chaque état. On peut alors avoir une représentation sagittale qui ressemble à la suivante:

\Par

\begin{figure}
\begin{center}
\includegraphics{165_04-graphe-exo-loup}
\figcaption{Représentation du problème}
\end{center}
\end{figure}

\item Résoudre le problème revient alors à trouver un chemin du sommet \og PLCX \fg{} au sommet \og vide \fg. On obtient alors, par exemple:

\begin{center}
PLCX $\to$ LX $\to$ PLX $\to$ X $\to$ PCX $\to$ C $\to$ PC $\to$ vide.
\end{center}

Cela signifie que:
\begin{itemize}
\item au départ, le passeur amène la chèvre sur la rive de destination, laissant le loup et le chou sur la rive de départ;
\item le passeur revient et se retrouve avec le loup et le chou;
\item il amène le loup sur la rive de destination, laissant le chou;
\item il ramène la chèvre sur la rive de départ car elle ne peut rester avec le loup sur la rive de destination;
\item il amène le chou sur la rive de destination, laissant la chèvre seule;
\item il revient seul car le loup et le chou peuvent rester ensemble sur la rive de destination;
\item il se retrouve donc avec la chèvre sur la rive de départ, et l'amène sur l'autre rive.
\end{itemize}
\end{questions}
\end{corrige}


%%%%%%%%%%%%%%%

\begin{exo}{Algorithme de Dijkstra}{Lycée Jean-Joseph Fourier, Auxerre}{2}{10} 
On considère le graphe suivant:

\Par\Par

\begin{figure}
\begin{center}
\includegraphics{153_04-graphe-exo-dijkstra}
\figcaption{Graphe orienté pondéré}
\end{center}
\end{figure}

\Par\Par

\begin{questions}
\item Appliquer l'algorithme de Dijkstra à ce graphe en partant du sommet A.
\item Montrer que la distance entre A et D obtenue n'est pas minimale.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item On a le tableau suivant:
\Par

\hspace*{-5mm}
\begin{tabular}{|C|*8{Zc|}}
\tabulartitle\hline
M & L[A] & L[B] & L[C] & L[D] & P[A] & P[B] & P[C] & P[D]\\
\hline
A & 0 & 1 & 2 & $\infty$ & - & A & A & - \\
\hline
A,B & 0 & 1 & 2 & 3 & - & A & B & B\\
\hline
A,B,C,D & 0 & -3 & 2 & 3 & - & C & A & B\\
\hline
\end{tabular}


\item La distance obtenue de A à D est égale à 3 avec l'algorithme de Dijkstra. Or, nous voyons bien que le chemin A -- C -- B -- D a un poids total de $2-5+2=-1$ et que ce poids est minimal.

La raison de ce \og bug \fg{} est que le sommet C a été traité après le sommet B; or, le poids de C à B étant négatif, L[B] a été mis à jour. L'algorithme de Dijkstra ne traitant qu'une seule fois un sommet, cela n'a pas pu entraîner la mise à jour de L[D].

C'est le problème de cet algorithme quand il y a des poids négatifs.
\end{questions}
\end{corrige}



%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Le politicien}{Lycée Henri Alain-Fournier, Bourges}{2}{15} 
Un politicien se trouve à sa permanence (en P) et doit se rendre à l'hôpital (en H) le plus rapidement possible.

Le graphe ci-dessous représente le temps de trajet pour aller d'un point à un autre.

\Par

\begin{figure}
\begin{center}
\includegraphics{153_04-graphe-exo-dijkstra2}
\figcaption{Graphe pondéré par les temps de trajet}
\end{center}
\end{figure}

\Par

Quel chemin doit-il emprunter pour y arriver au plus vite ?
\end{exo}

\begin{corrige}
On utilise l'algorithme de Dijkstra en indiquant chaque étape dans une ligne du tableau page suivante.
\Par
Dans la colonne \og H \fg, on voit qu'il y a deux chemins qui mènent à ce sommet; on prend celui qui a la plus petite pondération.
\Par
La dur\'ee minimale est donc de 29 minutes avec le trajet:
\[
\rm P \to B \to D \to G \to H.
\]
\begin{Remarque}
notons que le \og 11 (P) \fg{} a été reporté et non le \og 11 (A) \fg{} car il a été considéré avant. C'est une règle générale : on reporte toujours ce qui a été considéré en premier.
\end{Remarque}
\begin{center}
\begin{tabularx}{\linewidth}{|*9{>{\centering\arraybackslash}X|}}
\tabulartitle\hline
P & A & B & C & D & E & F &  G& H\\
\hline
$\times$  & 
4 (P)  &  
\tikz[remember picture,overlay] 
\node (B) {6 (P)}; &  
\tikz[remember picture,overlay] 
\node (C) {11 (P)}; &  
12 (P)  &  & & &   \\
\hline
$\times$  & \cellcolor{LB} 4 (P)  & 7 (A)  &  11 (A) &   &   &  & &  \\
\hline
$\times$  & $\times$   &  
\cellcolor{LB} 
\tikz[remember picture,overlay] 
\node (B1) {6 (P)}; 
\tikz[remember picture,overlay] \draw[DR,thick,->,>=latex] (B.west) to[bend right=30] (B1.west);   &   & 10 (B)  &   &  && \\
\hline
$\times$  & $\times$   &  $\times$  &   & \cellcolor{LB} 10 (B)  &   & \tikz[remember picture,overlay] 
\node (F) {15 (D)}; & \tikz[remember picture,overlay] 
\node (G) {19 (D)}; &  \\
\hline
$\times$  & $\times$   & $\times$   &  \cellcolor{LB} 
\tikz[remember picture,overlay] 
\node (C1) {11 (P)}; 
\tikz[remember picture,overlay] \draw[DR,thick,->,>=latex] (C.west) to[bend right=30] (C1.west);  & $\times$  &  \tikz[remember picture,overlay] 
\node (E) {22 (C)};  &  & 21 (C) &  \\
\hline
$\times$  & $\times$   & $\times$   &  $\times$ & $\times$  &   & \cellcolor{LB} \tikz[remember picture,overlay] \node (F1) {15 (D)}; \tikz[remember picture,overlay] \draw[DR,thick,->,>=latex] (F.west) to[bend right=30] (F1.west);   & 23 (F) &   \\
\hline
$\times$  & $\times$   & $\times$   &  $\times$ & $\times$  &   & $\times$  & \cellcolor{LB} 
\tikz[remember picture,overlay] 
\node (G1) {19 (D)}; 
\tikz[remember picture,overlay] \draw[DR,thick,->,>=latex] (G.west) to[bend right=30] (G1.west);  &  \\
\hline
$\times$  & $\times$   & $\times$   &  $\times$ & $\times$  &   & $\times$  & $\times$  & 29 (G) \\
\hline
$\times$  & $\times$   & $\times$   &  $\times$ & $\times$  & \cellcolor{LB} \tikz[remember picture,overlay] 
\node (E1) {22 (C)}; 
\tikz[remember picture,overlay] \draw[DR,thick,->,>=latex] (E.west) to[bend right=30] (E1.west);  & $\times$  & $\times$  & 31 (E) \\
\hline
\end{tabularx}
\end{center}
\end{corrige}

\sectionnn{Implémentation}


\begin{exo}{Matrice d'adjacence aléatoire}{Lycée Sophie Germain, Paris}{1}{5} 
\'Ecrire une fonction en Python admettant un paramètre entier $n$ et permettant de créer une matrice d'adjacence aléatoire de dimensions $n \times n$.
\end{exo}

\begin{corrige}
\begin{methode}
\og aléatoire \fg{} implique souvent \og appel au module random \fg. De plus, on exploite le fait qu'une matrice d'adjacence est carrée, ne comporte que des \og 0 \fg{} et des \og 1 \fg, que sa diagonale principale est remplie de 0 et qu'elle est symétrique par rapport à la diagonale principale. 
\end{methode}

Une fonction possible est alors celle donnée page suivante.

L'idée est donc ici d'initialiser une matrice de dimensions $n\times n$ remplie par exemple de \og 0 \fg.

Ensuite, pour chaque ligne (\texttt{for ligne in range(n)}), on parcourt chaque colonne : si on est au-dessus de la diagonale principale (\texttt{if colonne > ligne}) alors on choisit un coefficient au hasard entre 0 et 1. Si on est au contraire en dessous, le coefficient doit être égal à son symétrique par rapport à la diagonale principale (\texttt{M[ligne][colonne] = M[colonne][ligne]}).

Inutile de faire le cas où \texttt{ligne == colonne} car dans ce cas, le coefficient doit être nul, ce qui est déjà le cas par construction initiale de la matrice.

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/05-matadjalea.py}}}
\vspace*{-10pt}
\begin{listing}{}{05-matadjalea.py}\end{listing}

\end{corrige}

%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Par matrice d'adjacence}{Lycée Camille Jullian, Bordeaux}{2}{15} 
\label{exo:implementation-graphe-matrice-adj}
On considère le graphe de sommets A, B, C, D, E et F dont la matrice\linebreak d'adjacence est la suivante:
\[
\NiceMatrixOptions{code-for-first-row=\color{DB}\scriptstyle,code-for-last-col=\color{DB}\scriptstyle}
M = \begin{pNiceMatrix}[first-row,last-col=7]
A  & B & C & D & E & F\\
0 & 1 & 1 & 0 & 1 & 0 & A\\
1 & 0 & 1 & 1 & 0 & 1 & B\\
1 & 0 & 0 & 1 & 1 & 1 & C\\
0 & 1 & 1 & 0 & 1 & 0 & D\\
1 & 0 & 1 & 1 & 0 & 1 & E\\
0 & 1 & 1 & 0 & 1 & 0 & F
\end{pNiceMatrix}
\]
À l'aide de $M$, implémenter ce graphe par liste d'adjacence.
\end{exo}

\begin{corrige}
On pourrait implémenter ce graphe \og à la main \fg{} à l'aide de la classe \texttt{Graphe} donnée page \pageref{graphes-classe}, en énumérant toutes les arêtes grâce à la matrice d'adjacence donnée, mais si on pouvait implémenter une façon de passer de la
matrice d'adjacence à une liste d'adjacence, 
ce serait mieux.

Le programme page suivante répond à cette requête.

\Par

\begin{minipage}{0.5\linewidth}
Il affiche :

\Par

{\ttfamily
B : ['C', 'D', 'F']

A : ['B', 'C', 'E']

C : ['D', 'E', 'F']

E : ['F']

D : ['E']

F : []
}
\end{minipage}
\begin{minipage}{0.5\linewidth}
\[
\NiceMatrixOptions{code-for-first-row=\color{DB}\scriptstyle,code-for-last-col=\color{DB}\scriptstyle}
M = \begin{pNiceMatrix}[first-row,last-col=7,name=matrice]
A  & B & C & D & E & F\\
0 & 1 & 1 & 0 & 1 & 0 & A\\
1 & 0 & 1 & 1 & 0 & 1 & B\\
1 & 0 & 0 & 1 & 1 & 1 & C\\
0 & 1 & 1 & 0 & 1 & 0 & D\\
1 & 0 & 1 & 1 & 0 & 1 & E\\
0 & 1 & 1 & 0 & 1 & 0 & F
\end{pNiceMatrix}
\]
\newcounter{x}
\multido{\i=1+1}{6}{%
\setcounter{x}{7-\i}
\multido{\n=\i+1}{\thex}{%
\tikz[remember picture,overlay] \draw (matrice-\i-\n) circle (2mm) ;
}}
\end{minipage}
\Par
En effet, une arête est créée entre les sommets $i$ et $j$ si le coefficient $m_{ij}$ est égal à 1. Il suffit donc de faire deux boucles, sur $i$ et $j$ (où $i$ représente la ligne et $j$ la colonne de la matrice) et d'effectuer un test de valeur pour savoir si on doit créer une arête ou non.

De plus, on sait que la matrice d'adjacence est toujours symétrique par\linebreak rapport à sa diagonale principale. Il est donc inutile d'effectuer ces tests pour les coefficients $m_{ij}$ avec $j < i$.

\newpage

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/05-matadj.py}}}
\vspace*{-10pt}
\begin{listing}{}{05-matadj.py}\end{listing}
\end{corrige}

%%%%

\begin{exo}{Flux migratoires}{Lycée polyvalent Émile Zola, Aix-en-Provence}{2}{20} 
Une région est composée de trois départements que l'on notera X, Y et Z.

Chaque année,
\begin{itemize}
\item 5  \% des habitants du département X déménagent pour le département Y;
\item 1  \% des habitants du département X déménagent pour le département Z;
\item 7  \% des habitants du département Y déménagent pour le département X;
\item 3  \% des habitants du département Y déménagent pour le département Z;
\item 2  \% des habitants du département Z déménagent pour le département X;
\item 4  \% des habitants du département Z déménagent pour le département Y;
\item 1  \% des habitants du département X déménagent pour une autre région;
\item 3  \% des habitants du département Y déménagent pour une autre région;
\item 2 \% des habitants du département Z déménagent pour une autre région.
\item On suppose que le pourcentage d'habitants des autres régions qui\linebreak aménagent dans un des départements X, Y ou Z est assez faible pour\linebreak l'assimiler à 0.
\end{itemize}

\enlargethispage*{3em}
\begin{questions}
\item Représenter ces flux migratoires à l'aide d'un graphe (on n'oubliera pas les personnes restant dans leur département).
\item Donner la matrice de transition $M$ de ce graphe.
\item À l'aide de \texttt{numpy}, implémenter $M$.
\item À l'aide du module \texttt{numpy.linalg} et de  \texttt{matrix}\_\texttt{power}, déterminer $M^{10}$.
\item En 2019, un recensement a établi qu'il y avait:
\begin{itemize}
\item 1,081 million d'habitants dans le département X, 
\item 1,076 million d'habitants dans le département Y,
\item 0,327 million d'habitants dans le département Z,
\item 67 millions d'habitants dans le pays.
\end{itemize}

On note $P_0=\begin{pmatrix}1,081 & 1,076 & 0,327 & 64,516
\end{pmatrix}$ la matrice ligne\linebreak représentant l'état initial.

On suppose que le nombre d'habitants dans chaque département au bout de $n$ années est donné par la matrice $P_n = P_0 \times M^n=\begin{pmatrix}
x_n & y_n & z_n & a_n\end{pmatrix}$, où $x_n$, $y_n$ et $z_n$ représentent respectivement le nombre d'habitants des\linebreak départements X, Y et Z (et où $a_n$ représente le nombre d'habitants dans les autres régions).

À l'aide de la fonction \texttt{dot} de \texttt{numpy}, qui permet de calculer le produit de deux matrices, déterminer $x_{10}$, $y_{10}$ et $z_{10}$.

\item \'Ecrire un programme permettant de voir l'évolution du nombre\linebreak d'habitants dans chaque département au cours des 200 années à venir. Que constate-t-on ? Quelles conclusions peut-on faire ?
\end{questions}
\end{exo}

\begin{corrige}
\enlargethispage*{\baselineskip}
\begin{questions}
\item Dans la mesure où certains habitants déménagent vers une autre\linebreak région, nous allons représenter les flux migratoires par un graphe à quatre\linebreak sommets : X, Y, Z et A (où A représentera tout ce qui n'est pas dans la région).

De plus, le graphe doit être orienté (car le mouvement X $\to$ Y n'est pas similaire au mouvement Y $\to$ X) et pondéré (par les pourcentages, mis en décimaux par exemple). Il ne faut pas oublier les pourcentages non indiqués dans l'énoncé, à savoir ceux correspondants aux habitants qui restent dans leur département.

On a alors la représentation sagittale suivante:

\Par

\begin{figure}
\begin{center}
\includegraphics{170_04-graphe-exo-flux}
\figcaption{Représentation des flux migratoires}
\end{center}
\end{figure}

\item La matrice de transition de ce graphe est:
\[
\NiceMatrixOptions{code-for-first-row=\color{DB}\scriptstyle,code-for-last-col=\color{DB}\scriptstyle}
M = \begin{pNiceMatrix}[first-row,last-col=5,name=flux]
X & Y & Z & A\\
0,93 & 0,05 & 0,01 & 0,01 &  X\\
0,07 & 0,87 & 0,03 & 0,03  & Y\\
0,02 & 0,04 & 0,92 & 0,02 & Z\\
0 & 0 & 0 & 1 & A
\end{pNiceMatrix}
\]

\item On implémente la matrice de la manière suivante:
\Par
\quad\begin{tabularx}{\linewidth}{@{}|>{\ttfamily}X@{}}
\pychevrons from numpy import *\\
\pychevrons M = array( [\\
\quad    [0.93,0.05,0.01,0.01] ,\\
\quad    [0.07,0.87,0.03,0.03] ,\\
\quad    [0.02,0.04,0.92,0.02] ,\\
\quad    [0,0,0,1]\\
\quad    ] )
\end{tabularx}

\newpage

\item On obtient $M^{10}$ en tapant:
\Par
\quad\begin{tabularx}{\linewidth}{@{}|>{\ttfamily}X@{}}
\pychevrons from numpy.linalg import matrix\_power\\
\pychevrons matrix\_power(M,10)\\
array([[0.56932088, 0.21942888, 0.08467249, 0.12657775],\\
\quad       [0.30805016, 0.33744598, 0.13505622, 0.21944764],\\
\quad       [0.16509636, 0.18149117, 0.46765393, 0.18575854],\\
\quad       [0.        , 0.        , 0.        , 1.        ]])
\end{tabularx}

\item On peut écrire :
\Par
\quad\begin{tabularx}{\linewidth}{@{}|>{\ttfamily}X@{}}
\pychevrons P = array( [ 1.081 , 1.076 , 0.327 , 64.516] )\\
\pychevrons dot( P , matrix\_power(M,10) )\\
array([ 1.00088435,  0.65964211,  0.38977429, 64.94969926])\end{tabularx}
\Par
On obtient ainsi :
\[
x_{10}\approx\numprint{1,000884}\quad,\quad y_{10}\approx\numprint{0,659642}\quad,\quad z_{10}\approx\numprint{0,389774}.
\]

\item Une simple boucle suffit:

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/05-fluxmigratoires-q6.py}}}
\vspace*{-10pt}
\begin{listing}{}{05-fluxmigratoires-q6.py}\end{listing}

\Par\Par

On s'aperçoit alors que les nombres d'habitants des départements X, Y et Z ne font que décroitre, ce qui nous laisse à penser que ces départements se dépeuplent et qu'à long terme, ils seront désertés si aucun plan n'est adopté pour remédier à cette migration.
\end{questions}

\newpage

%\begin{aretenir}
%Les graphes sont très souvent utilisés pour traduire des changements d'états :
%\begin{itemize}
%\item mouvement d'un solide vers plusieurs endroits, 
%\item changement d'état d'un objet (marche, arrêt, veille, etc.),
%\item changement climatique,
%\item etc.
%\end{itemize}
%Le graphe ainsi obtenu est appelé \textit{graphe probabiliste} et la matrice de transition permet d'obtenir, lorsque $n$ tend vers $+\infty$, une matrice $M^n$ dont chaque colonne représente la probabilité des états. Dans la pratique, on prendra $n$ assez grand. Nous en parlons dans l'exercice suivant.
%\end{aretenir}
\end{corrige}


%%%%%%%%%%%%%%%%

\begin{exo}{Une simple histoire de temps}{Lycée Sainte-Clotilde, Strasbourg}{2}{20} 
Dans un pays imaginaire, si le temps d'un jour est pluvieux ou neigeux, alors il reste inchangé dans 50  \% des cas le lendemain et ne devient beau que dans 25  \% des cas. Lorsque le temps est beau, le lendemain il est pluvieux ou neigeux de manière équiprobable mais il ne restera pas ensoleillé deux jours à la suite.

Les habitants affirment qu'il ne fait beau qu'un jour sur cinq. Ont-ils raison ?

Pour répondre à cette question, on pourra:
\begin{itemize}
\item établir le graphe représentant les changements climatiques;
\item déterminer sa matrice de transition $M$;
\item s'aider de Python, et plus particulièrement de \texttt{numpy}, pour déterminer la probabilité qu'il fasse beau un jour donné en calculant une puissance de $M$ assez grande.
\end{itemize}
\end{exo}

\begin{corrige}
\begin{itemize}
\item Commençons par représenter les changements climatiques à l'aide d'un graphe:
\Par
\begin{figure}
\begin{center}
\includegraphics{172_04-graphe-exo-temps}
\figcaption{Représentation des changements climatiques}
\end{center}
\end{figure}

\item La matrice de transition de ce graphe est:
\[
\NiceMatrixOptions{code-for-first-row=\color{DB}\scriptstyle,code-for-last-col=\color{DB}\scriptstyle}
M = \begin{pNiceMatrix}[first-row,last-col=4,name=weather]
N & P & S \\
0,5 & 0,25 & 0,25 &  N\\
0,25 & 0,5 & 0,25  & P\\
0,5 & 0,5 & 0 & S
\end{pNiceMatrix}
\]

\item On implémente alors la matrice de la manière suivante:
\Par
\quad\begin{tabularx}{\linewidth}{@{}|>{\ttfamily}X@{}}
\pychevrons from numpy import *\\
\pychevrons M = array( [\\
\quad    [0.5,0.25,0.25] ,\\
\quad    [0.25,0.5,0.25] ,\\
\quad    [0.5,0.5,0] ,
\quad    ] )
\end{tabularx}

\item On calcule par exemple $M^{100}$ :
\Par
\quad\begin{tabularx}{\linewidth}{@{}|>{\ttfamily}X@{}}
\pychevrons from numpy.linalg import matrix\_power\\
\pychevrons matrix\_power(M,100)\\
array([[0.4, 0.4, 0.2],\\
\quad       [0.4, 0.4, 0.2],\\
\quad       [0.4, 0.4, 0.2]])
\end{tabularx}
\end{itemize}

Cette dernière matrice nous dit alors que la probabilité qu'il fasse beau à long terme est égale à 0,2 (par rapport à l'ordre que nous avons choisi, on regarde la dernière colonne), soit un jour sur cinq.
\end{corrige}

%%%%%%%%%%%%%%%%

\begin{exo}{Le labyrinthe}{Lycée Camille Jullian, Bordeaux}{3}{30}
\label{exo:05-labyrinthe}
\index{Labyrinthe}
Le \og labyrinthe de Pan \fg est une attraction d'une fête foraine : c'est un\linebreak labyrinthe dont les murs intérieurs sont des miroirs. Le plan de ce labyrinthe est donné ci-dessous sur une grille:

\Par

\begin{figure}
\begin{center}
\includegraphics{156_04-graphe-exo-labyrinthe-01}
\figcaption{Plan du \og Labyrinthe de Pan \fg}
\end{center}
\end{figure}

\Par

En considérant chaque case comme un sommet de graphe, implémenter ce labyrinthe en Python, puis trouver le chemin le plus court de l'entrée à la sortie.

On pourra pour cela s'aider de la classe \texttt{Graphe} complète téléchargeable à la page \pageref{graphe-classe-complete}.
\end{exo}

\begin{corrige}
\begin{minipage}{0.5\linewidth}
Il existe des méthodes plus économes que celle souhaitée par l'énoncé, comme par exemple la fusion de cases pour réduire le nombre de sommets du graphe représentant le labyrinthe, mais contentons-nous pour l'instant de la méthode la plus évidente : à chaque case son sommet. Notons $S_{i,j}$ le sommet de la case sur la $i$-ième ligne et $j$-ième colonne. 
\end{minipage}
\begin{minipage}{0.5\linewidth}
\begin{center}
Si on fait un zoom\\sur l'entrée,\\ cela donne:
\end{center}

\begin{figure}
\begin{center}
\includegraphics{173_04-graphe-exo-labyrinthe-02}
\figcaption{Zoom sur l'entrée}
\end{center}
\end{figure}
\end{minipage}


\Par

On marque par une arête la présence d'un passage entre 2 cases adjacentes. Par exemple: il n'y a pas d'arête entre S$_{1,1}$ et S$_{1,2}$ mais il y en a une entre S$_{1,1}$ et S$_{2,1}$.

En tout, il aura $11 \times 11 = 121$ sommets. Le graphe est creux car il y aura très peu d'arêtes par rapport au nombre de sommets. Ceci nous pousse à implémenter le graphe par liste d'adjacence.

\Par

\qrset{height=1.1cm,version=5}\rput(-1,0){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/05-labyrinthe.py/}}}
\textit{Téléchargez l'implémentation complète.}

\Par

À l'aide de ce programme, on voit que le plus court chemin est le suivant, de longueur 36 (nombre d'arêtes):

\begin{center}
\ttfamily

'S1-1', 'S2-1', 'S2-2', 'S2-3', 'S3-3', 'S4-3', 'S4-4', 'S4-5', 'S5-5', 'S5-4', 'S6-4', 'S6-5', 'S6-6', 'S7-6', 'S7-7', 'S8-7', 'S8-6', 'S8-5', 'S9-5', 'S9-4', 'S9-3', 'S9-2', 'S9-1', 'S10-1', 'S11-1', 'S11-2', 'S11-3', 'S11-4', 'S11-5', 'S11-6', 'S11-7', 'S11-8', 'S10-8', 'S10-9', 'S11-9', 'S11-10', 'S11-11'
\end{center}

Cela correspond au chemin suivant:\enlargethispage*{5em}

\Par

\begin{center}
\includegraphics{173_04-graphe-exo-labyrinthe-03}
\figcaption{Chemin le plus court}
\end{center}
\end{corrige}

\sectionnn{Objectif bac}

%%% NEW 2025

\begin{exo}{Recette}{Lycée Richelieu, Versailles}{3}{45}
On s'intéresse à la fabrication de pain. La recette est fournie sous la forme de tâches à réaliser page ci-contre. Cette recette est réalisée par une personne seule.\resetchoix

\newpage

\begin{itemize}
    \item[\choix] Préparer 500 g de farine.
    \item[\choix] Préparer $1 / 3$ de litre d'eau (33cl).
    \item[\choix] Préparer 1 c. à café de sel.
    \item[\choix] Préparer 20 g de levure de boulanger.
    \item[\choix] Faire tiédir l'eau dans une casserole.
    \item[\choix] Délayer la levure dans l'eau tiède.
    \item[\choix] Laisser reposer la levure 5 minutes.
    \item[\choix] Préparer un grand saladier.
    \item[\choix] Verser la farine dans le saladier.
    \item[\choix] Verser le sel dans le saladier.
    \item[\choix] Mélanger la farine et le sel puis creuser un puits.
    \item[\choix] Verser l'eau mélangée à la levure dans le puits.
    \item[\choix] Pétrir jusqu'à obtenir une pâte homogène.
    \item[\choix] Couvrir à l'aide d'un linge humide et laisser fermenter au moins 1h30.
    \item[\choix] Disposer dans le fond du four un petit récipient contenant de l'eau.
    \item[\choix] Préchauffer un four à 200 degrés Celsius.
    \item[\choix] Fariner un plan de travail.
    \item[\choix] Verser la pâte à pain sur le plan de travail.
    \item[\choix] Pétrir rapidement la pâte à pain.
    \item[\choix] Disposer la pâte dans un moule à cake.
    \item[\choix] Mettre au four pour 15 à 20 minutes, arrêter le four et sortir le pain.
\end{itemize}

La figure \ref{fig:recette_pain} représente les différentes tâches et les dépendances entre ces tâches sous la forme d'un graphe. Chaque sommet du graphe représente une tâche à réaliser. Les dépendances entre les tâches sont représentées par les arcs entre les sommets.

\begin{figure}
    \centering
    \includegraphics{157_recette01}
    \figcaption{Recette du pain : tâches à effectuer avec leurs dépendances}
    \label{fig:recette_pain}
\end{figure}

\begin{questions}
    \item Dire, sans justifier, s'il s'agit d'un graphe orienté ou non orienté.
    \item D'après le graphe, dire s'il est possible d'effectuer les réalisations dans chacun des ordres suivants :
    \begin{questions}
        \item réaliser la tâche (f) puis la tâche (g)
        \item réaliser la tâche (g) puis la tâche (f)
        \item réaliser la tâche (i) puis la tâche (j)
        \item réaliser la tâche (j) puis la tâche (i)
    \end{questions}
    \item Donner toutes les tâches qu'il faut nécessairement avoir réalisées depuis le début pour pouvoir réaliser la tâche (k). Ne donner que les tâches nécessaires.
    \item Indiquer, sans justifier, si le graphe de la Figure \ref{fig:recette_pain} contient un cycle.
\end{questions}

\subsubsectionnn{Graphe de tâches}

On s'intéresse désormais de manière plus générale à un graphe de tâches avec des dépendances.

Les sommets sont nommés par des indices. Comme précédemment, un arc orienté d'un sommet d'indice $i$ à un sommet d'indice $j$ signifie que la tâche représentée par le sommet d'indice $i$ doit être réalisée avant la tâche représentée par le sommet d'indice $j$.

\begin{figure}
    \centering
    \includegraphics{158_recette02}
    \figcaption{Exemple de graphe de dépendances entre 6 tâches}
    \label{fig:graphe_dependances}
\end{figure}

\begin{questions}
\setcounter{enumi}{4}
    \item Déterminer un ordre permettant de réaliser toutes les tâches représentées dans le graphe de la Figure \ref{fig:graphe_dependances} en respectant les dépendances entre les tâches.
\end{questions}

Voici une matrice d'adjacence d'un graphe écrite en langage Python et telle que si $m[i][j]=1$ alors il existe un arc qui va du sommet d'indice $i$ au sommet d'indice $j$. Par exemple, $m[0][1]=1$ alors il existe un arc qui va du sommet d'indice 0 au sommet d'indice 1.

\[
M = \begin{bmatrix}
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}
\]


\begin{questions}
\setcounter{enumi}{5}
    \item Représenter le graphe associé à cette matrice d'adjacence. Les noms des sommets seront leurs indices.
    \item Déterminer s'il est possible de trouver un ordre permettant de réaliser les tâches représentées par le graphe de la question 6 en respectant leurs dépendances. Si oui, donner l'ordre. Si non, expliquer pourquoi.
\end{questions}

On donne le code Python d'une fonction \texttt{mystere}.

\qrset{height=1.1cm,version=5}\rput(-1.2,-1.5){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/05-recette-mystere.py}}}
\vspace*{-10pt}
\begin{listing}[numbers=left,numberstyle=\ttfamily\small\color{DO}]{}{05-recette-mystere.py}\end{listing}

\begin{questions}
\setcounter{enumi}{7}
    \item En utilisant la matrice $M$ donnée précédemment, déterminer si la variable \texttt{ok} vaut \texttt{True} ou \texttt{False} à l'issue des instructions suivantes :
    \begin{verbatim}
    n = len(M)
    ouverts = [False for i in range(n)]
    fermes = [False for i in range(n)]
    ok = mystere(M, 1, n, ouverts, fermes, None)
    \end{verbatim}
    Décrire précisément les appels effectués à la fonction \texttt{mystere} et les valeurs des tableaux \texttt{ouverts} et \texttt{fermes} lors de chaque appel. On pourra recopier et compléter le tableau ci-dessous.
    
    \Par

    \begin{tabular}{|c|c|c|}
        \hline\tabulartitle
        Appel mystere & variable ouverts & variable fermes \\
        \hline
        Avant l'appel mystere & $[F, F, F, F, F]$ & $[F, F, F, F, F]$ \\
        mystere(M, 1,5, $[F, F, F, F, F]$, & $[F, F, F, F, F]$ & $[F, F, F, F, F]$ \\
        mystere(M, 2,5, $[F, T, F, F, F]$, & $[F, T, T, F, F]$ & $[F, F, F, F, F]$ \\
        \ldots &  &  \\
        \hline
    \end{tabular}
    
    \Par
    
    \item De manière générale, expliquer dans quel cas cette fonction \texttt{mystere} renvoie \texttt{False}.
\end{questions}

L'objectif est d'utiliser la fonction \texttt{mystere} pour écrire une fonction\linebreak \texttt{ordre\_realisation} qui, lorsque c'est possible, détermine l'ordre de réalisation des tâches d'un graphe donné par sa matrice d'adjacence en respectant les dépendances entre les tâches.

Une structure de données de pile est représentée par une classe \texttt{Pile} qui possède les méthodes suivantes :
\begin{itemize}
    \item la méthode \texttt{estvide} qui renvoie \texttt{True} si la pile représentée par l'objet est vide, \texttt{False} sinon ;
    \item la méthode \texttt{empiler} qui prend en paramètre un élément et l'ajoute au sommet de la pile ;
    \item la méthode \texttt{depiler} qui renvoie la valeur du sommet de la pile et enlève cet élément.
\end{itemize}


\begin{questions}
\setcounter{enumi}{9}
    \item Déterminer la valeur associée à la variable \texttt{elt} après l'exécution des instructions suivantes :
    \begin{verbatim}
    essai = Pile()
    essai.empiler(3)
    essai.empiler(2)
    essai.empiler(10)
    elt = essai.depiler()
    elt = essai.depiler()
    \end{verbatim}
\end{questions}

Lorsqu'il en existe un, un ordre de réalisation des tâches sera représenté par un objet de classe \texttt{Pile} contenant tous les sommets du graphe de manière à ce que les tâches qu'il faut réaliser en premier se retrouvent au sommet de la pile.

\newpage

La fonction \texttt{ordre\_realisation} est écrite de la manière suivante :

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/05-recette-ordre.py}}}
\vspace*{-10pt}
\begin{listing}{}{05-recette-ordre.py}\end{listing}

\begin{questions}
\setcounter{enumi}{10}
    \item Sachant que dans la fonction \texttt{mystere}, la ligne 24 peut être remplacée par une ou plusieurs instructions, donner ce qu'il faut écrire pour que, lorsque c'est possible, \texttt{ordre\_realisation} renvoie effectivement un ordre de réalisation des tâches du graphe.
\end{questions}

\end{exo}

\begin{corrige}
\begin{questions}
\item Ce graphe est orienté car le passage d'un n\oe ud à l'autre a un sens.
\item 
\begin{questions}
\item Réaliser la tâche (f) puis la tâche (g) : oui.
\item Réaliser la tâche (g) puis la tâche (f) : non.
\item Réaliser la tâche (i) puis la tâche (j) : oui car il n'y a pas de dépendance entre les deux n\oe uds.
\item Réaliser la tâche (j) puis la tâche (i) : oui, pour les mêmes raisons qu'à la question précédente.
\end{questions}

\item %Pour réaliser la tâche (k), 
Il faut nécessairement avoir réalisé les tâches (a), (c), (h), (i) et (j).

\item Le graphe ne contient pas de cycle.% (on ne revient jamais à un n\oe ud duquel on est parti).

\vspace*{-2mm}
\item 
\begin{multicols}{2}
\begin{itemize}
\item Graphe de gauche: 0, 2 puis 1.
\item Graphe de droite: 3, 5 puis 4.
\end{itemize}
\end{multicols}

\vspace*{-2mm}
\begin{minipage}{0.45\linewidth}
\item Le graphe associé à la matrice d'adjacence donnée est le suivant:
\begin{center}
\includegraphics{174_recette03}
\end{center}
\end{minipage}
\hfill
\begin{minipage}{0.45\linewidth}
\item Il est impossible de trouver un ordre permettant de réaliser les tâches représentées par le graphe de la question 6 en respectant leurs dépendances car un cycle y est présent.

\vspace*{3mm}~
\end{minipage}

\item Faisons un tableau d'exécution de la fonction \texttt{mystere}:\vspace*{-4mm}
\begin{center}
\begin{tabular}{|>{\ttfamily\small}m{4cm}|*2{c|}}
    \hline\tabulartitle
    Appel \texttt{mystere} & variable \texttt{ouverts} & variable \texttt{fermes} \\
    \hline
    Avant l'appel mystere & [F, F, F, F, F] & [F, F, F, F, F] \\
    \hline
   mystere(M, 1, 5, [F, F, F, F, F], [F, F, F, F, F], None) & [F, T, F, F, F] & [F, F, F, F, F] \\
    \hline
    mystere(M, 2, 5, [F, T, F, F, F], [F, F, F, F, F], None) & [F, T, T, F, F] & [F, F, F, F, F] \\
    \hline
    mystere(M, 3, 5, [F, T, T, F, F], [F, F, F, F, F], None) & [F, T, T, T, F] & [F, F, F, F, F] \\
    \hline
    mystere(M, 1, 5, [F, T, T, T, F], [F, F, F, F, F], None) & [F, T, T, T, T] & [F, F, F, F, F] \\
    \hline
\end{tabular}
\end{center}

Ainsi, \texttt{ok = False} car au niveau du dernier appel récursif, \texttt{ouverts[1]} est déjà égal à \texttt{T}; la fonction renvoie donc \texttt{False}.

\item La fonction renvoie \texttt{False} quand le graphe comporte un cycle.
\enlargethispage*{5em}
\item Après l'exécution des instructions, \texttt{elt = 2}.

\item À la ligne 24 de la fonction \texttt{mystère}, on peut insérer:
\begin{verbatim}
resultat.empiler(s)
\end{verbatim}
Ainsi, lorsque cela est possible, \texttt{ordre\_realisation} renvoie effectivement un ordre de réalisation des tâches du graphe.
\end{questions}
\end{corrige}





\thumb
\AfficheCorrige
