\documentclass[a4paper,11pt,french]{article}
\linespread{1}


\newcommand{\ch}{Chapitre 3}
\newcommand{\Ch}{Graphes, Matrices \linebreak[2] et Probabilités}	
\newcommand{\Cl}{T$^{\circ}$ ES Sp\'ecialit\'e}	
\newcommand{\Annee}{2010-2011}	
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%		Package
%\usepackage[french,lined,boxed,commentsnumbered]{algorithm2e}

\input macro_final.tex

\geometry{hmargin=2cm,vmargin=2.5cm}

\setcounter{NumLecon}{1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	Premiere page
\begin{document}
 
\setcounter{NumLecon}{1}


\debutCha{melancolie.eps}{Autoportrait (1937-38, complété en 1960) \fg \, et \\ \og M\'elancolie ()}{Joan Miro}
{Ce qui est important, ce n'est pas de finir une oeuvre, mais d'entrevoir qu'elle permette un jour de 
commencer quelque chose}{Joan Miro}{Joan Miro (1894 - 1984) est ...}{0.6}{0.8}

\setcounter{NumLecon}{1}
\TITRE{poisson_chantant.eps}{0.8}

\begin{flushright}
 \textit{Poisson chantant} (?) 
\end{flushright}

\begin{Intro}{Résumé}{
On a déjà vu que la théorie des graphes nous permettait de résoudre certains problèmes, comme celui de composition de matches, celui de coloration 
de cartes, et celui de chemin eulérien. Dans le premier chapitre, nous avons essentiellement travaillé sur les bases et le vocabulaire.\\
Mais la théorie des graphes permet de résoudre des problèmes bien plus complexe. En particulier, nous allons voir ici comment coder
un graphe de manière à le rendre utilisable par un ordinateur...}
\end{Intro}


\section{Matrice associée à un graphe}

\subsection{Exercice d'introduction}
Un parcours de santé est aménagé pour les sportifs dans le parc d'une ville. Il est composé de chemins à sens unique, 
et de quatre points de repère, tous distants de 500 mètres, comme indiqué sur le schéma ci-dessous.
\begin{center}
 \begin{psmatrix}[mnode=circle]
 & $S_1$ \\ 
 &  &  &  & $S_2$ \\ 
 &  & $S_4$ \\ 
 &  &  &  &  &  & $S_3$ 
\end{psmatrix}
\psset{arrows=->, labelsep=1mm,
       shortput=nab}
\ncline[linewidth=2pt]{1,2}{2,5}
\ncline[linewidth=2pt]{1,2}{3,3}
\ncline[linewidth=2pt]{4,7}{2,5}
\ncarc[arcangle=15,linewidth=2pt]{2,5}{3,3}
\ncarc[arcangle=15,linewidth=2pt]{3,3}{2,5}
\ncarc[arcangle=15,linewidth=2pt]{4,7}{3,3}
\ncarc[arcangle=15,linewidth=2pt]{3,3}{4,7}
\end{center}

Sur ce schéma du parcours de santé, $S_1$ désigne l'entré et $S_4$ la sortie. On fera l'hypothèse que tout trajet commenceren $S_1$ et finit en $S_4$.\\
Combien y a-t-il de trajets différents de 
\begin{itemize}
 \item $1$ km ?
 \item $1.5$ km?
 \item $2$ km ?
 \item $2.5$ km ?
\end{itemize}



\subsection{Définition et propriété}

\Defc{
La matrice associée à un graphe d'ordre $n$ (ou matrice d'adjacence) est la matrice carré $n \times n$ dont l'élément situé sur la ligne $i$ et 
la colonne $j$ est égal au nombre d'arêtes allant du sommet $i$ vers le sommet $j$ (ou les reliant simplement, dans le cas de graphe non orienté).
}

\Expls{
Dans le cas précédent, la matrice associé au graphe est la matrice $M=\left(\begin{array}{cccc}
                                                                             0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0& 1 & 0& 1 \\ 0& 1 & 1 & 0
                                                                            \end{array} \right)$.\\
La première colonne est remplie de $0$, car aucune arête d'arrive en $S_1$.\\
Il y a deux $1$ sur la première ligne : cela traduit le fait que le sommet $S_1$ est à l'origine de deux arêtes. \\\\
Si on oublie l'orientation du graphe précédent, la matrice associée est alors
$$N=\left(\begin{array}{cccc}
                                                                             0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0& 1 \\ 1& 1 & 2 & 0
                                                                            \end{array} \right)$$
}

\Rqs{
\item Dans un graphe orienté, la somme des termes est égale au nombre d'arrêtes. Si le graphe est non orienté, la somme 
des termes vaut le double du nombres d'arêtes.
\item Dans le cas d'un graphe non orienté, la matrice d'adjacence est symétrique.
 \item Une matrice décrit complètement un graphe. C'est le moyen le plus simple pour coder un graphe de façon utilisable pour un ordinateur.}

\Exos{
n$^{\circ}$ 21 - 23 - 25 - 27 - 29 p 243 (du graphe à la matrice)
}

\Exos{
n$^{\circ}$ 30 - 32 - 35 p 243 (de la matrice au graphe) + 2 p 259 + 21 p 261
}

\Act{
On reprend l'exemple du parcours de santé.
\begin{enumerate}
 \item Calculer $M^2$ à la main. Vérifier à la calculatrice. 
 \item Calculer $M^3$ à la main. Vérifier à la calculatrice. 
  \item Faire de même  pour $M^3$ et $M^4$. 
 \item Observer dans chaque cas alors le terme $m_{1,4}$. Que constatez-vous ?
\item Pouvez-vous trouver par avec la calculatrice le nombre de parcours reliant $S_1$ à $S_4$ de longueur $5$ km ? 
\end{enumerate}
}

\Thc[Admis]{
Soit un graphe de matrice $A$.\\
Le nombre de chaînes de longueur $n$ joignant le sommet $i$ au sommet $j$ est donné par le terme d'indice $i,j$ de la matrice $A^n$.
}

\Expl{
Dans l'exemple précédent, déterminer le nombre de chemins de 7 arêtes reliant $S_1$ à $S_4$. A quelle distance cela correspond-t-il ?\\
En admettant que le parcours soit non orienté, donner le nombre de chemins de 7 arêtes reliant  $S_1$ à $S_1$ ? $S_3$ à $S_2$ ?
}

\Expl{
On considère le parcours de santé non orienté. Un sportif décide d'emprunter chaque jour un nouveau trajet de 2km : combien
de jours peut-il tenir cet engagement, sachant qu'il part toujours de $S_1$ pourarriver en $S_4$ ?
}


\Exos{
n$^{\circ}$ 40-41-46 p 244 
}

\subsection{Plus courte chaîne}

\Defc[Rappel]{
La distance entre deux sommets est la plus courte longueur de chaîne qui les relient. \\
Le diamètre d'un graphe est la plus grande distance entre deux sommets, parmi toutes les paires de sommets.}

\Corc{
Soit un graphe de matrice $A$. La distance entre deux sommets $i$ et $j$ est le plus petit entier $n$ tel que le terme 
d'indice $i,j$ de $A^n$ soit non nul.
}

\Expl{
Utiliser cette propriété pour donner le diamètre du graphe représentant le parcours de santé.
}

\newpage
\section{Graphes Pondérés}

\subsection{Exemple}
\begin{multicols}{2}
Un voyageur souhaite se rendre de Marseille au Futuroscope en train. D'une carte du réseau TGV, il a extrait le schéma ci-contre :\\
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
Les guides donnent par ailleurs les temps suivants :\\
\begin{psmatrix}[mnode=circle,colsep=0.05,rowsep=0.05]
 &  &  &  &  & Paris \\ 
 &  &  & St Pierre des Corps \\ 
 &  & Futuroscope \\ 
 & Bordeaux &  &  &  & Lyon \\ 
 &  & Toulouse &  &  &  & Marseille 
\end{psmatrix}
\psset{arrows=-}
\ncline{5,7}{1,6}
\ncline{5,7}{4,6}
\ncline{5,7}{5,3}
\ncline{1,6}{4,6}
\ncline{1,6}{2,4}
\ncline{4,6}{2,4}
\ncline{2,4}{3,3}
\ncline{3,3}{4,2}
\ncline{4,2}{5,3}
\end{multicols}

\begin{tabular}{|l|l|l|}\hline
 Marseille-Lyon : 1h50 & Lyon-Paris : 2h15 & St Pierre des Corps-Futuroscope : 30' \\\hline
 Marseille-Paris : 3h & Lyon-St Pierre des Corps : 3h & Futuroscope-Bordeaux : 2h10 \\\hline
 Marseille-Toulouse : 3h & Paris-St Pierre des Corps : 1h & Toulouse-Bordeaux : 2h10 \\\hline
\end{tabular}\\

Quel trajet conseilleriez-vous à ce voyageur ? (on négligera dans cet exercice les temps de correspondance)

\subsection{Définitions}

\Defc{
Un graphe est dit pondéré lorsque chacune de ses arêtes est affectée d'un nombre appelé poids.
}

\Rq{Cette année, les poids seront toujours positifs, mais ce n'est pas forcément le cas.
}

\Defc{
Le poids d'une chaîne est la somme des poids des arêtes qui la composent.\\
Une plus courte chaîne entre deux sommets donnés est une chaîne de poids minimal parmi toutes les chaînes reliant ces deux sommets.
}

\Rq{Dans un graphe connexe avec des poids positifs, il y a forcément une plus courte chaîne entre n'importe quels sommets du graphe, mais celle-ci n'est pas toujours unique.}

\Expl{Dans l'exemple précédent, la plus courte chaîne reliant Marseille au Futuroscope est : ...}

\subsection{Algorithme de Dijkstra (1959)}

Les données sont un graphe $G$ et un sommet de départ $D$ et un d'arrivée $A$. 
\begin{center}
 \begin{psmatrix}[mnode=circle,colsep=1,rowsep=1]
 &  & G &  &  & S \\ 
D &  &  & H &  &  &  & A \\ 
 &  & M &  &  & C 
\end{psmatrix}
\psset{arrows=-,shortput=nab}
\ncline{2,1}{1,3}^{8}
\ncline{2,1}{3,3}^{10}
\ncline{1,3}{3,3}^{3}
\ncline{1,3}{2,4}^{5}
\ncline{1,3}{1,6}^{15}
\ncline{3,3}{2,4}^{5}
\ncline{3,3}{3,6}^{7}
\ncline{2,4}{1,6}^{5}
\ncline{2,4}{3,6}^{3}
\ncline{1,6}{3,6}^{3}
\ncline{1,6}{2,8}^{10}
\ncline{3,6}{2,8}^{8}
\end{center}

\begin{enumerate}
 \item \textbf{Initialisation} : on fixe à $0$ la marque de $D$.\\
Marquer chacun des sommets adjacents à $D$ par le poids de l'arête joignant ce sommet à $D$.\\
Marquer les autres sommets par $+\infty$.
 \item Regarder tous les sommets de marque non fixée. Repérer celui qui a la plus petite marque et la fixer. Soit $X$ ce sommet.\\
Pour chaque sommet $Y$ adjacent à $X$, et de marque non fixée, calculer la somme de la marque de $X$ et du poids de l'arête reliant $X$ à $Y$.\\
Si cette somet est inférieur à la marque de $Y$, barrer cette marque et la remplacer par cette somme, en indiquant entre parenthèses la provenance de cette nouvelle marque, dite améliorée.
\item \textbf{Itération} : On recommence la deuxième étape jusqu'à épuisement des sommets.
\end{enumerate}

\Expl{
Dans l'exemple précédent, cela donne :
\begin{itemize}
\item \'{E}tape 1 : sélection de D.
\item Marquage de G (8 de D) et de M (10 de D), les autres sommets étant marqués à $+\infty$.
 \item \'{E}tape 2 : Sélection de G.
\item Marquage de H (13 de G) et de S (23 de G) \textit{conservation de M.}
\item \'{E}tape 2 (bis) : Sélection de M.
\item Marquage de C (17 de M) ; \textit{conservation det H et de G}
 \item \'{E}tape 2  : Sélection de H.
\item Marquage de S (18 de H) et de C (16 de H)
\item \'{E}tape 2 : Sélection de C
\item Marquage de A (24 de C) ; \textit{conservation de S}
\item \'{E}tape 2 : Sélection de S 
\item \textit{conservation de A}
\item \'{E}tape 3 : sélection de A
\end{itemize}
La plus courte chaîne entre D et A est donc D-G-H-C-A 
}

\Rq{On peut placer les opérations successives au fur et à mesure dans un tableau (voir p 275).}

\Exos{
n$^{\circ}$ 5 à 15 p 281 + annales 1 et 2 de la feuille d'exo
}



\newpage
\section{Graphes étiquetés ou Automates}

\subsection{Exemple}

Activité 7 p 270

\subsection{Définition}

\Defc{
Un graphe  \textbf{étiqueté}  est un graphe orienté dans lequel chacune de ses arêtes est affectée d'étiquettes 
qui peuvent être des lettres ou des symboles, et qui possède un sommet initial et un sommet final (toujours indiqués).\\
L'ensemble de ces symboles est appelé \textbf{alphabet}.\\
Un \textbf{mot} est une suite fini de symboles de l'alphabet.\\
Un mot est dit \textbf{reconnu} par un graphe étiqueté (ou accepté come code d'accès) s'il existe un chemin orienté
du graphe, partant du sommet initial et arrivant au sommet final, et étiqueté par ce mot.\\
Un \textbf{langage} associé à un graphe étiqueté est l'ensemble des mots reconnus par ce graphe.
}

\Rq{
Le contenu de ce chapitre se borne à faire comprendre ces notions de mot reconnu par un graphe étiqueté et de
langage associé à un graphe étiqueté, et à les faire fonctionner dans des cas simples.\\
Aucun théorème n’est au programme. Il ne faudrait pas s’imaginer que c’est parce qu’il n’y en a pas ! Les
graphes étiquetés, ou automates, ont donné lieu depuis une cinquantaine d’années à une théorie mathématique 
abstraite, riche et diversifiée, possédant de nombreuses applications.\\
Ils sont en particulier fondamentaux en informatique, et c’est pourquoi on a jugé utile de les faire connaître aux élèves
de terminale.

}

\Expl{
Voir p 275 et activité 6 p 275
}


\Exos{
n$^{\circ}$ 16-17 p 281 + 50 p 288 + 3 p 279
}

\newpage

\section{Graphes probabilistes}

\subsection{Exemple}

\textbf{Partie A : Des puces savantes ...}\\
Mario est un dresseur de puces qui a un excellent numéro de cirque : il possède 100 puces savantes qu'il fait sauter en
l'air en cadence.\\
Il place deux podiums l'un à côté de l'autre : un petit (P) et un grand (G).\\
Il a alors constaté que :
\begin{itemize}
 \item Parmi les puces posées sur le grand podium, $80\%$ retombent sur place et $20\%$ sur le petit.
 \item Parmi les puces posées sur le petit podium, $40\%$ retombent sur place et $60\%$ sur le grand.
\end{itemize}
\begin{enumerate}
 \item Représenter la situation par un graphe pondéré. Les sommets représentent les podiums, les arêtes les sauts de puces et leur
poids leurs probabilités.
\item Expliquer pourquoi la somme des pondérations des arêtes partant d'un des sommets est forcément 1.
\item A partir de la situation où les 100 puces sont sur le podium G au départ, indiquer la répartition des 
puces après le $1^{er}$ saut,
puis après deux sauts (on pourra utiliser un arbre pondéré).
\end{enumerate}
\textbf{Partie B : Du côté des matrices}\\
Au départ, les puces sont toutes sur le podium G. On a donc une répartition que l'on peut noter sous la forme d'une 
matrice ligne $P_0=\left(\begin{array}{cc}
                      100 & 0
                     \end{array}\right)$.\\
On note $M$ la matrice associée au graphe précédent (en rangeant G et P dans cet ordre).
\begin{enumerate}
 \item Vérifier à la main que le produit $P_0 \times M$ permet de retrouver la répartition des puces après le premier saut.\\
On notera $P_1$ cette répartition.
\item Vérifier à la main que le produit $P_1 \times M$ permet de retrouver la répartition des puces après le deuxième saut.\\
On notera $P_2$ cette répartition.
\item Vérifier à la calculatrice que $P_2=P_0 \times M^2$.
\item En déduire un calcul matriciel permettant de connaître la répartition des puces après 3, 4 puis 5 sauts.
\end{enumerate}
\textbf{Partie C : Vers un état stable}\\
\begin{enumerate}
 \item Dans le cas où toutes les puces sont sur le podium G au départ, déterminer à l'aide de la calculatrice 
la répartition des puces après 10 sauts, puis 15. Que sembe-t-il se passer ?
\item \begin{enumerate}
       \item Dans le cas où toutes les puces sont sur le podium P au départ, indiquer la nouvelle répartition initiale $P_0$
 \item Déterminer les 5 répartitions suivantes. Que peut-on en déduire ?
      \end{enumerate}
\item Reprendre la question 2 avec une répatition de votre choix.
\end{enumerate}
\textbf{Partie C : Pour aller plus loin}\\
On considère la matrice $P=\left(\begin{array}{cc}
                                  x & 1-x
                                 \end{array}\right)$ avec $0\leq x \leq 1$ correspondant à une répartiton donnée.
\begin{enumerate}
 \item Effectuer à la main le calcul $P \times M$
 \item Déterminer la valeur de $x$ pour laquelle $P=P\times M$
 \item Comparer le résultat obtenu avec celui conjecturé à la fin de la partie C.
\end{enumerate}


\newpage
\subsection{Définition}

On considère une expérience aléatoire à deux ou trois issues possibles, que l'on répète $n$ fois.\\
A chaque étape $k$, on définit une loi de probabilité sur l'ensemble des issues possibles, appelée un \textbf{état de probabiliste},
représentée par une matrice ligne 
$$P_n=\left(\begin{array}{cc}
                                  a_n & b_n
                                 \end{array}\right) \qquad \text{ ou } \qquad P_n=\left(\begin{array}{ccc}
                                  a_n & b_n & c_n
                                 \end{array}\right)$$ 
On suppose que le passage d'un état au suivant est toujours régi de la même façon. Ce passage se décrit par un graphe probabiliste
ou une matrice de transition.\\
On peut aussi applicquer cette notion dans le cas de la répartition d'un ensemble en deux ou trois parties et son évolution par étapes successives.

\Rq{Ceci se généralise à n'importe quel nombre fini d'issues possibles, mais cela n'est pas au programme.}

\Defc{
Un graphe probabiliste est un graphe orienté et pondéré tel que :
\begin{itemize}
 \item Les sommets du graphe sont les issues possibles d'une expérience aléatoire
\item Le poids d'une arête orientée partant du sommet $i$ et allant vers le sommet $j$ est la probabilité conditionnelle 
d'obtenir l'issue $j$ à l'étape $n+1$ sachant que l'on a obtenu $i$ précédente (à l'étape $n$).
\end{itemize}
La matrice associée à un graphe probabiliste s'appelle la matrice de transition du graphe.
}

\Rq{Nécessairement, la somme des poids des arêtes partant d'un même sommet vaut 1.
}

\Ptec{
La matrice de transition d'un graphe probabiliste est une matrice carré 
dont les éléments sont les poids des arêtes du graphe lorsqu'elles existent, et sont égaux à $0$ sinon.\\
La somme des éléments de chaque ligne est égale à 1.\\
L'état probabiliste à l'étape $n+1$ s'obtient par $P_{n+1}=P_n \times M$.
}

\Expl{
Un élève peut se rendre à son lycée par trois chemins $A$, $B$ et $C$. Chaque jour, il peut changer ou non d'itinéaire :
\begin{itemize}
 \item S'il passe par le chemin $A$, le lendemain, il prend le chemin $B$ aveec la probabilité $0.5$ et le chemin $C$
avec la probabilité $0.2$.
 \item S'il passe par le chemin $B$, le lendemain, il prend le chemin $A$ aveec la probabilité $0.1$ et le chemin $C$
avec la probabilité $0.6$.
 \item S'il passe par le chemin $C$, le lendemain, il prend le chemin $A$ aveec la probabilité $0.6$ et le chemin $B$
avec la probabilité $0.2$.
 \end{itemize}
\begin{enumerate}
 \item Dessiner le graphe probabiliste correspondant à cette expérience, et donner sa matrice de transition.
\end{enumerate}
}

\Defc{Un état probabiliste $P$ est stable lorsqu'il reste le même dans la répétition de l'expérience
aléatoire décrite par la matrice de transition d'un graphe probabiliste, ie qu'il vérifie $P=P \times M$.
}

\Exos{
n$^{\circ}$ 20-21-22 p 283 + 26 p 284 
}


\subsection{Propriétés}

\Propc{Soient $M$ la matrice de transition d'un graphe probabiliste, $P_0$ la matrice représentant l'état 
probabiliste initial d'une expérience aléatoire, et $P_n$ la matrice décrivant l'état à l'étape $n$. Alors, pour tout $n\geq 0$ on a :
$$P_n=P_0 \times M^n$$
}

\Propc{Pour tout graphe probabiliste d'ordre 2, dont la matrice de transition n'admet pas de 0, 
lorsque $n$ devient très grand, l'état probabiliste $P_n$ tend vers un état stable $P$, indépendant
de l'état initial $P_0$.
}

\Exop{Deux villes X et Y totalisent à elles deux une population d’un million d’habitants.\\
La ville X est plus agréable, mais la ville Y offre de meilleurs salaires.
$20 \%$ des habitants de Y partent chaque année habiter X pour avoir un meilleur cadre de vie, et 
$5 \%$ des habitants de X partent chaque année habiter Y pour augmenter leur niveau de vie.
\begin{enumerate}
 \item Sachant qu’en l’année 0, un quart des habitants sont en X , calculer la population de X et de Y au bout de 1, 2, 5
et 10 ans.
\item Que se passe-t-il si l’on suppose que $99 \%$ des habitants sont initialement en X ou en Y ?
\item Même question si la population est également répartie entre les deux villes en l’année zéro ?\\
Que constate-t-on ?
\item On étudie le cas général. On note $P_n=\left(\begin{array}{cc}
                                  X_n & Y_n
                                 \end{array}\right)$ le vecteur ligne qui décrit la population de X et Y
au bout de $n$ années.
\begin{enumerate}
 \item Déterminer la matrice $M$ de transition du graphe.
 \item Exprimer $P_1$ et $P_2$ en fonction de $M$ et $P_0$
 \item A l'aide de la formule exprimant $P_n$ en fonction de $P_0$ et $M$, trouver l'état stable du problème.
\end{enumerate}
\end{enumerate}
 }


\Exop{Un individu vit dans un milieu où il est susceptible d’attraper une maladie par piqûre d’insecte. Il peut être dans l’un
des trois états suivants : immunisé (I ), malade (M), sain, c’est-à-dire non malade et non immunisé, (S).\\
D’un mois à l’autre, son état peut changer selon les règles suivantes :
\begin{itemize}
 \item  étant immunisé, il peut le rester avec une probabilité 0,9 ou passer à l’état S avec une probabilité 0,1 ;
\item  étant dans l’état S, il peut le rester avec une probabilité 0,5 ou passer à l’état M avec une probabilité 0,5 ;
\item  étant malade, il peut le rester avec une probabilité 0,2 ou passer à l’état I avec une probabilité 0,8.
\end{itemize}
\begin{enumerate}
 \item Tracer un graphe probabiliste pour décrire cette situation et écrire la matrice de transition.
\item Calculer l’état de probabilité de l’individu au bout de trois mois, de six mois, d’un an, de deux ans pour chacune
des situations suivantes :
\begin{enumerate}
 \item au départ, il est immunisé ;
\item au départ, il est non malade et non immunisé ;
\item au départ, il est malade.
\end{enumerate}
\end{enumerate}
}


\Exos{
n$^{\circ}$ 30 p 285 + 39 p 286 + 49 p 288 + 58 p 290 + annales 3 à 5
}



\end{document}
