\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}
-\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}
\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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\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)\}$~?
\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$};
\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$};
\end{tikzpicture}
}
\end{center}
-\caption{Représentation d'un graphe}\label{fig:g1}
+\caption{Représentation d'un graphe}\label{fig:g1}
\end{figure}
\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}
\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}
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}.
\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
\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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}
\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}
\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}
%\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}
\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\\
\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]
\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
\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}
\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}
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.
\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}.
\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}
\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):
\noindent
-De même {\tt Parcours-Prefixe(3)} retourne
+De même {\tt Parcours-Prefixe(3)} retourne
$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}
\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):
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}
\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.
\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]
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]
\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]
\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]
\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}
% \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}
%%%%%%%%%%%%%%%
\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}.
\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}.
-% \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}
