X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-maths-dis.git/blobdiff_plain/7e16643d8ba519bcc6512c70661b4ffa8ca521a0..refs/heads/master:/graphes/S2MD.tex

diff --git a/graphes/S2MD.tex b/graphes/S2MD.tex
index a86b2b9..5c52021 100644
--- a/graphes/S2MD.tex
+++ b/graphes/S2MD.tex
@@ -1,12 +1,10 @@
 \documentclass[]{report}
 \usepackage[a4paper]{geometry}
 \geometry{hmargin=1.5cm, vmargin=1.5cm }
-\usepackage[latin1]{inputenc}
+\usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc} 
 \usepackage[french]{babel}
 \usepackage{amsmath,amssymb,latexsym,eufrak,euscript,array}
-
-
 \usepackage{pgf}
 \usepackage{tikz}
 \usepackage{pdfpages}
@@ -19,8 +17,8 @@
 
 
 
-\newtheorem{definition}{Definition}
-\newtheorem{theoreme}[definition]{Théorème}
+\newtheorem{definition}{DÃ©finition}
+\newtheorem{theoreme}[definition]{ThÃ©orÃ¨me}
 \newtheorem{proposition}[definition]{Proposition}
 \newtheorem{exemple}[definition]{Exemple}
 
@@ -34,8 +32,8 @@
 \def \A {\mathcal{A}}
 \def \B {\mathcal{B}}
 
-\title{Cours Mathématiques Discrètes
-  \\IUT Belfort Montbéliard}
+\title{Cours MathÃ©matiques DiscrÃ¨tes
+  \\IUT Belfort MontbÃ©liard}
 \author{{\sc Pierre-Cyrille HEAM}}
 
 
@@ -50,30 +48,30 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\chapter{Graphes finis orientés}
+\chapter{Graphes finis orientÃ©s}
 
 
 %%%%%%%%%%%%%%%%
-\section{Premières définitions}
+\section{PremiÃ¨res dÃ©finitions}
 
-Un {\bf graphe fini orienté} est un couple $(V,E)$ où 
+Un {\bf graphe fini orientÃ©} est un couple $(V,E)$ oÃ¹ 
 \begin{itemize}
-\item $V$ est un ensemble fini dont les éléments sont appelés {\bf sommets}
-  ou {\bf noeuds} ou {\bf états}.
-\item $E\subseteq V\times V$ est un ensemble de couples d'éléments de $V$,
-  appelés {\bf arêtes} ou {\bf transitions}.
+\item $V$ est un ensemble fini dont les Ã©lÃ©ments sont appelÃ©s {\bf sommets}
+  ou {\bf noeuds} ou {\bf Ã©tats}.
+\item $E\subseteq V\times V$ est un ensemble de couples d'Ã©lÃ©ments de $V$,
+  appelÃ©s {\bf arÃªtes} ou {\bf transitions}.
 \end{itemize}
 
 Par exemple $\left(\{1,2,3\},\{(1,2),(2,2),(3,1)\}\right)$ est un graphe
-fini orienté. Le choix des lettres $V$ et $E$ viennent de l'anglais pour
+fini orientÃ©. Le choix des lettres $V$ et $E$ viennent de l'anglais pour
 {\it vertice} et {\it edge}. On rappelle que dans un ensemble (entre $\{\}$)
-les éléments ne sont pas ordonnés et n'apparaissent qu'au plus une fois. En
-revanche dans un couple (deux éléments entre parenthèse), les éléments sont
-ordonnés. Le couple $(1,2)$ est différent du couple $(2,1)$.
+les Ã©lÃ©ments ne sont pas ordonnÃ©s et n'apparaissent qu'au plus une fois. En
+revanche dans un couple (deux Ã©lÃ©ments entre parenthÃ¨se), les Ã©lÃ©ments sont
+ordonnÃ©s. Le couple $(1,2)$ est diffÃ©rent du couple $(2,1)$.
 
 
 \begin{exo}
-Les couples $(V,E)$ suivants sont-ils des graphes finis orienté~?
+Les couples $(V,E)$ suivants sont-ils des graphes finis orientÃ©~?
 \begin{enumerate}
 \item $V=\{1,2,3\}$ et $E=\{(1,3)\}$~?
 \item $V=\{1,2,3\}$ et $E=\{(1,6),(2,4)\}$~?
@@ -83,20 +81,20 @@ Les couples $(V,E)$ suivants sont-ils des graphes finis orient
 \end{enumerate}
 \end{exo}
 
-{\bf Sauf mention contraire, tous les graphes étudiés dans ce polycopié
-  seront des graphes finis orientés, que nous appellerons simplement {\it
+{\bf Sauf mention contraire, tous les graphes Ã©tudiÃ©s dans ce polycopiÃ©
+  seront des graphes finis orientÃ©s, que nous appellerons simplement {\it
     graphes} par la suite.}
 
-Un graphe se représente souvent par un dessin où les sommets sont des points
-(parfois entourés d'un cercle) et les arêtes des flèches~: si $(x,y)$ est
-une arête, on dessine une flèche entre $x$ et $y$. Par exemple le graphe
+Un graphe se reprÃ©sente souvent par un dessin oÃ¹ les sommets sont des points
+(parfois entourÃ©s d'un cercle) et les arÃªtes des flÃ¨ches~: si $(x,y)$ est
+une arÃªte, on dessine une flÃ¨che entre $x$ et $y$. Par exemple le graphe
 $$(\{1,2,3,4\},\{(1,1),(1,2),(3,1),(2,4),(3,4)\})$$ peut se dessiner comme sur la
-figure~\ref{fig:g1}. Comme on peut le voir, il n'y a pas unicité de la façon
+figure~\ref{fig:g1}. Comme on peut le voir, il n'y a pas unicitÃ© de la faÃ§on
 de dessiner un graphe. 
 
 \begin{figure}[h]
 \begin{center}
-\subfigure[première possibilité]{
+\subfigure[premiÃ¨re possibilitÃ©]{
 \begin{tikzpicture}
 \node (1) at (0,0) {$1$};
 \node (2) at (4,0) {$2$};
@@ -109,7 +107,7 @@ de dessiner un graphe.
 \path[->,>=triangle 90] (2) edge[] node [above] {} (4);
 \end{tikzpicture}
 }\hspace*{3cm}
-\subfigure[deuxième possibilité]{
+\subfigure[deuxiÃ¨me possibilitÃ©]{
 \begin{tikzpicture}
 
 \node (1) at (0,0) {$1$};
@@ -124,7 +122,7 @@ de dessiner un graphe.
 \end{tikzpicture}
 }
 \end{center}
-\caption{Représentation d'un graphe}\label{fig:g1}
+\caption{ReprÃ©sentation d'un graphe}\label{fig:g1}
 \end{figure}
 
 
@@ -151,7 +149,7 @@ Donner sous forme ensembliste ($V$ et $E$) le graphe suivant~:
 \end{tikzpicture}
 \end{center}
 
-Le dessin ci-dessous représente-t-il un graphe~? Si oui le donner
+Le dessin ci-dessous reprÃ©sente-t-il un graphe~? Si oui le donner
 explicitement, sinon dire pourquoi.
 
 \begin{center}
@@ -269,24 +267,24 @@ sont les voisins de $3$~? de $7$~? Quels sommets ont $9$ pour voisin~?
 
 
 \begin{exo}
-On considère la fonction $f$ de $\{0,\ldots,7\}$ dans $\{0,\ldots,7\}$ qui à
-$x$ associe son reste modulo $3$. Dessiner le graphe où $V=\{0,\ldots,7\}$ et
-$(x,y)\in E$ si et seulement si $y=f(x)$. Mêmes question avec $(x,y)\in E$
-ssi $x^2=y \mod 5$ (c'est-à-dire si $x^2-y$ est un multiple de $5$). Même question avec $(x,y)\in E$ ssi $xy=1 \mod 6$.
+On considÃ¨re la fonction $f$ de $\{0,\ldots,7\}$ dans $\{0,\ldots,7\}$ qui Ã 
+$x$ associe son reste modulo $3$. Dessiner le graphe oÃ¹ $V=\{0,\ldots,7\}$ et
+$(x,y)\in E$ si et seulement si $y=f(x)$. MÃªmes question avec $(x,y)\in E$
+ssi $x^2=y \mod 5$ (c'est-Ã -dire si $x^2-y$ est un multiple de $5$). MÃªme question avec $(x,y)\in E$ ssi $xy=1 \mod 6$.
 \end{exo}
 
 \begin{exo}
-On considère $V=\{maison, voiture, poisson, porte, cartable, grue\}$ et
+On considÃ¨re $V=\{maison, voiture, poisson, porte, cartable, grue\}$ et
 $(x,y)\in E$ si et seulement $x$ est avant $y$ dans l'ordre du dictionnaire. 
 Dessiner le graphe $(V,E)$.
-Même question mais cette fois ci $(x,y)\in E$ si et seulement $x$ et
+MÃªme question mais cette fois ci $(x,y)\in E$ si et seulement $x$ et
 $y$ ont au moins deux lettres en commun.
 \end{exo}
 
 \begin{exo}
 Soit $G=(V,E)$ un graphe. Comment voit-on sur un dessin de $G$ que la relation
 $E$ est une application bijective~? que la relation $E$ est transitive~?
-réflexive~? 
+rÃ©flexive~? 
 \end{exo}
 
 
@@ -296,24 +294,24 @@ r
 
 
 Soit $G=(V,E)$ un graphe. Un {\bf chemin} est une suite finie
-$(x_1,x_2),(x_2,x_3),\ldots,(x_{n},x_{n+1})$ d'arêtes consécutives. L'entier
-$n$ est appelé {\bf taille} ou {\bf longueur} du chemin. Le sommet $x_1$ est l'{\bf origine}
+$(x_1,x_2),(x_2,x_3),\ldots,(x_{n},x_{n+1})$ d'arÃªtes consÃ©cutives. L'entier
+$n$ est appelÃ© {\bf taille} ou {\bf longueur} du chemin. Le sommet $x_1$ est l'{\bf origine}
 du chemin et $x_n$ sa {\bf destination}. On dit aussi que ce chemin part de
 $x_1$ pour arriver en $x_n$.  
 Dans le graphe de la figure~\ref{fig:grapheexo1}, $(0,1),(1,2),(2,6)$ est un
 chemin partant de $0$, arrivant en $6$ et de longueur $3$. Par convention,
-de tout point part un chemin vers lui même de longueur $0$ (qui n'utilise
-aucune arête). 
+de tout point part un chemin vers lui mÃªme de longueur $0$ (qui n'utilise
+aucune arÃªte). 
 
 
 Une {\bf boucle} est un chemin dont le sommet d'origine est aussi le sommet
-d'arrivée. Une boucle qui ne passe pas deux fois par le même sommet (sauf à
-l'origine et à la destination) est appelé un {\bf circuit}. Dans le graphe
+d'arrivÃ©e. Une boucle qui ne passe pas deux fois par le mÃªme sommet (sauf Ã 
+l'origine et Ã  la destination) est appelÃ© un {\bf circuit}. Dans le graphe
 de la figure~\ref{fig:grapheexo1}, $(5,12),(12,10),(10,5)$ est un circuit. 
 Le chemin 
 $$(0,1),(1,7)(7,13)(13,0),(0,3),(3,7),(7,13),(13,0)$$
 est une boucle mais n'est pas un circuit. 
-Un chemin qui ne passe jamais deux fois par le même sommet est dit {\bf sans
+Un chemin qui ne passe jamais deux fois par le mÃªme sommet est dit {\bf sans
   boucle}. 
 
 
@@ -322,20 +320,20 @@ Dans le graphe de la figure~\ref{fig:grapheexo1} donner
 \begin{enumerate}
 \item Un circuit de taille $1$,
 \item Une boucle de longueur $9$ passant par $4$,
-\item Un chemin sans boucle de $0$ à $18$,
+\item Un chemin sans boucle de $0$ Ã  $18$,
 \item Un chemin sans boucle de taille au moins $10$. 
 \end{enumerate}
 \end{exo}
 
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%ùù
-\section{Graphe et modélisation}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Ã¹Ã¹
+\section{Graphe et modÃ©lisation}
 
-L'objectif de ce chapitre est de voir comment passer d'un problème concret à
-un problème de graphe. 
+L'objectif de ce chapitre est de voir comment passer d'un problÃ¨me concret Ã 
+un problÃ¨me de graphe. 
 
 \begin{exo}
-On considère le plan ci-dessous d'un musée. La porte d'entrée est en bas à
+On considÃ¨re le plan ci-dessous d'un musÃ©e. La porte d'entrÃ©e est en bas Ã 
 gauche. 
 
 \bigskip
@@ -366,24 +364,24 @@ gauche.
 \end{tikzpicture}
 
 \begin{enumerate}
-\item Représenter sous forme de graphe ce musée, en mettant un sommet par
+\item ReprÃ©senter sous forme de graphe ce musÃ©e, en mettant un sommet par
   salle. 
 \item On suppose qu'un gardien peut surveiller la salle dans laquelle il se
   trouve ainsi que les salles voisines. Combien faut-il de gardiens au
   minimum~?
-Formuler ce problème, d'une manière générale, dans le vocabulaire des
+Formuler ce problÃ¨me, d'une maniÃ¨re gÃ©nÃ©rale, dans le vocabulaire des
 graphes. 
 
-\item Un groupe de visiteurs souhaite admirer toutes les salles du musée. 
-Peut-il le faire sans jamais passer deux fois par la même salle (on ne
+\item Un groupe de visiteurs souhaite admirer toutes les salles du musÃ©e. 
+Peut-il le faire sans jamais passer deux fois par la mÃªme salle (on ne
 compte pas le chemin de retour; le groupe peut partir de n'importe quelle
-salle aussi)~? Proposer une formulation générale de ce
-problème en utilisant le vocabulaire des graphes.
+salle aussi)~? Proposer une formulation gÃ©nÃ©rale de ce
+problÃ¨me en utilisant le vocabulaire des graphes.
 
-\item Le soir, le conservateur souhaite avant de fermer le musée passer dans
+\item Le soir, le conservateur souhaite avant de fermer le musÃ©e passer dans
   toutes les salles puis ressortir, tout en minimisant le trajet (il part de
-  l'entrée et ressort par l'entrée/sortie). Quel
-  chemin doit-il prendre~? Formuler ce problème de façon général en
+  l'entrÃ©e et ressort par l'entrÃ©e/sortie). Quel
+  chemin doit-il prendre~? Formuler ce problÃ¨me de faÃ§on gÃ©nÃ©ral en
   utilisant le vocabulaire des graphes.
 
 \end{enumerate}
@@ -393,77 +391,77 @@ probl
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{exo}
-On considère un ensemble fini $V$ de joueurs de tennis, et le graphe orienté
-$(V,E)$ tel que $(x,y)\in E$ si et seulement si $x$ a déjà gagné un match
-contre $y$. Donner des formulations dans le vocabulaire de la théorie des
-graphes des propriétés suivantes.
+On considÃ¨re un ensemble fini $V$ de joueurs de tennis, et le graphe orientÃ©
+$(V,E)$ tel que $(x,y)\in E$ si et seulement si $x$ a dÃ©jÃ  gagnÃ© un match
+contre $y$. Donner des formulations dans le vocabulaire de la thÃ©orie des
+graphes des propriÃ©tÃ©s suivantes.
 
 \begin{enumerate}
 \item Il y a un joueur qui n'a jamais perdu.
-\item Il y a un joueur qui n'a jamais gagné.
-\item Un joueur ne joue jamais contre lui-même.
-\item Tous les joueurs ont déjà joué au moins un match conte un autre
+\item Il y a un joueur qui n'a jamais gagnÃ©.
+\item Un joueur ne joue jamais contre lui-mÃªme.
+\item Tous les joueurs ont dÃ©jÃ  jouÃ© au moins un match conte un autre
   joueur.
-\item Il y a un joueur qui a déjà joué contre tout le monde.
-\item Il y a un joueur qui a déjà gagné contre tout le monde.
-\item Il y a un joueur qui a joué contre tout le monde et  perdu tous
+\item Il y a un joueur qui a dÃ©jÃ  jouÃ© contre tout le monde.
+\item Il y a un joueur qui a dÃ©jÃ  gagnÃ© contre tout le monde.
+\item Il y a un joueur qui a jouÃ© contre tout le monde et  perdu tous
   ses matchs. 
 \end{enumerate}
 \end{exo}
 
 \begin{exo}
-On considère un graphe représentant la carte d'une ville~: chaque n\oe{}ud est
-un croisement, chaque arête un tronçon de rue, codant le sens de
-circulation.  On considère de plus que les neouds sont coloriés, en rouge
+On considÃ¨re un graphe reprÃ©sentant la carte d'une ville~: chaque n\oe{}ud est
+un croisement, chaque arÃªte un tronÃ§on de rue, codant le sens de
+circulation.  On considÃ¨re de plus que les neouds sont coloriÃ©s, en rouge
 (s'il y a un feu de signalisation au croisement) ou en bleu (s'il n'y a pas
 de feu). 
-Exprimer, dans le vocabulaire de la théorie des graphes les
-propriétés suivantes.
+Exprimer, dans le vocabulaire de la thÃ©orie des graphes les
+propriÃ©tÃ©s suivantes.
 
 \begin{enumerate}
 \item Il n'y a pas de sens unique.
 \item Il n'y a pas d'impasse. 
-\item De n'importe où, je peux aller partout. 
-\item De n'importe où, je peux aller partout en passant par au plus trois
+\item De n'importe oÃ¹, je peux aller partout. 
+\item De n'importe oÃ¹, je peux aller partout en passant par au plus trois
   feux de signalisation.
-\item Deux croisements  consécutifs ne peuvent avoir tout deux des feux. 
-\item Il n'y a jamais plus de deux rues qui se croisent à la fois. 
+\item Deux croisements  consÃ©cutifs ne peuvent avoir tout deux des feux. 
+\item Il n'y a jamais plus de deux rues qui se croisent Ã  la fois. 
 \item Il n'y a ni pont, ni tunnel.
 \end{enumerate}
 \end{exo}
 
 \begin{exo}
-On considère le graphe $G$ dont les sommets sont les configurations possible
-d'un rubics cube, et il y a une arête entre deux configurations si l'on peut
-passer de l'une à l'autre en jouant un coup (c'est-à-dire une rotation d'un
-quart de tour d'un coté). Exprimer avec le vocabulaire de la théorie des
-graphes les propriétés suivantes (on ne cherche pas à savoir si elles sont
+On considÃ¨re le graphe $G$ dont les sommets sont les configurations possible
+d'un rubics cube, et il y a une arÃªte entre deux configurations si l'on peut
+passer de l'une Ã  l'autre en jouant un coup (c'est-Ã -dire une rotation d'un
+quart de tour d'un cotÃ©). Exprimer avec le vocabulaire de la thÃ©orie des
+graphes les propriÃ©tÃ©s suivantes (on ne cherche pas Ã  savoir si elles sont
 vraies ou fausse)~:
 \begin{itemize}
 \item Il y a toujours une solution.
 \item A partir de certaines configurations, il n'y a pas de solution.
-\item De toute position, si je modifie le cube, je peux revenir à cette
+\item De toute position, si je modifie le cube, je peux revenir Ã  cette
   position. 
-\item Il existe une position dans laquelle je peux résoudre le rubics cube,
+\item Il existe une position dans laquelle je peux rÃ©soudre le rubics cube,
   mais pas en moins de 30 coups.
-\item Si dans une position je peux résoudre le rubics cube, alors je peux le
-  résoudre en moins de 30 coups. 
+\item Si dans une position je peux rÃ©soudre le rubics cube, alors je peux le
+  rÃ©soudre en moins de 30 coups. 
 \end{itemize}
 \end{exo}
 
 
 \begin{exo}
-On considère un ensemble de $n$ enfants portant chacun un dossard différent,
-numéroté de $1$ à $n$, et jouant à cache-cache. On considère le graphe dont
-les sommets sont les entiers de $1$ à $n$ et il y a une arête entre $i$ et
+On considÃ¨re un ensemble de $n$ enfants portant chacun un dossard diffÃ©rent,
+numÃ©rotÃ© de $1$ Ã  $n$, et jouant Ã  cache-cache. On considÃ¨re le graphe dont
+les sommets sont les entiers de $1$ Ã  $n$ et il y a une arÃªte entre $i$ et
 $j$ si l'enfant avec le dossard $i$ peut voir l'enfant avec le dossard $j$.
-Exprimer dans le vocabulaire de la théorie des graphes les propriétés
+Exprimer dans le vocabulaire de la thÃ©orie des graphes les propriÃ©tÃ©s
 suivantes~:
 
 \begin{enumerate}
-\item Il y a un enfant bien caché qu'aucun autre ne peut voir.
+\item Il y a un enfant bien cachÃ© qu'aucun autre ne peut voir.
 \item Il y a un enfant qui ne voit personne.
-\item Un enfant se voit toujours lui-même.
+\item Un enfant se voit toujours lui-mÃªme.
 \item Il y a deux enfants qui se voient l'un l'autre.
 \item Tout enfant voit au moins un autre enfant.
 \end{enumerate}
@@ -471,29 +469,29 @@ suivantes~:
 
 
 \begin{exo}
-Un homme se trouve au bord d'une rivière avec un choux, une chèvre et loup.
-Il possède une barque et veut traverser la rivière. Cependant, il ne peut
-mettre en même temps, en plus de lui, dans la barque qu'un des trois. Et,
+Un homme se trouve au bord d'une riviÃ¨re avec un choux, une chÃ¨vre et loup.
+Il possÃ¨de une barque et veut traverser la riviÃ¨re. Cependant, il ne peut
+mettre en mÃªme temps, en plus de lui, dans la barque qu'un des trois. Et,
 malheureusement aussi, il ne peut laisser sur une rive seul le loup avec la
-chèvre, ni la chèvre avec le choux.
+chÃ¨vre, ni la chÃ¨vre avec le choux.
 
 
-Modéliser le problème avec un graphe et proposer une solution.
+ModÃ©liser le problÃ¨me avec un graphe et proposer une solution.
 \end{exo}
 
 \begin{exo}
-On considère un site Web statique, installé sur un serveur. On se pose les
-questions suivantes, liées à l'ergonomie du site~:
+On considÃ¨re un site Web statique, installÃ© sur un serveur. On se pose les
+questions suivantes, liÃ©es Ã  l'ergonomie du site~:
 \begin{enumerate}
-\item Puis-je à l'aide de la souris uniquement accéder à toutes les pages du
-  site à partir de la page d'accueil~?
-\item Puis-je toujours en un clic retourner à la page d'accueil~?
-\item Puis-je, à partir de n'importe quelle page, accéder à n'importe quelle
+\item Puis-je Ã  l'aide de la souris uniquement accÃ©der Ã  toutes les pages du
+  site Ã  partir de la page d'accueil~?
+\item Puis-je toujours en un clic retourner Ã  la page d'accueil~?
+\item Puis-je, Ã  partir de n'importe quelle page, accÃ©der Ã  n'importe quelle
   autre page en moins de 3 clics~?
 \end{enumerate}
 
-Proposer une modélisation de cette situation par un graphe, puis décrire des
-algorithmes pour répondre aux questions posées. 
+Proposer une modÃ©lisation de cette situation par un graphe, puis dÃ©crire des
+algorithmes pour rÃ©pondre aux questions posÃ©es. 
 
 \end{exo}
 
@@ -524,20 +522,20 @@ algorithmes pour r
 \draw (1.5-0.1,3.25) [fill=white]rectangle +(0.2,.5);
 \draw (1.5-0.1,2.25) [fill=white]rectangle +(0.2,.5);
 \end{tikzpicture}
-\caption{Plan du musée 1}\label{m1}
+\caption{Plan du musÃ©e 1}\label{m1}
 \end{figure}
 
 
 \begin{exo}
-On considère le musée décrit dans la figure~\ref{m1}. Le directeur
+On considÃ¨re le musÃ©e dÃ©crit dans la figure~\ref{m1}. Le directeur
 souhaite, pour une exposition exceptionnelle, placer un gardien dans chaque
 salle. Il recrute pour cela des gardiens espagnols (qui ne parlent que
 l'espagnol) et des gardiens italiens (qui ne parlent qu'italien). Afin qu'il
-ne discutent pas entre eux, il ne veut pas que deux gardiens de la même
-nationalité soient dans des salles voisines. Est-ce possible~?
+ne discutent pas entre eux, il ne veut pas que deux gardiens de la mÃªme
+nationalitÃ© soient dans des salles voisines. Est-ce possible~?
 
 \bigskip
-Même question avec le musée de la figure~\ref{m2}.
+MÃªme question avec le musÃ©e de la figure~\ref{m2}.
 
 \begin{figure}[h]
 \begin{tikzpicture}
@@ -564,33 +562,33 @@ M
 %\draw (1.5-0.1,3.25) [fill=white]rectangle +(0.2,.5);
 \draw (1.5-0.1,2.25) [fill=white]rectangle +(0.2,.5);
 \end{tikzpicture}
-\caption{Plan du musée 2}\label{m2}
+\caption{Plan du musÃ©e 2}\label{m2}
 \end{figure}
 
 \bigskip
-Généraliser ce problème sur les graphes. Décrire un algorithme pour le
-résoudre~?
+GÃ©nÃ©raliser ce problÃ¨me sur les graphes. DÃ©crire un algorithme pour le
+rÃ©soudre~?
 \end{exo}
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \section{Codage des graphes}
 
-On s'intéresse maintenant à coder les graphes (en machine). Il y a deux
-méthodes principales (qui admettent des variantes), le codage par liste
+On s'intÃ©resse maintenant Ã  coder les graphes (en machine). Il y a deux
+mÃ©thodes principales (qui admettent des variantes), le codage par liste
 d'adjacence et le codage par matrice d'adjacence.
 
 
 \subsection{Codage par matrices d'adjacence}
 
-Soit $G=(V,E)$ un graphe. On suppose, sans perte de généralité, que
+Soit $G=(V,E)$ un graphe. On suppose, sans perte de gÃ©nÃ©ralitÃ©, que
 $V=\{1,\ldots,n\}$. On appelle {\bf matrice d'adjacence} de $V$ le tableau
 (matrice) de taille $n$ sur $n$ ne contenant que des $0$ ou des $1$ et
-défini par~: la case de la $i$-ème ligne et de la $j$-ième colonne contient
+dÃ©fini par~: la case de la $i$-Ã¨me ligne et de la $j$-iÃ¨me colonne contient
 un $1$ si et seulement si $(i,j)\in E$. 
 
-On considère par exemple le graphe 
-$(\{1,2,3,4\},\{(1,1),(1,2),(3,1),(2,4),(3,4)\})$ dessiné  sur la
+On considÃ¨re par exemple le graphe 
+$(\{1,2,3,4\},\{(1,1),(1,2),(3,1),(2,4),(3,4)\})$ dessinÃ©  sur la
 figure~\ref{fig:g1}. Sa matrice d'adjacence est 
 $$\left(
 \begin{array}{cccc}
@@ -602,7 +600,7 @@ $$\left(
 \right).
 $$
 
-Réciproquement, le graphe dont la matrice d'adjacence est 
+RÃ©ciproquement, le graphe dont la matrice d'adjacence est 
 $\left(
 \begin{array}{cccc}
 0 & 0 & 1 & 0\\
@@ -643,20 +641,20 @@ Dessiner le graphe dont la matrice d'adjacence est $\left(
 \right)$.
 
 \noindent
-Quel est la matrice d'adjacence du graphe où $V=\{1,\ldots,7\}$ et 
+Quel est la matrice d'adjacence du graphe oÃ¹ $V=\{1,\ldots,7\}$ et 
 $$E=\{(1,2),(4,2),(3,5),(7,1),(6,4),(1,5),(5,0) \}~?$$
 \end{exo}
 
 \begin{exo}
 Soit $(V,E)$ un graphe. Comment lit-on sur la matrice d'adjacence de ce
-graphe que la relation $E$ est réflexive~? symétrique~? antisymétrique~?
+graphe que la relation $E$ est rÃ©flexive~? symÃ©trique~? antisymÃ©trique~?
 \end{exo}
 
 
 \begin{exo}
-Pour tout graphe orienté $G$, on note $G^R$ le graphe défini par~: les
-sommets de $G^R$ sont les mêmes que ceux de $G$ et $(x,y)$ est une arête de 
- $G^R$ si et seulement si $(y,x) $ est une arête de $G$. Le graphe  $G^R$
+Pour tout graphe orientÃ© $G$, on note $G^R$ le graphe dÃ©fini par~: les
+sommets de $G^R$ sont les mÃªmes que ceux de $G$ et $(x,y)$ est une arÃªte de 
+ $G^R$ si et seulement si $(y,x) $ est une arÃªte de $G$. Le graphe  $G^R$
 s'appelle {\it miroir} de $G$. 
 
 \begin{figure}[h]
@@ -689,12 +687,12 @@ s'appelle {\it miroir} de $G$.
 
 \subsection{Codage par liste d'adjacence}
 
-Le codage d'un graphe par liste d'adjacence consiste à coder, pour chaque
+Le codage d'un graphe par liste d'adjacence consiste Ã  coder, pour chaque
 sommet du graphe, l'ensemble de ses voisins par une liste {\it
-  triée}\footnote{Attention, le fait qu'elle soit triée n'est pas toujours
-  imposé dans la littérature, mais c'est le choix que nous prendrons.}.
-On considère encore que $V=\{1,\ldots,n\}$. On dispose alors d'un tableau de
-taille $n$ dont la première case contient  la liste des voisins de $1$, la
+  triÃ©e}\footnote{Attention, le fait qu'elle soit triÃ©e n'est pas toujours
+  imposÃ© dans la littÃ©rature, mais c'est le choix que nous prendrons.}.
+On considÃ¨re encore que $V=\{1,\ldots,n\}$. On dispose alors d'un tableau de
+taille $n$ dont la premiÃ¨re case contient  la liste des voisins de $1$, la
 seconde la liste des voisins de $2$, etc. 
 
 Par exemple, le graphe de la figure~\ref{fig:g1} se code par le tableau de
@@ -743,7 +741,7 @@ liste~:
 
 
 \begin{exo}
-Dessiner le graphe dont la représentation par liste d'adjacence est~:
+Dessiner le graphe dont la reprÃ©sentation par liste d'adjacence est~:
 
 \medskip
 \begin{center}
@@ -820,47 +818,47 @@ Dessiner le graphe dont la repr
 \end{exo}
 
 \begin{exo}
-Dessiner la représentation par liste d'adjacence du graphe de la
+Dessiner la reprÃ©sentation par liste d'adjacence du graphe de la
 figure~\ref{fig:grapheexo1}.
 \end{exo}
 
 
 \begin{exo}\label{titi}
-On considère que l'on code en Python un graphe par liste d'adjacence de la
-manière suivante~:
+On considÃ¨re que l'on code en Python un graphe par liste d'adjacence de la
+maniÃ¨re suivante~:
 \begin{itemize}
 \item Un graphe un un couple de la forme $(V,E)$,
-\item $V$ est une liste d'éléments tous différents, triés,
-\item $E$ est un dictionnaire qui à chaque élément de $V$ associe la liste
-  triée de ses voisins.
+\item $V$ est une liste d'Ã©lÃ©ments tous diffÃ©rents, triÃ©s,
+\item $E$ est un dictionnaire qui Ã  chaque Ã©lÃ©ment de $V$ associe la liste
+  triÃ©e de ses voisins.
 \end{itemize}
 
 
 \begin{enumerate}
-\item Dessiner le graphe correspondant à \\
+\item Dessiner le graphe correspondant Ã  \\
 {\tt ([1,2,3],\{1:[2],2:[2,3],3:[1,3]\})}
-\item Écrire une fonction qui teste si un coupe $(V,E)$ où $V$ est une liste
-  d'entiers et $E$ un dictionnaire, représente bien un graphe par liste
+\item Ãcrire une fonction qui teste si un coupe $(V,E)$ oÃ¹ $V$ est une liste
+  d'entiers et $E$ un dictionnaire, reprÃ©sente bien un graphe par liste
   d'adjacence. 
 
-\item Écrire une fonction qui compte le nombre d'arêtes d'un graphe.
+\item Ãcrire une fonction qui compte le nombre d'arÃªtes d'un graphe.
 
-\item Écrire une fonction qui teste si $(i,j)$ est une arête d'un graphe. 
+\item Ãcrire une fonction qui teste si $(i,j)$ est une arÃªte d'un graphe. 
 
 \item On appelle {\it sommet bloquant} un sommet $i$ tel que pour tout
-  sommet $j$, $(i,j)$ n'est pas une arête. Écrire une fonction qui teste
+  sommet $j$, $(i,j)$ n'est pas une arÃªte. Ãcrire une fonction qui teste
   si un sommet est bloquant.
 
 \item On appelle {\it sommet puits} un sommet $i$ tel que pour tout
-  sommet $j\neq i$, $(i,j)$ n'est pas une arête et tel que $(i,i)$ soit
-  une arête. Écrire une fonction qui teste
+  sommet $j\neq i$, $(i,j)$ n'est pas une arÃªte et tel que $(i,i)$ soit
+  une arÃªte. Ãcrire une fonction qui teste
   si un sommet est un puits.
 
-\item Écrire une fonction qui ajoute une arête $(i,j)$ à un graphe. 
+\item Ãcrire une fonction qui ajoute une arÃªte $(i,j)$ Ã  un graphe. 
 
-\item Écrire une fonction qui supprime une arête $(i,j)$ à un graphe (on
-  rappelle que la méthode {\tt remove} de python retire la première
-  occurrence d'une valeur donnée en paramètre).
+\item Ãcrire une fonction qui supprime une arÃªte $(i,j)$ Ã  un graphe (on
+  rappelle que la mÃ©thode {\tt remove} de python retire la premiÃ¨re
+  occurrence d'une valeur donnÃ©e en paramÃ¨tre).
 
 \end{enumerate}
  
@@ -883,40 +881,40 @@ mani
 L'exercice suivant est une introduction aux parcours de graphes. 
 
 \begin{exo}
-On considère le graphe de la figure~\ref{fig:zomb}. Il y a une flèche entre
-$x$ et $y$ si $x$ connaît l'adresse de $y$. On considère aussi que certains
-individus dans cette liste peuvent être des zombies. 
+On considÃ¨re le graphe de la figure~\ref{fig:zomb}. Il y a une flÃ¨che entre
+$x$ et $y$ si $x$ connaÃ®t l'adresse de $y$. On considÃ¨re aussi que certains
+individus dans cette liste peuvent Ãªtre des zombies. 
 \begin{enumerate}
-\item On considère que chaque nuit, un zombie va mordre et donc transformer
-  en zombie des individus dont il connaît l'adresse et qui ne sont pas encore
+\item On considÃ¨re que chaque nuit, un zombie va mordre et donc transformer
+  en zombie des individus dont il connaÃ®t l'adresse et qui ne sont pas encore
   zombies. Si c'est possible, chaque zombie transforme au moins
-  un zombie par nuit. En supposant qu'au départ seule Karina est un zombie,
-  donner quelques possibilités indiquant, in fine, qui  zombifie qui?
-  Dessiner les solutions à l'aide d'un graphe où $(x,y)$ est une arête si
-  $x$ a zombifié $y$. 
+  un zombie par nuit. En supposant qu'au dÃ©part seule Karina est un zombie,
+  donner quelques possibilitÃ©s indiquant, in fine, qui  zombifie qui?
+  Dessiner les solutions Ã  l'aide d'un graphe oÃ¹ $(x,y)$ est une arÃªte si
+  $x$ a zombifiÃ© $y$. 
 
-\item On considère maintenant que chaque nuit, chaque zombie va transformer
-  tous les individus  dont il connaît l'adresse et qui ne sont pas encore
-  zombies.  En supposant qu'au départ seule Karina est un zombie,
-  donner quelques possibilités indiquant, in fine, qui  zombifie qui?
+\item On considÃ¨re maintenant que chaque nuit, chaque zombie va transformer
+  tous les individus  dont il connaÃ®t l'adresse et qui ne sont pas encore
+  zombies.  En supposant qu'au dÃ©part seule Karina est un zombie,
+  donner quelques possibilitÃ©s indiquant, in fine, qui  zombifie qui?
 
 \item On suppose maintenant que chaque zombie doit non seulement  transformer
-  tous les individus  dont il connaît l'adresse et qui ne sont pas encore
-  zombies, mais aussi dans l'ordre croissant de leur numéros. Par exemple,
+  tous les individus  dont il connaÃ®t l'adresse et qui ne sont pas encore
+  zombies, mais aussi dans l'ordre croissant de leur numÃ©ros. Par exemple,
   Karina transformera dans l'ordre Raph, Mike puis David. On suppose de plus
-  que chaque nuit les zombies vont mordre à tour de rôle, en commençant par
-  celui qui à été transformé en zombies le plus anciennement.   En supposant
-  qu'au départ seule Karina est un zombie. Écrire qui  zombifie qui, et dans
+  que chaque nuit les zombies vont mordre Ã  tour de rÃ´le, en commenÃ§ant par
+  celui qui Ã  Ã©tÃ© transformÃ© en zombies le plus anciennement.   En supposant
+  qu'au dÃ©part seule Karina est un zombie. Ãcrire qui  zombifie qui, et dans
   quel ordre.  
 
 \item On suppose maintenant que chaque nuit, un zombie dont aucun voisin
   (au sens des graphes) 
-  n'est zombie va mordre le premier (par ordre de numéro) des individus non
-  zombies qu'il connaît qui n'est pas encore zombie. Un zombie qui a au moins
+  n'est zombie va mordre le premier (par ordre de numÃ©ro) des individus non
+  zombies qu'il connaÃ®t qui n'est pas encore zombie. Un zombie qui a au moins
   un voisin zombie ne fait rien la nuit, il attend.  Un zombie dont tous les
-  voisins sont devenus eux aussi des zombies se transforme en poussière. 
+  voisins sont devenus eux aussi des zombies se transforme en poussiÃ¨re. 
  En supposant
-  qu'au départ seule Karina est un zombie, Écrire qui a zombifié qui, et dans
+  qu'au dÃ©part seule Karina est un zombie, Ãcrire qui a zombifiÃ© qui, et dans
   quel ordre.  
 
 
@@ -961,8 +959,8 @@ individus dans cette liste peuvent 
 \end{exo}
 
 
-Les graphes obtenus dans les questions de l'exercice précédent s'appellent
-des {\it arbres couvrants}. La façon de procéder de la question~3 s'appelle
+Les graphes obtenus dans les questions de l'exercice prÃ©cÃ©dent s'appellent
+des {\it arbres couvrants}. La faÃ§on de procÃ©der de la question~3 s'appelle
 {\it parcours en largeur} et celle de la question~4 s'appelle {\it parcours
   en profondeur}. 
 
@@ -979,39 +977,39 @@ Un {\bf arbre} est un graphe $G=(V,E)$ tel que~:
 
 \item[(2)] Si $(x,y)$ et $(z,y)$ sont dans $E$, alors $x=z$. 
 
-\item[(3)] Il existe un sommet $x_0$, appelé {\bf racine}, tel que pour
-  tout sommet $y$, il existe une chemin de $x_0$ à $y$.
+\item[(3)] Il existe un sommet $x_0$, appelÃ© {\bf racine}, tel que pour
+  tout sommet $y$, il existe une chemin de $x_0$ Ã  $y$.
 \end{enumerate}
 
-Un exemple d'arbre dont la racine est $1$ est dessiné sur la
+Un exemple d'arbre dont la racine est $1$ est dessinÃ© sur la
 figure~\ref{fig:arbre}.
 
 \begin{exo}
-Dessiner trois arbres différents à 6 sommets.
+Dessiner trois arbres diffÃ©rents Ã  6 sommets.
 \end{exo}
 
 
 \begin{exo}
-Dessiner un graphe qui vérifie $(1)$ et $(2)$ de la définition mais qui
-n'est pas un arbre. Même question avec $(2)$ et $(3)$. Même question avec
+Dessiner un graphe qui vÃ©rifie $(1)$ et $(2)$ de la dÃ©finition mais qui
+n'est pas un arbre. MÃªme question avec $(2)$ et $(3)$. MÃªme question avec
 $(3)$ et $(1)$.
 \end{exo}
 
 \medskip
-Dans un arbre, on utilise à la fois une terminologie de type 
-\og {\it végétal}\fg{} et
+Dans un arbre, on utilise Ã  la fois une terminologie de type 
+\og {\it vÃ©gÃ©tal}\fg{} et
 aussi
-de type \og {\it arbre généalogique}\fg{}. 
+de type \og {\it arbre gÃ©nÃ©alogique}\fg{}. 
 On appelle {\bf feuille} tout sommet d'un arbre qui n'a pas de voisin.  Tout
-chemin de la racine à une feuille est appelée {\bf branche}. Les voisins
-d'un noeud sont appelés ses {\bf fils}. 
+chemin de la racine Ã  une feuille est appelÃ©e {\bf branche}. Les voisins
+d'un noeud sont appelÃ©s ses {\bf fils}. 
 Tous les sommets atteignables depuis un sommet $x$ sont dits les {\bf
-  descendants} de $x$ et ils constituent le {\bf sous-arbre} enraciné en $x$.
-Si $y$ est atteignable depuis $x$, alors $x$ est un {\bf ancêtre} de $y$. 
-Si $y$ est un voisin de $x$, alors $x$ est le {\bf père} de $y$. Deux sommets
-qui ont le même père sont {\bf frères}. 
+  descendants} de $x$ et ils constituent le {\bf sous-arbre} enracinÃ© en $x$.
+Si $y$ est atteignable depuis $x$, alors $x$ est un {\bf ancÃªtre} de $y$. 
+Si $y$ est un voisin de $x$, alors $x$ est le {\bf pÃ¨re} de $y$. Deux sommets
+qui ont le mÃªme pÃ¨re sont {\bf frÃ¨res}. 
 Par exemple, dans le dessin de la figure~\ref{fig:arbre},
-$6$ est le père de $7$, $3$ est un frère de $2$ et $5$ est une descendant de
+$6$ est le pÃ¨re de $7$, $3$ est un frÃ¨re de $2$ et $5$ est une descendant de
 $1$.  
 
 \begin{figure}
@@ -1046,32 +1044,32 @@ $1$.
 
 \begin{exo}
 Dans le graphe de la figure~\ref{fig:arbre}, quels sont les descendants de
-$3$? Les fils de $1$? Les ancêtres de $6$? les feuilles?
+$3$? Les fils de $1$? Les ancÃªtres de $6$? les feuilles?
 \end{exo}
 
 
-% \begin{exo}
-% On considère dans cet exercice des arbres codés par liste d'adjacence comme
-% dans l'exercice en Python de la page~\pageref{titi}. On suppose que la
-% racine est le premier sommet de la liste $V$.
-
-% \begin{enumerate}
-% \item Écrire une fonction qui compte le nombre de feuille d'un arbre.
-% \item Écrire une fonction qui compte le nombre de descendants d'un sommet
-%   donné. 
-% \end{enumerate}
-% \end{exo}
+\begin{exo}
+On considÃ¨re dans cet exercice des arbres codÃ©s par liste d'adjacence comme
+dans l'exercice en Python de la page~\pageref{titi}. On suppose que la
+racine est le premier sommet de la liste $V$.
+
+\begin{enumerate}
+\item Ãcrire une fonction qui compte le nombre de feuille d'un arbre.
+\item Ãcrire une fonction qui compte le nombre de descendants d'un sommet
+  donnÃ©. 
+\end{enumerate}
+\end{exo}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \subsection{Parcours d'arbres}
 
 
 Parcourir un arbre, c'est appliquer un algorithme qui va visiter, une et une
 seule fois chaque sommet de l'arbre. Les deux parcours les plus connus, sont
-les parcours préfixes et suffixes. A chaque visite de noeud,  une fonction
-{\tt Traiter} est appliquée, selon ce que l'on souhaite faire. 
+les parcours prÃ©fixes et suffixes. A chaque visite de noeud,  une fonction
+{\tt Traiter} est appliquÃ©e, selon ce que l'on souhaite faire. 
 
-Le parcours Préfixe est l'algorithme récursif suivant. Initialement, le
-parcours est lancé à la racine. 
+Le parcours PrÃ©fixe est l'algorithme rÃ©cursif suivant. Initialement, le
+parcours est lancÃ© Ã  la racine. 
 
 \begin{verbatim}
 Parcours-Prefixe(V,E,x):
@@ -1098,7 +1096,7 @@ $2$ $4$ $5$
 
 
 \noindent
-De même  {\tt Parcours-Prefixe(3)} retourne
+De mÃªme  {\tt Parcours-Prefixe(3)} retourne
 
 $3$ $6$ $7$ $8$ $9$
 
@@ -1109,7 +1107,7 @@ $1$ $2$ $4$ $5$ $3$ $6$ $7$ $8$ $9$
 
 
 \begin{exo}
-Que retourne l'algorithme de parcours préfixe sur l'arbre de la figure~\ref{fig:arbre2}.
+Que retourne l'algorithme de parcours prÃ©fixe sur l'arbre de la figure~\ref{fig:arbre2}.
 
 
 \begin{figure}
@@ -1144,8 +1142,8 @@ Que retourne l'algorithme de parcours pr
 \end{exo}
 
 \medskip
-La parcours suffixe est identique à la différence près que le traitement se
-fait après l'appel récursif. 
+La parcours suffixe est identique Ã  la diffÃ©rence prÃ¨s que le traitement se
+fait aprÃ¨s l'appel rÃ©cursif. 
 
 \begin{verbatim}
 Parcours-Suffixe(V,E,x):
@@ -1159,29 +1157,29 @@ Parcours-Suffixe(V,E,x):
 Que donne le parcours suffixe sur les arbres des figures~\ref{fig:arbre} et~\ref{fig:arbre2}?
 \end{exo}
 
-% \begin{exo}
-% Avec le même codage que précédemment, écrire en Python des fonctions de
-% parcours préfixe et suffixe.
-% \end{exo}
+\begin{exo}
+Avec le mÃªme codage que prÃ©cÃ©demment, Ã©crire en Python des fonctions de
+parcours prÃ©fixe et suffixe.
+\end{exo}
 
 %%%%%%%%%%%%%%%%%%%%%
 \subsection{Arbres couvrants}
 
-Attention, ici, on parle d'arbres couvrants de graphes orientés.
+Attention, ici, on parle d'arbres couvrants de graphes orientÃ©s.
 
-Soit $G=(V,E)$. Un arbre couvrant pour $G$, enraciné en $x\in V$, est un
+Soit $G=(V,E)$. Un arbre couvrant pour $G$, enracinÃ© en $x\in V$, est un
 arbre $(V^\prime,E^\prime)$ tel que
 \begin{enumerate}
 \item[(1)] $V^\prime\subseteq V$ et  $E^\prime\subseteq E$.
 \item[(2)] $x$ est la racine de $(V^\prime,E^\prime)$.
-\item[(3)] On ne peut pas rajouter à l'arbre un sommet ou une arête de sorte 
+\item[(3)] On ne peut pas rajouter Ã  l'arbre un sommet ou une arÃªte de sorte 
   que les conditions 
-  $(1)$ et $(2)$ soient toujours vérifiées: l'arbre est maximal. 
+  $(1)$ et $(2)$ soient toujours vÃ©rifiÃ©es: l'arbre est maximal. 
 \end{enumerate}
 
 Intuitivement un arbre couvrant est un arbre que l'on peut calquer sur un
 graphe -- conditions (1) et (2) -- sans pouvoir le prolonger.
-Considérons par exemple le graphe de la figure~\ref{fig:graphcouvrant}.
+ConsidÃ©rons par exemple le graphe de la figure~\ref{fig:graphcouvrant}.
 
 \begin{figure}[h]
 \begin{center}
@@ -1237,7 +1235,7 @@ Consid
 \end{figure}
 
 Dans ce graphe, l'arbre de gauche de la figure~\ref{fig:graphcouvrant2}
-vérifie bien $(1)$ et $(2)$ mais
+vÃ©rifie bien $(1)$ et $(2)$ mais
 pas $(3)$.  En revanche celui de droite est bien un arbre couvrant. 
 
 
@@ -1297,42 +1295,42 @@ pas $(3)$.  En revanche celui de droite est bien un arbre couvrant.
 \caption{Arbres non couvrant et couvrant}\label{fig:graphcouvrant2}
 \end{figure}
 
-% \begin{exo}
-% Écrire une fonction qui étant donné un graphe et un arbre codé en Python
-% comme précédemment, teste si l'arbre est un arbre couvrant du graphe (on ne
-% testera pas si c'est bien un arbre). 
-% \end{exo}
+\begin{exo}
+Ãcrire une fonction qui Ã©tant donnÃ© un graphe et un arbre codÃ© en Python
+comme prÃ©cÃ©demment, teste si l'arbre est un arbre couvrant du graphe (on ne
+testera pas si c'est bien un arbre). 
+\end{exo}
 
 
 L'objectif des algorithmes de parcours de graphes est de construire des
 arbres couvrants de graphes afin, ensuite, d'appliquer des parcours (type
-préfixe/suffixe) sur les arbres obtenus. Il existe deux constructions
-d'arbres couvrant très utilisées, appelées {\it parcours en largeur} et {\it
+prÃ©fixe/suffixe) sur les arbres obtenus. Il existe deux constructions
+d'arbres couvrant trÃ¨s utilisÃ©es, appelÃ©es {\it parcours en largeur} et {\it
   parcours en profondeur}. 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%
 \subsection{Parcours en largeur}
 
 
-On ne donne pas explicitement l'algorithme de parcours en largeur à partir
+On ne donne pas explicitement l'algorithme de parcours en largeur Ã  partir
 de $x$ qui
-demanderait l'introduction des structures de données. On se contente d'un
-pseudo-algorithme expliquant la méthode~:
+demanderait l'introduction des structures de donnÃ©es. On se contente d'un
+pseudo-algorithme expliquant la mÃ©thode~:
 \begin{enumerate}
 \item $x$ est la racine de l'arbre.
-\item On insère dans l'arbre tous les voisins de $x$ (sauf éventuellement
+\item On insÃ¨re dans l'arbre tous les voisins de $x$ (sauf Ã©ventuellement
   $x$), dans l'ordre. 
-\item On insère (dans l'ordre) dans l'arbre tous les voisins de la feuille
+\item On insÃ¨re (dans l'ordre) dans l'arbre tous les voisins de la feuille
   la plus anciennement introduite dans l'arbre et pour laquelle c'est possible.
-\item On recommence l'étape précédente tant que c'est possible. 
+\item On recommence l'Ã©tape prÃ©cÃ©dente tant que c'est possible. 
 \end{enumerate}
 
-Si l'on exécute le parcours sur le graphe de la
-figure~\ref{fig:graphcouvrant}, en partant du sommet $3$. Après les étapes
+Si l'on exÃ©cute le parcours sur le graphe de la
+figure~\ref{fig:graphcouvrant}, en partant du sommet $3$. AprÃ¨s les Ã©tapes
 $1$ et $2$ on a l'arbre $A_1$ de la figure~\ref{fig:parcourslargeur}. 
 La feuille introduite le plus anciennement
-(attention à l'ordre qui est l'ordre des numéro des sommets) est $2$. On
-ajoute donc $1$ et $6$ -- et pas $7$ qui y est déjà. On obtient alors
+(attention Ã  l'ordre qui est l'ordre des numÃ©ro des sommets) est $2$. On
+ajoute donc $1$ et $6$ -- et pas $7$ qui y est dÃ©jÃ . On obtient alors
 l'arbre $A_2$ de la figure~\ref{fig:parcourslargeur}.
 
 \begin{figure}[h]
@@ -1389,11 +1387,11 @@ l'arbre $A_2$ de la figure~\ref{fig:parcourslargeur}.
 Ensuite, la feuille la plus anciennement introduite est $4$. Son seul voisin
 est $9$ qui n'est pas encore dans l'arbre. On obtient donc l'arbre $A_3$
 de la figure~\ref{fig:parcourslargeurA3}.
-Ensuite il s'agit du sommet $5$ dont l'unique fils $3$ est déjà dans
-l'arbre. La construction n'évolue donc pas pour $5$. Ensuite, on a fini les
-fils de $3$, on passe donc aux fils du premier fils de $3$, à savoir $2$.
-Les fils de $1$ sont $2$, $6$ et $7$, qui sont déjà dans l'arbre.  En
-continuant ainsi, on voit qu'il n'y a plus rien à ajouter. On obtient donc
+Ensuite il s'agit du sommet $5$ dont l'unique fils $3$ est dÃ©jÃ  dans
+l'arbre. La construction n'Ã©volue donc pas pour $5$. Ensuite, on a fini les
+fils de $3$, on passe donc aux fils du premier fils de $3$, Ã  savoir $2$.
+Les fils de $1$ sont $2$, $6$ et $7$, qui sont dÃ©jÃ  dans l'arbre.  En
+continuant ainsi, on voit qu'il n'y a plus rien Ã  ajouter. On obtient donc
 l'arbre de la figure~\ref{fig:parcourslargeurA3}
 
 \begin{figure}[ht]
@@ -1435,8 +1433,8 @@ l'arbre de la figure~\ref{fig:parcourslargeurA3}
 \begin{exo}
 \begin{enumerate}
 \item Sur le graphe de la figure ci-dessous, dessiner les arbres
-obtenus par un parcours en largeur à partir de $2$. Même question en partant
-de $6$. Même question en partant de $9$. 
+obtenus par un parcours en largeur Ã  partir de $2$. MÃªme question en partant
+de $6$. MÃªme question en partant de $9$. 
 
 \begin{center}
 \begin{tikzpicture}[scale = 0.8]
@@ -1490,7 +1488,7 @@ de $6$. M
 \end{center}
 
 
-\item Même question à partir de $3$, puis de $0$, puis de $8$ sur le graphe de
+\item MÃªme question Ã  partir de $3$, puis de $0$, puis de $8$ sur le graphe de
 la figure~\ref{fig:exo}.
 
 \begin{figure}[h]
@@ -1583,30 +1581,30 @@ la figure~\ref{fig:exo}.
 \end{exo}
 
 
-% \begin{exo}
-% Écrire en Python l'algorithme de parcours en largeur pour un graphe codé par
-% liste d'adjacence. 
-% \end{exo}
+\begin{exo}
+Ãcrire en Python l'algorithme de parcours en largeur pour un graphe codÃ© par
+liste d'adjacence. 
+\end{exo}
 
 
-% \begin{exo}
-% Écrire en Python une fonction qui teste si un graphe donné par liste
-% d'adjacence est un arbre dont la racine est le plus petit sommet. 
-% \end{exo}
+\begin{exo}
+Ãcrire en Python une fonction qui teste si un graphe donnÃ© par liste
+d'adjacence est un arbre dont la racine est le plus petit sommet. 
+\end{exo}
 
 \begin{exo} 
 Les
 {\em composantes fortement connexes} d'un graphe sont des sous-ensembles de
-sommets telles que~: (1) tout sommet appartient à une composante fortement
+sommets telles que~: (1) tout sommet appartient Ã  une composante fortement
 connexe, (2) s'il existe un chemin de $p$ vers $q$ et un chemin de $q$ vers
-$p$, alors $p$ et $q$ doivent appartenir à la même composante fortement
-connexe~; et réciproquement.  
+$p$, alors $p$ et $q$ doivent appartenir Ã  la mÃªme composante fortement
+connexe~; et rÃ©ciproquement.  
 \begin{enumerate}
-\item Deux composantes fortement connexes sont-elles forcément
+\item Deux composantes fortement connexes sont-elles forcÃ©ment
   disjointes? Pourquoi? 
 \item Quels sont les composantes fortement connexes du graphe de la figure~\ref{fig:exo}.
 
-\item Décrire une méthode algorithmique pour trouver les composantes
+\item DÃ©crire une mÃ©thode algorithmique pour trouver les composantes
   fortement connexe d'un graphe. 
 \end{enumerate}
 \end{exo}
@@ -1614,7 +1612,7 @@ connexe~; et r
 
 % \begin{exo}
 % Comment utiliser un parcours en largeur pour trouver un chemin de taille la
-% plus courte possible entre deux sommets donnés?
+% plus courte possible entre deux sommets donnÃ©s?
 % \end{exo}
 
 %%%%%%%%%%%%%%%
@@ -1647,23 +1645,23 @@ connexe~; et r
 \end{figure}
 
 
-On ne donne pas explicitement l'algorithme de parcours en profondeur à partir
+On ne donne pas explicitement l'algorithme de parcours en profondeur Ã  partir
 de $x$ qui
-demanderait l'introduction des structures de données. On se contente d'un
-pseudo-algorithme expliquant la méthode~:
+demanderait l'introduction des structures de donnÃ©es. On se contente d'un
+pseudo-algorithme expliquant la mÃ©thode~:
 \begin{enumerate}
 \item $x$ est la racine de l'arbre.
-\item On insère dans l'arbre le premier voisin de $x$ (sauf éventuellement
+\item On insÃ¨re dans l'arbre le premier voisin de $x$ (sauf Ã©ventuellement
   $x$). 
-\item On insère  dans l'arbre le premier  voisins du sommet
-  le plus récemment introduit dans l'arbre et pour lequel c'est possible.
-\item On recommence l'étape précédente tant que c'est possible. 
+\item On insÃ¨re  dans l'arbre le premier  voisins du sommet
+  le plus rÃ©cemment introduit dans l'arbre et pour lequel c'est possible.
+\item On recommence l'Ã©tape prÃ©cÃ©dente tant que c'est possible. 
 \end{enumerate}
 
-On va appliquer la méthode sur l'arbre de la figure~\ref{fig:graphcouvrant},
-en partant du sommet $3$. L'arbre commence par $3$ à la racine. Puis on
-introduit le plus petit fils de $3$, c'est-à-dire $2$. La feuille la plus
-récente de l'arbre est $2$, donc on introduit le plus petit fils de $2$, à
+On va appliquer la mÃ©thode sur l'arbre de la figure~\ref{fig:graphcouvrant},
+en partant du sommet $3$. L'arbre commence par $3$ Ã  la racine. Puis on
+introduit le plus petit fils de $3$, c'est-Ã -dire $2$. La feuille la plus
+rÃ©cente de l'arbre est $2$, donc on introduit le plus petit fils de $2$, Ã 
 savoir $1$. A nouveau, on va introduire $6$, puis $9$. On obtient alors
 l'arbre de la figure~\ref{fig:prof1}.  
 
@@ -1671,7 +1669,7 @@ l'arbre de la figure~\ref{fig:prof1}.
 
 \pagebreak[3]
 \begin{exo}
-Donner les parcours en profondeur obtenus à partir de $0$, puis $8$, puis $7$
+Donner les parcours en profondeur obtenus Ã  partir de $0$, puis $8$, puis $7$
 sur le graphe de la figure~\ref{fig:exo}.
 
 
@@ -1761,13 +1759,13 @@ sur le graphe de la figure~\ref{fig:exo}.
 
 
 
-% \begin{exo}
-% Écrire en Python l'algorithme de parcours en profondeur pour un graphe codé par
-% liste d'adjacence. 
-% \end{exo}
+\begin{exo}
+Ãcrire en Python l'algorithme de parcours en profondeur pour un graphe codÃ© par
+liste d'adjacence. 
+\end{exo}
 
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
-%\input{automates}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Ã¹
+\input{automates}
 
 \end{document}
