+\documentclass[]{report}
+\usepackage[a4paper]{geometry}
+\geometry{hmargin=1.5cm, vmargin=1.5cm }
+\usepackage[latin1]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage[french]{babel}
+\usepackage{amsmath,amssymb,latexsym,eufrak,euscript,array}
+
+
+\usepackage{pgf}
+\usepackage{tikz}
+\usepackage{pdfpages}
+\usetikzlibrary{arrows}
+\usetikzlibrary{automata}
+\usetikzlibrary{snakes}
+\usetikzlibrary{shapes}
+
+\usepackage[hang,centerlast]{subfigure}
+
+
+
+\newtheorem{definition}{Definition}
+\newtheorem{theoreme}[definition]{Théorème}
+\newtheorem{proposition}[definition]{Proposition}
+\newtheorem{exemple}[definition]{Exemple}
+
+\newtheorem{Exo}[definition]{Exercice}
+
+\newenvironment{exo}
+{\begin{Exo}{\rm }
+{}\end{Exo}\vspace{-1em}
+\begin{sf}}{\end{sf}}
+
+\def \A {\mathcal{A}}
+\def \B {\mathcal{B}}
+
+\title{Cours Mathématiques Discrètes
+ \\IUT Belfort Montbéliard}
+\author{{\sc Pierre-Cyrille HEAM}}
+
+
+%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\begin{document}
+
+\maketitle
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\chapter{Graphes finis orientés}
+
+
+%%%%%%%%%%%%%%%%
+\section{Premières définitions}
+
+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}.
+\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
+{\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)$.
+
+
+\begin{exo}
+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)\}$~?
+\item $V=\{1,2,3\}$ et $\emptyset$~?
+\item $V=\{1,2,3\}$ et $E=\{\{1,3\}\}$~?
+\item $V=\mathbb{N}$ et $E=\{(1,3)\}$~?
+\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
+ 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
+$$(\{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
+de dessiner un graphe.
+
+\begin{figure}[h]
+\begin{center}
+\subfigure[première possibilité]{
+\begin{tikzpicture}
+\node (1) at (0,0) {$1$};
+\node (2) at (4,0) {$2$};
+\node (3) at (2,-0.7) {$3$};
+\node (4) at (2,0.7) {$4$};
+\path[->,>=triangle 90] (1) edge[loop above] node [above] {} ();
+\path[->,>=triangle 90] (1) edge[] node [above] {} (2);
+\path[->,>=triangle 90] (3) edge[] node [above] {} (4);
+\path[->,>=triangle 90] (3) edge[] node [above] {} (1);
+\path[->,>=triangle 90] (2) edge[] node [above] {} (4);
+\end{tikzpicture}
+}\hspace*{3cm}
+\subfigure[deuxième possibilité]{
+\begin{tikzpicture}
+
+\node (1) at (0,0) {$1$};
+\node (2) at (3,0) {$2$};
+\node (3) at (2,-0.7) {$3$};
+\node (4) at (5,-0.7) {$4$};
+\path[->,>=triangle 90] (1) edge[loop above] node [above] {} ();
+\path[->,>=triangle 90] (1) edge[] node [above] {} (2);
+\path[->,>=triangle 90] (3) edge[] node [above] {} (4);
+\path[->,>=triangle 90] (3) edge[] node [above] {} (1);
+\path[->,>=triangle 90] (2) edge[] node [above] {} (4);
+\end{tikzpicture}
+}
+\end{center}
+\caption{Représentation d'un graphe}\label{fig:g1}
+\end{figure}
+
+
+\begin{exo}
+Dessiner les graphes suivants.
+\begin{enumerate}
+\item $V=\{1,2,3,4,5\}$ et $E=\{(1,2),(2,1),(3,4),(4,4),(4,5),(5,3)\}$.
+\item $V=\{1,2,3,4,5\}$ et $E=\{(1,4),(4,1),(3,4),(4,4),(4,5),(5,3)\}$.
+\end{enumerate}
+Donner sous forme ensembliste ($V$ et $E$) le graphe suivant~:
+
+\begin{center}
+\begin{tikzpicture}
+\node (1) at (0,0) {$1$};
+\node (2) at (4,0) {$2$};
+\node (3) at (2,-1) {$3$};
+\node (4) at (2,1) {$4$};
+\path[->,>=triangle 90] (1) edge[bend left] node [above] {} (3);
+\path[->,>=triangle 90] (2) edge[] node [above] {} (1);
+\path[->,>=triangle 90] (3) edge[bend left] node [above] {} (1);
+\path[->,>=triangle 90] (3) edge[] node [above] {} (2);
+\path[->,>=triangle 90] (3) edge[] node [above] {} (4);
+\path[->,>=triangle 90] (4) edge[] node [above] {} (2);
+\end{tikzpicture}
+\end{center}
+
+Le dessin ci-dessous représente-t-il un graphe~? Si oui le donner
+explicitement, sinon dire pourquoi.
+
+\begin{center}
+\begin{tikzpicture}
+\node (1) at (0,0) {$1$};
+\node (2) at (4,0) {$2$};
+\node (3) at (2,-1) {$3$};
+\node (4) at (2,1) {$4$};
+\path[->,>=triangle 90] (1) edge[bend left] node [above] {} (3);
+\path[->,>=triangle 90] (2) edge[] node [above] {} (1);
+\path[->,>=triangle 90] (1) edge[bend right] node [above] {} (3);
+\path[->,>=triangle 90] (3) edge[] node [above] {} (2);
+\path[->,>=triangle 90] (3) edge[] node [above] {} (4);
+\path[->,>=triangle 90] (4) edge[] node [above] {} (2);
+\end{tikzpicture}
+\end{center}
+
+
+\end{exo}
+
+
+Dans un graphe, les {\bf voisins} d'un sommet $x$ sont tous les sommets $y$
+tels que $(x,y)$ soit dans~$E$.
+
+\begin{exo}
+Pour le graphe de la figure~\ref{fig:grapheexo1}, quels
+sont les voisins de $3$~? de $7$~? Quels sommets ont $9$ pour voisin~?
+\begin{figure}[h]
+\begin{tikzpicture}[scale = 0.8]
+\node (0) at (-2,-1) {0};
+
+\node (1) at (0,0) {1};
+\node (2) at (3,0) {2};
+\node (3) at (6,0) {3};
+\node (4) at (9,0) {4};
+\node (5) at (12,0) {5};
+
+\node (6) at (0,-2) {6};
+\node (7) at (3,-2) {7};
+\node (8) at (6,-2) {8};
+\node (9) at (9,-2) {9};
+\node (10) at (12,-2) {10};
+
+\node (11) at (15,0) {11};
+\node (12) at (15,-2) {12};
+
+\node (13) at (0,-4) {13};
+\node (14) at (3,-4) {14};
+\node (15) at (6,-4) {15};
+\node (16) at (9,-4) {16};
+\node (17) at (12,-4) {17};
+\node (18) at (15,-4) {18};
+
+
+
+\path[->,>=triangle 90] (0) edge[] node [swap] {} (1);
+\path[->,>=triangle 90] (0) edge[] node [swap] {} (2);
+\path[->,>=triangle 90] (0) edge[out=60, in =120] node [swap] {} (3);
+
+\path[->,>=triangle 90] (1) edge[] node [swap] {} (2);
+\path[->,>=triangle 90] (1) edge[] node [swap] {} (6);
+\path[->,>=triangle 90] (1) edge[] node [swap] {} (7);
+\path[->,>=triangle 90] (2) edge[] node [swap] {} (7);
+\path[->,>=triangle 90] (2) edge[] node [swap] {} (6);
+
+\path[->,>=triangle 90] (2) edge[loop] node [swap] {} (2);
+
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (7);
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (4);
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (2);
+
+\path[->,>=triangle 90] (4) edge[] node [swap] {} (9);
+\path[->,>=triangle 90] (5) edge[] node [swap] {} (9);
+\path[->,>=triangle 90] (5) edge[] node [swap] {} (11);
+\path[->,>=triangle 90] (5) edge[] node [swap] {} (12);
+\path[->,>=triangle 90] (3) edge[out=45,in=135] node [swap] {} (5);
+
+
+
+\path[->,>=triangle 90] (6) edge[] node [swap] {} (14);
+\path[->,>=triangle 90] (6) edge[out=-20, in =-160] node [swap] {} (9);
+
+\path[->,>=triangle 90] (7) edge[] node [swap] {} (13);
+\path[->,>=triangle 90] (7) edge[] node [swap] {} (15);
+
+
+\path[->,>=triangle 90] (8) edge[out=-20, in =-160] node [swap] {} (10);
+
+\path[->,>=triangle 90] (8) edge[] node [swap] {} (2);
+\path[->,>=triangle 90] (8) edge[] node [swap] {} (4);
+\path[->,>=triangle 90] (8) edge[] node [swap] {} (14);
+\path[->,>=triangle 90] (8) edge[] node [swap] {} (15);
+
+\path[->,>=triangle 90] (9) edge[] node [swap] {} (3);
+\path[->,>=triangle 90] (9) edge[] node [swap] {} (8);
+\path[->,>=triangle 90] (9) edge[] node [swap] {} (16);
+
+\path[->,>=triangle 90] (10) edge[] node [swap] {} (4);
+\path[->,>=triangle 90] (10) edge[] node [swap] {} (5);
+\path[->,>=triangle 90] (10) edge[] node [swap] {} (17);
+
+\path[->,>=triangle 90] (12) edge[] node [swap] {} (10);
+
+\path[->,>=triangle 90] (13) edge[] node [swap] {} (0);
+\path[->,>=triangle 90] (16) edge[] node [swap] {} (17);
+\path[->,>=triangle 90] (17) edge[] node [swap] {} (18);
+\path[->,>=triangle 90] (18) edge[out=-160, in =-20] node [swap] {} (16);
+
+\end{tikzpicture}
+\caption{Graphe 1}\label{fig:grapheexo1}
+\end{figure}
+
+\end{exo}
+
+
+
+\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$.
+\end{exo}
+
+\begin{exo}
+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
+$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~?
+\end{exo}
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Chemins, boucles et circuits}
+
+
+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}
+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).
+
+
+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
+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
+ boucle}.
+
+
+\begin{exo}
+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 taille au moins $10$.
+\end{enumerate}
+\end{exo}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%ùù
+\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.
+
+\begin{exo}
+On considère le plan ci-dessous d'un musée. La porte d'entrée est en bas à
+gauche.
+
+\bigskip
+
+\begin{tikzpicture}
+
+\draw (0,0) rectangle +(6,4);
+\draw (0,0) rectangle +(1.5,1);
+\draw (0,0) rectangle +(1.5,2);
+\draw (0,0) rectangle +(1.5,3);
+\draw (0,0) rectangle +(1.5,4);
+\draw (1.5,2) rectangle +(1.5,2);
+\draw (1.5,1) rectangle +(3,3);
+\draw (0,0) rectangle +(4.5,1);
+
+\draw (0.5,-0.1) [fill=white]rectangle +(0.5,.2) ;
+\draw (0.5,0.9) [fill=white]rectangle +(0.5,.2);
+\draw (0.5,3-0.1) [fill=white]rectangle +(0.5,.2);
+\draw (2,1-0.1) [fill=white]rectangle +(0.5,.2);
+
+
+\draw (1.5-0.1,0.25) [fill=white]rectangle +(0.2,.5);
+\draw (4.5-0.1,0.25) [fill=white]rectangle +(0.2,.5);
+\draw (4.5-0.1,2.25) [fill=white]rectangle +(0.2,.5);
+\draw (3-0.1,2.75) [fill=white]rectangle +(0.2,.5);
+\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}
+
+\begin{enumerate}
+\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
+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
+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.
+
+\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
+ utilisant le vocabulaire des graphes.
+
+\end{enumerate}
+
+\end{exo}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\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.
+
+\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
+ 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
+ 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
+(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.
+
+\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
+ 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 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
+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
+ position.
+\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.
+\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
+$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
+suivantes~:
+
+\begin{enumerate}
+\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 Il y a deux enfants qui se voient l'un l'autre.
+\item Tout enfant voit au moins un autre enfant.
+\end{enumerate}
+\end{exo}
+
+
+\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,
+malheureusement aussi, il ne peut laisser sur une rive seul le loup avec la
+chèvre, ni la chèvre avec le choux.
+
+
+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~:
+\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
+ 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.
+
+\end{exo}
+
+
+
+\begin{figure}[t]
+\begin{tikzpicture}
+
+\draw (0,0) rectangle +(6,4);
+\draw (0,0) rectangle +(1.5,1);
+\draw (0,0) rectangle +(1.5,2);
+\draw (0,0) rectangle +(1.5,3);
+\draw (0,0) rectangle +(1.5,4);
+\draw (1.5,2) rectangle +(1.5,2);
+\draw (1.5,1) rectangle +(3,3);
+\draw (0,0) rectangle +(4.5,1);
+
+\draw (0.5,-0.1) [fill=white]rectangle +(0.5,.2) ;
+\draw (0.5,0.9) [fill=white]rectangle +(0.5,.2);
+\draw (0.5,3-0.1) [fill=white]rectangle +(0.5,.2);
+\draw (2,1-0.1) [fill=white]rectangle +(0.5,.2);
+
+
+\draw (1.5-0.1,0.25) [fill=white]rectangle +(0.2,.5);
+\draw (4.5-0.1,0.25) [fill=white]rectangle +(0.2,.5);
+\draw (4.5-0.1,2.25) [fill=white]rectangle +(0.2,.5);
+\draw (3-0.1,2.75) [fill=white]rectangle +(0.2,.5);
+\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}
+\end{figure}
+
+
+\begin{exo}
+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~?
+
+\bigskip
+Même question avec le musée de la figure~\ref{m2}.
+
+\begin{figure}[h]
+\begin{tikzpicture}
+
+\draw (0,0) rectangle +(6,4);
+\draw (0,0) rectangle +(1.5,1);
+\draw (0,0) rectangle +(1.5,2);
+\draw (0,0) rectangle +(1.5,3);
+\draw (0,0) rectangle +(1.5,4);
+\draw (1.5,2) rectangle +(1.5,2);
+\draw (1.5,1) rectangle +(3,3);
+\draw (0,0) rectangle +(4.5,1);
+
+\draw (0.5,-0.1) [fill=white]rectangle +(0.5,.2) ;
+\draw (0.5,0.9) [fill=white]rectangle +(0.5,.2);
+\draw (0.5,3-0.1) [fill=white]rectangle +(0.5,.2);
+\draw (2,1-0.1) [fill=white]rectangle +(0.5,.2);
+
+
+\draw (1.5-0.1,0.25) [fill=white]rectangle +(0.2,.5);
+%\draw (4.5-0.1,0.25) [fill=white]rectangle +(0.2,.5);
+\draw (4.5-0.1,2.25) [fill=white]rectangle +(0.2,.5);
+\draw (3-0.1,2.75) [fill=white]rectangle +(0.2,.5);
+%\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}
+\end{figure}
+
+\bigskip
+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
+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
+$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
+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
+figure~\ref{fig:g1}. Sa matrice d'adjacence est
+$$\left(
+\begin{array}{cccc}
+1 & 1 & 0 & 0\\
+0 & 0 & 0 & 1\\
+1 & 0 & 0 & 1\\
+0 & 0 & 0 & 0
+\end{array}
+\right).
+$$
+
+Réciproquement, le graphe dont la matrice d'adjacence est
+$\left(
+\begin{array}{cccc}
+0 & 0 & 1 & 0\\
+1 & 0 & 0 & 0\\
+1 & 1 & 0 & 1\\
+0 & 1 & 0 & 0
+\end{array}
+\right)
+$ est le graphe ci-dessous~:
+\bigskip
+
+\begin{center}
+\begin{tikzpicture}
+\node (1) at (0,0) {$1$};
+\node (2) at (4,0) {$2$};
+\node (3) at (2,-1) {$3$};
+\node (4) at (2,1) {$4$};
+\path[->,>=triangle 90] (1) edge[bend left] node [above] {} (3);
+\path[->,>=triangle 90] (2) edge[] node [above] {} (1);
+\path[->,>=triangle 90] (3) edge[bend left] node [above] {} (1);
+\path[->,>=triangle 90] (3) edge[] node [above] {} (2);
+\path[->,>=triangle 90] (3) edge[] node [above] {} (4);
+\path[->,>=triangle 90] (4) edge[] node [above] {} (2);
+\end{tikzpicture}
+\end{center}
+
+
+\begin{exo}
+Dessiner le graphe dont la matrice d'adjacence est $\left(
+\begin{array}{cccccc}
+1 & 1 & 1 & 0 & 0 & 0\\
+1 & 0 & 1 & 0 & 1 & 0\\
+0 & 1 & 1 & 0 & 0 & 1\\
+0 & 1 & 0 & 0 & 1 & 1\\
+1 & 0 & 0 & 0 & 0 & 0\\
+0 & 0 & 1 & 1 & 0 & 0\\
+\end{array}
+\right)$.
+
+\noindent
+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~?
+\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$
+s'appelle {\it miroir} de $G$.
+
+\begin{figure}[h]
+\begin{center}
+\begin{tikzpicture}[scale=0.7]
+\node (1) at (0,0) [draw,state] {$1$};
+\node (2) at (3,0) [draw,state] {$2$};
+\node (3) at (6,0) [draw,state] {$3$};
+\node (4) at (9,0) [draw,state] {$4$};
+\path[->,thick,draw] (1) -- (2);
+\path[->,thick,draw] (2) -- (3);
+\path[->,thick,draw] (3) edge[out=-45] node [swap] {} (4);
+\path[->,thick,draw] (4) edge[out=-135,in=45] node [swap] {} (3);
+\path[->,thick,draw] (1) edge[loop above] node [] {} (1);
+\end{tikzpicture}
+\end{center}
+\caption{}\label{fig-exo1}
+\end{figure}
+
+\begin{enumerate}
+\item Dessiner le graphe miroir du graphe de la figure~\ref{fig-exo1}.
+\item Soit $A$ la matrice d'adjacence d'un graphe $G$. Quelle est la matrice
+ d'adjacence de $G^R$, en fonction de $A$~?
+\item Justifier que $(G^R)^R=G$ pour tout graphe $G$.
+\item Justifier que si $G$ contient une boucle de longueur $k$, alors $G^R$
+ aussi.
+\end{enumerate}
+
+\end{exo}
+
+\subsection{Codage par liste d'adjacence}
+
+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
+seconde la liste des voisins de $2$, etc.
+
+Par exemple, le graphe de la figure~\ref{fig:g1} se code par le tableau de
+liste~:
+
+\medskip
+\begin{center}
+\begin{tikzpicture}
+\node[draw,minimum width=0.5cm,minimum height=0.5cm] (1) at (0,0) {};
+\node[draw,minimum width=0.5cm,minimum height=0.5cm] (2) at (0,-0.5) {};
+\node[draw,minimum width=0.5cm,minimum height=0.5cm] (3) at (0,-1) {};
+\node[draw,minimum width=0.5cm,minimum height=0.5cm] (4) at (0,-1.5) {};
+\node (1a) at (0,0) {};
+\node (2a) at (0,-0.5) {};
+\node (3a) at (0,-1) {};
+\node (4a) at (0,-1.5) {};
+
+
+\node (11) at (1,0) {$1$};
+\node (12) at (2,0) {$2$};
+\node (13) at (4,0) {NULL};
+
+\node (21) at (1,-0.5) {$4$};
+\node (22) at (3,-0.5) {NULL};
+
+\node (31) at (1,-1) {$1$};
+\node (32) at (2,-1) {$4$};
+\node (33) at (4,-1) {NULL};
+
+\node (41) at (2,-1.5) {NULL};
+\path[->,>=triangle 90] (1a) edge[] node [above] {} (11);
+\path[->,>=triangle 90] (11) edge[] node [above] {} (12);
+\path[->,>=triangle 90] (12) edge[] node [above] {} (13);
+
+\path[->,>=triangle 90] (2a) edge[] node [above] {} (21);
+\path[->,>=triangle 90] (21) edge[] node [above] {} (22);
+
+\path[->,>=triangle 90] (3a) edge[] node [above] {} (31);
+\path[->,>=triangle 90] (31) edge[] node [above] {} (32);
+\path[->,>=triangle 90] (32) edge[] node [above] {} (33);
+\path[->,>=triangle 90] (4a) edge[] node [above] {} (41);
+
+
+\end{tikzpicture}
+\end{center}
+
+
+\begin{exo}
+Dessiner le graphe dont la représentation par liste d'adjacence est~:
+
+\medskip
+\begin{center}
+\begin{tikzpicture}
+\node[draw,minimum width=0.5cm,minimum height=0.5cm] (1) at (0,0) {};
+\node[draw,minimum width=0.5cm,minimum height=0.5cm] (2) at (0,-0.5) {};
+\node[draw,minimum width=0.5cm,minimum height=0.5cm] (3) at (0,-1) {};
+\node[draw,minimum width=0.5cm,minimum height=0.5cm] (4) at (0,-1.5) {};
+\node[draw,minimum width=0.5cm,minimum height=0.5cm] (5) at (0,-2) {};
+\node[draw,minimum width=0.5cm,minimum height=0.5cm] (6) at (0,-2.5) {};
+\node (1a) at (0,0) {};
+\node (2a) at (0,-0.5) {};
+\node (3a) at (0,-1) {};
+\node (4a) at (0,-1.5) {};
+\node (5a) at (0,-2) {};
+\node (6a) at (0,-2.5) {};
+
+
+\node (11) at (1,0) {$2$};
+\node (12) at (2,0) {$5$};
+\node (13) at (4,0) {NULL};
+
+\node (21) at (1,-0.5) {$3$};
+\node (22) at (3,-0.5) {NULL};
+
+\node (31) at (1,-1) {$1$};
+\node (32) at (2,-1) {$4$};
+\node (33) at (3,-1) {$5$};
+\node (34) at (4,-1) {$6$};
+\node (35) at (6,-1) {NULL};
+
+\node (41) at (1,-1.5) {$2$};
+\node (42) at (3,-1.5) {NULL};
+
+\node (51) at (2,-2) {NULL};
+
+
+\node (61) at (1,-2.5) {$2$};
+\node (62) at (2,-2.5) {$3$};
+\node (63) at (3,-2.5) {$4$};
+\node (64) at (4,-2.5) {$6$};
+\node (65) at (6,-2.5) {NULL};
+\path[->,>=triangle 90] (1a) edge[] node [above] {} (11);
+\path[->,>=triangle 90] (11) edge[] node [above] {} (12);
+\path[->,>=triangle 90] (12) edge[] node [above] {} (13);
+
+\path[->,>=triangle 90] (2a) edge[] node [above] {} (21);
+\path[->,>=triangle 90] (21) edge[] node [above] {} (22);
+
+\path[->,>=triangle 90] (3a) edge[] node [above] {} (31);
+\path[->,>=triangle 90] (31) edge[] node [above] {} (32);
+\path[->,>=triangle 90] (32) edge[] node [above] {} (33);
+\path[->,>=triangle 90] (33) edge[] node [above] {} (34);
+\path[->,>=triangle 90] (34) edge[] node [above] {} (35);
+
+
+\path[->,>=triangle 90] (4a) edge[] node [above] {} (41);
+\path[->,>=triangle 90] (41) edge[] node [above] {} (42);
+
+
+\path[->,>=triangle 90] (5a) edge[] node [above] {} (51);
+
+
+\path[->,>=triangle 90] (6a) edge[] node [above] {} (61);
+\path[->,>=triangle 90] (61) edge[] node [above] {} (62);
+\path[->,>=triangle 90] (62) edge[] node [above] {} (63);
+\path[->,>=triangle 90] (63) edge[] node [above] {} (64);
+\path[->,>=triangle 90] (64) edge[] node [above] {} (65);
+
+\end{tikzpicture}
+\end{center}
+
+
+\end{exo}
+
+\begin{exo}
+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~:
+\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.
+\end{itemize}
+
+
+\begin{enumerate}
+\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
+ d'adjacence.
+
+\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 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
+ 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
+ si un sommet est un puits.
+
+\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).
+
+\end{enumerate}
+
+\end{exo}
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\chapter{Parcours de Graphes}
+
+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.
+\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
+ 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$.
+
+\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,
+ 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
+ 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
+ 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.
+ En supposant
+ qu'au départ seule Karina est un zombie, Écrire qui a zombifié qui, et dans
+ quel ordre.
+
+
+\end{enumerate}
+
+\begin{figure}[h]
+\begin{center}
+\begin{tikzpicture}
+
+\node (1) at (0,0) {Raph (1)};
+\node (2) at (-2,-2) {Jeff (2)};
+\node (3) at (0,-3) {Peter (3)};
+\node (4) at (2,-2) {Chris (4)};
+\node (5) at (0,2) {Mike (5)};
+\node (6) at (-3,2) {Karina (6)};
+\node (7) at (-3,0) {David (7)};
+\node (8) at (3,0) {John-Claude (8)};
+
+\path[->,>=triangle 90] (6) edge[] node [above] {} (5);
+\path[->,>=triangle 90] (6) edge[] node [above] {} (7);
+\path[->,>=triangle 90] (6) edge[] node [above] {} (1);
+
+\path[->,>=triangle 90] (1) edge[] node [above] {} (5);
+\path[->,>=triangle 90] (1) edge[] node [above] {} (7);
+\path[->,>=triangle 90] (1) edge[] node [above] {} (8);
+\path[->,>=triangle 90] (1) edge[] node [above] {} (2);
+
+\path[->,>=triangle 90] (4) edge[] node [above] {} (1);
+
+\path[->,>=triangle 90] (5) edge[] node [above] {} (8);
+\path[->,>=triangle 90] (8) edge[] node [above] {} (4);
+\path[->,>=triangle 90] (2) edge[] node [above] {} (3);
+\path[->,>=triangle 90] (2) edge[] node [above] {} (4);
+\path[->,>=triangle 90] (3) edge[] node [above] {} (4);
+\path[->,>=triangle 90] (3) edge[] node [above] {} (1);
+
+
+\end{tikzpicture}
+\end{center}
+\caption{Graphe des connaissances}\label{fig:zomb}
+\end{figure}
+\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
+{\it parcours en largeur} et celle de la question~4 s'appelle {\it parcours
+ en profondeur}.
+
+
+\section{Arbres couvrants}
+
+\subsection{Arbres}
+
+
+Un {\bf arbre} est un graphe $G=(V,E)$ tel que~:
+\begin{enumerate}
+\item[(1)] Il n'y a pas de boucle de longueur non nulle dans $G$ (on dit que $G$
+ est acyclique).
+
+\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$.
+\end{enumerate}
+
+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.
+\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
+$(3)$ et $(1)$.
+\end{exo}
+
+\medskip
+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{}.
+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}.
+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}.
+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
+$1$.
+
+\begin{figure}
+\begin{center}
+\begin{tikzpicture}[scale=0.6]
+\node (1) at (0,0) {$1$};
+\node (2) at (-3,-2) {$2$};
+\node (3) at (3,-2) {$3$};
+
+\node (5) at (-2,-4) {$5$};
+\node (4) at (-3,-4) {$4$};
+\node (6) at (3,-4) {$6$};
+
+\node (7) at (1,-6) {$7$};
+\node (8) at (2,-6) {$8$};
+\node (9) at (3,-6) {$9$};
+
+
+\path[->,>=triangle 90] (1) edge[] node [above] {} (2);
+\path[->,>=triangle 90] (1) edge[] node [above] {} (3);
+\path[->,>=triangle 90] (2) edge[] node [above] {} (5);
+\path[->,>=triangle 90] (2) edge[] node [above] {} (4);
+\path[->,>=triangle 90] (3) edge[] node [above] {} (6);
+\path[->,>=triangle 90] (6) edge[] node [above] {} (7);
+\path[->,>=triangle 90] (6) edge[] node [above] {} (8);
+\path[->,>=triangle 90] (6) edge[] node [above] {} (9);
+\end{tikzpicture}
+\end{center}
+\caption{Exemple d'arbre}\label{fig:arbre}
+\end{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?
+\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.
+
+Le parcours Préfixe est l'algorithme récursif suivant. Initialement, le
+parcours est lancé à la racine.
+
+\begin{verbatim}
+Parcours-Prefixe(V,E,x):
+ Traiter(x)
+ Pour chaque fils f de x:
+ Parcours-Prefixe(V,E,f)
+ FinPour
+\end{verbatim}
+
+Si l'on applique {\tt Parcours-Prefixe} en $1$ sur l'arbre de la
+figure~\ref{fig:arbre}, avec pour fonction {\tt Traiter} la fonction qui
+affiche la valeur du sommet on obtient.
+
+$1$ {\tt Parcours-Prefixe(2)} {\tt Parcours-Prefixe(3)} \hspace{2cm} (sommets
+dans l'ordre)
+
+\noindent
+Or {\tt Parcours-Prefixe(2)} retourne
+
+$2$ {\tt Parcours-Prefixe(4)} {\tt Parcours-Prefixe(5)} \hspace{2cm} et
+donc retourne
+
+$2$ $4$ $5$
+
+
+\noindent
+De même {\tt Parcours-Prefixe(3)} retourne
+
+$3$ $6$ $7$ $8$ $9$
+
+\noindent
+Et donc {\tt Parcours-Prefixe(1)} retourne
+
+$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}.
+
+
+\begin{figure}
+\begin{center}
+\begin{tikzpicture}[scale=0.6]
+\node (1) at (0,0) {$1$};
+\node (2) at (3,-2) {$3$};
+\node (3) at (-3,-2) {$2$};
+\node (4) at (4,-4) {$4$};
+\node (5) at (2,-4) {$6$};
+\node (6) at (-3,-4) {$5$};
+\node (7) at (-3,-6) {$7$};
+\node (8) at (-2,-6) {$8$};
+\node (9) at (2,-6) {$9$};
+\node (10) at (3,-6) {$10$};
+
+
+\path[->,>=triangle 90] (1) edge[] node [above] {} (2);
+\path[->,>=triangle 90] (1) edge[] node [above] {} (3);
+\path[->,>=triangle 90] (3) edge[] node [above] {} (5);
+\path[->,>=triangle 90] (2) edge[] node [above] {} (4);
+\path[->,>=triangle 90] (3) edge[] node [above] {} (6);
+\path[->,>=triangle 90] (6) edge[] node [above] {} (7);
+\path[->,>=triangle 90] (6) edge[] node [above] {} (8);
+\path[->,>=triangle 90] (5) edge[] node [above] {} (9);
+\path[->,>=triangle 90] (5) edge[] node [above] {} (10);
+\end{tikzpicture}
+\end{center}
+\caption{Arbre}\label{fig:arbre2}
+\end{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.
+
+\begin{verbatim}
+Parcours-Suffixe(V,E,x):
+ Pour chaque fils f de x:
+ Parcours-Suffixe(V,E,f)
+ FinPour
+ Traiter(x)
+\end{verbatim}
+
+\begin{exo}
+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}
+
+%%%%%%%%%%%%%%%%%%%%%
+\subsection{Arbres couvrants}
+
+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
+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
+ que les conditions
+ $(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}.
+
+\begin{figure}[h]
+\begin{center}
+\begin{tikzpicture}[scale = 0.8]
+\node (0) at (-2,-1) {0};
+
+\node (1) at (0,0) {1};
+\node (2) at (3,0) {2};
+\node (3) at (6,0) {3};
+\node (4) at (9,0) {4};
+\node (5) at (12,0) {5};
+
+\node (6) at (0,-2) {6};
+\node (7) at (3,-2) {7};
+\node (8) at (6,-2) {8};
+\node (9) at (9,-2) {9};
+
+
+
+\path[->,>=triangle 90] (0) edge[] node [swap] {} (1);
+
+\path[->,>=triangle 90] (1) edge[bend left] node [swap] {} (2);
+\path[->,>=triangle 90] (1) edge[] node [swap] {} (6);
+\path[->,>=triangle 90] (1) edge[] node [swap] {} (7);
+\path[->,>=triangle 90] (2) edge[] node [swap] {} (7);
+\path[->,>=triangle 90] (2) edge[] node [swap] {} (6);
+\path[->,>=triangle 90] (2) edge[bend left] node [swap] {} (1);
+
+\path[->,>=triangle 90] (2) edge[loop] node [swap] {} (2);
+
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (7);
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (4);
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (2);
+
+\path[->,>=triangle 90] (4) edge[] node [swap] {} (9);
+\path[->,>=triangle 90] (5) edge[] node [swap] {} (9);
+\path[->,>=triangle 90] (3) edge[out=45,in=135] node [swap] {} (5);
+
+
+
+\path[->,>=triangle 90] (6) edge[out=-20, in =-160] node [swap] {} (9);
+
+
+
+\path[->,>=triangle 90] (8) edge[] node [swap] {} (2);
+\path[->,>=triangle 90] (8) edge[] node [swap] {} (4);
+
+\path[->,>=triangle 90] (9) edge[] node [swap] {} (3);
+
+\end{tikzpicture}
+\end{center}
+\caption{Graphe 1}\label{fig:graphcouvrant}
+\end{figure}
+
+Dans ce graphe, l'arbre de gauche de la figure~\ref{fig:graphcouvrant2}
+vérifie bien $(1)$ et $(2)$ mais
+pas $(3)$. En revanche celui de droite est bien un arbre couvrant.
+
+
+\begin{figure}[h]
+\begin{center}
+\subfigure{
+\begin{tikzpicture}[scale = 0.8]
+\node (0) at (-2,-1) {0};
+
+\node (1) at (0,0) {1};
+\node (2) at (2,0) {2};
+\node (6) at (0,-2) {6};
+
+\path[->,>=triangle 90] (0) edge[] node [swap] {} (1);
+
+\path[->,>=triangle 90] (1) edge[bend left] node [swap] {} (2);
+\path[->,>=triangle 90] (1) edge[] node [swap] {} (6);
+
+\end{tikzpicture}}\hspace{1cm}
+\subfigure{
+
+\begin{tikzpicture}[scale = 0.6]
+\node (0) at (-2,-1) {0};
+
+\node (1) at (0,0) {1};
+\node (2) at (3,0) {2};
+\node (3) at (6,0) {3};
+\node (4) at (9,0) {4};
+\node (5) at (12,0) {5};
+
+\node (6) at (0,-2) {6};
+\node (7) at (3,-2) {7};
+\node (9) at (9,-2) {9};
+
+
+
+\path[->,>=triangle 90] (0) edge[] node [swap] {} (1);
+
+\path[->,>=triangle 90] (1) edge[bend left] node [swap] {} (2);
+\path[->,>=triangle 90] (1) edge[] node [swap] {} (6);
+\path[->,>=triangle 90] (1) edge[] node [swap] {} (7);
+
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (4);
+
+
+\path[->,>=triangle 90] (3) edge[out=45,in=135] node [swap] {} (5);
+\path[->,>=triangle 90] (6) edge[out=-20, in =-160] node [swap] {} (9);
+
+\path[->,>=triangle 90] (9) edge[] node [swap] {} (3);
+
+
+
+\end{tikzpicture}
+}
+\end{center}
+
+\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}
+
+
+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
+ parcours en profondeur}.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\subsection{Parcours en largeur}
+
+
+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~:
+\begin{enumerate}
+\item $x$ est la racine de l'arbre.
+\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
+ 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.
+\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
+$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
+l'arbre $A_2$ de la figure~\ref{fig:parcourslargeur}.
+
+\begin{figure}[h]
+\begin{center}
+\subfigure[$A_1$]{
+\begin{tikzpicture}[scale = 0.6]
+\node (2) at (3,0) {2};
+\node (3) at (6,0) {3};
+\node (4) at (9,0) {4};
+\node (5) at (12,0) {5};
+\node (7) at (3,-2) {7};
+
+
+
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (7);
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (4);
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (2);
+\path[->,>=triangle 90] (3) edge[out=45,in=135] node [swap] {} (5);
+\end{tikzpicture}
+}
+\subfigure[$A_2$]{
+\begin{tikzpicture}[scale = 0.6]
+
+\node (1) at (0,0) {1};
+\node (2) at (3,0) {2};
+\node (3) at (6,0) {3};
+\node (4) at (9,0) {4};
+\node (5) at (12,0) {5};
+
+\node (6) at (0,-2) {6};
+\node (7) at (3,-2) {7};
+
+
+
+\path[->,>=triangle 90] (2) edge[] node [swap] {} (6);
+\path[->,>=triangle 90] (2) edge[bend left] node [swap] {} (1);
+
+
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (7);
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (4);
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (2);
+\path[->,>=triangle 90] (3) edge[out=45,in=135] node [swap] {} (5);
+
+
+
+
+\end{tikzpicture}
+}
+\end{center}
+\caption{Parcours en largeur}\label{fig:parcourslargeur}
+\end{figure}
+
+
+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
+l'arbre de la figure~\ref{fig:parcourslargeurA3}
+
+\begin{figure}[ht]
+\begin{center}
+\begin{tikzpicture}[scale = 0.6]
+
+\node (1) at (0,0) {1};
+\node (2) at (3,0) {2};
+\node (3) at (6,0) {3};
+\node (4) at (9,0) {4};
+\node (5) at (12,0) {5};
+
+\node (6) at (0,-2) {6};
+\node (7) at (3,-2) {7};
+
+\node (9) at (9,-2) {9};
+
+
+
+\path[->,>=triangle 90] (2) edge[] node [swap] {} (6);
+\path[->,>=triangle 90] (2) edge[bend left] node [swap] {} (1);
+
+
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (7);
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (4);
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (2);
+\path[->,>=triangle 90] (3) edge[out=45,in=135] node [swap] {} (5);
+
+\path[->,>=triangle 90] (4) edge[] node [swap] {} (9);
+
+
+
+\end{tikzpicture}
+\end{center}
+\caption{Parcours en largeur~$A_3$}\label{fig:parcourslargeurA3}
+\end{figure}
+
+
+\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$.
+
+\begin{center}
+\begin{tikzpicture}[scale = 0.8]
+\node (0) at (-2,-1) {0};
+
+\node (1) at (0,0) {1};
+\node (2) at (3,0) {2};
+\node (3) at (6,0) {3};
+\node (4) at (9,0) {4};
+\node (5) at (12,0) {5};
+
+\node (6) at (0,-2) {6};
+\node (7) at (3,-2) {7};
+\node (8) at (6,-2) {8};
+\node (9) at (9,-2) {9};
+
+
+
+\path[->,>=triangle 90] (0) edge[] node [swap] {} (1);
+
+\path[->,>=triangle 90] (1) edge[bend left] node [swap] {} (2);
+\path[->,>=triangle 90] (1) edge[] node [swap] {} (6);
+\path[->,>=triangle 90] (1) edge[] node [swap] {} (7);
+\path[->,>=triangle 90] (2) edge[] node [swap] {} (7);
+\path[->,>=triangle 90] (2) edge[] node [swap] {} (6);
+\path[->,>=triangle 90] (2) edge[bend left] node [swap] {} (1);
+
+\path[->,>=triangle 90] (2) edge[loop] node [swap] {} (2);
+
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (7);
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (4);
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (2);
+
+\path[->,>=triangle 90] (4) edge[] node [swap] {} (9);
+\path[->,>=triangle 90] (5) edge[] node [swap] {} (9);
+\path[->,>=triangle 90] (3) edge[out=45,in=135] node [swap] {} (5);
+
+
+
+\path[->,>=triangle 90] (6) edge[out=-20, in =-160] node [swap] {} (9);
+
+
+
+\path[->,>=triangle 90] (8) edge[] node [swap] {} (2);
+\path[->,>=triangle 90] (8) edge[] node [swap] {} (4);
+
+\path[->,>=triangle 90] (9) edge[] node [swap] {} (3);
+
+
+\end{tikzpicture}
+\end{center}
+
+
+\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]
+\begin{center}
+\begin{tikzpicture}[scale = 0.8]
+\node (0) at (-2,-1) {0};
+
+\node (1) at (0,0) {1};
+\node (2) at (3,0) {2};
+\node (3) at (6,0) {3};
+\node (4) at (9,0) {4};
+\node (5) at (12,0) {5};
+
+\node (6) at (0,-2) {6};
+\node (7) at (3,-2) {7};
+\node (8) at (6,-2) {8};
+\node (9) at (9,-2) {9};
+\node (10) at (12,-2) {10};
+
+\node (11) at (15,0) {11};
+\node (12) at (15,-2) {12};
+
+\node (13) at (0,-4) {13};
+\node (14) at (3,-4) {14};
+\node (15) at (6,-4) {15};
+\node (16) at (9,-4) {16};
+\node (17) at (12,-4) {17};
+\node (18) at (15,-4) {18};
+
+
+
+\path[->,>=triangle 90] (0) edge[] node [swap] {} (1);
+\path[->,>=triangle 90] (0) edge[] node [swap] {} (2);
+\path[->,>=triangle 90] (0) edge[out=60, in =120] node [swap] {} (3);
+
+\path[->,>=triangle 90] (1) edge[] node [swap] {} (2);
+\path[->,>=triangle 90] (1) edge[] node [swap] {} (6);
+\path[->,>=triangle 90] (1) edge[] node [swap] {} (7);
+\path[->,>=triangle 90] (2) edge[] node [swap] {} (7);
+\path[->,>=triangle 90] (2) edge[] node [swap] {} (6);
+
+\path[->,>=triangle 90] (2) edge[loop] node [swap] {} (2);
+
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (7);
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (4);
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (2);
+
+\path[->,>=triangle 90] (4) edge[] node [swap] {} (9);
+\path[->,>=triangle 90] (5) edge[] node [swap] {} (9);
+\path[->,>=triangle 90] (5) edge[] node [swap] {} (11);
+\path[->,>=triangle 90] (5) edge[] node [swap] {} (12);
+\path[->,>=triangle 90] (3) edge[out=45,in=135] node [swap] {} (5);
+
+
+
+\path[->,>=triangle 90] (6) edge[] node [swap] {} (14);
+\path[->,>=triangle 90] (6) edge[out=-20, in =-160] node [swap] {} (9);
+
+\path[->,>=triangle 90] (7) edge[] node [swap] {} (13);
+\path[->,>=triangle 90] (7) edge[] node [swap] {} (15);
+
+
+\path[->,>=triangle 90] (8) edge[out=-20, in =-160] node [swap] {} (10);
+
+\path[->,>=triangle 90] (8) edge[] node [swap] {} (2);
+\path[->,>=triangle 90] (8) edge[] node [swap] {} (4);
+\path[->,>=triangle 90] (8) edge[] node [swap] {} (14);
+\path[->,>=triangle 90] (8) edge[] node [swap] {} (15);
+
+\path[->,>=triangle 90] (9) edge[] node [swap] {} (3);
+\path[->,>=triangle 90] (9) edge[] node [swap] {} (8);
+\path[->,>=triangle 90] (9) edge[] node [swap] {} (16);
+
+\path[->,>=triangle 90] (10) edge[] node [swap] {} (4);
+\path[->,>=triangle 90] (10) edge[] node [swap] {} (5);
+\path[->,>=triangle 90] (10) edge[] node [swap] {} (17);
+
+\path[->,>=triangle 90] (12) edge[] node [swap] {} (10);
+
+\path[->,>=triangle 90] (13) edge[] node [swap] {} (0);
+\path[->,>=triangle 90] (16) edge[] node [swap] {} (17);
+\path[->,>=triangle 90] (17) edge[] node [swap] {} (18);
+\path[->,>=triangle 90] (18) edge[out=-160, in =-20] node [swap] {} (16);
+
+\end{tikzpicture}
+\end{center}
+\caption{Rappel d'un graphe du chapitre 1}\label{fig:exo}
+\end{figure}
+\end{enumerate}
+\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}
+Les
+{\em composantes fortement connexes} d'un graphe sont des sous-ensembles de
+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.
+\begin{enumerate}
+\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
+ 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?
+% \end{exo}
+
+%%%%%%%%%%%%%%%
+\subsection{Parcours en profondeur}
+
+
+\begin{figure}
+\begin{center}
+\begin{tikzpicture}[scale = 0.8]
+
+\node (1) at (0,0) {1};
+\node (2) at (3,0) {2};
+\node (3) at (6,0) {3};
+\node (6) at (0,-2) {6};
+\node (9) at (9,-2) {9};
+
+\path[->,>=triangle 90] (1) edge[] node [swap] {} (6);
+\path[->,>=triangle 90] (2) edge[bend left] node [swap] {} (1);
+
+
+\path[->,>=triangle 90] (3) edge[] node [swap] {} (2);
+
+
+
+\path[->,>=triangle 90] (6) edge[out=-20, in =-160] node [swap] {} (9);
+
+\end{tikzpicture}
+\end{center}
+\caption{Parcours en profondeur (1)}\label{fig:prof1}
+\end{figure}
+
+
+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~:
+\begin{enumerate}
+\item $x$ est la racine de l'arbre.
+\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.
+\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$, à
+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$
+sur le graphe de la figure~\ref{fig:exo}.
+
+
+% \begin{tikzpicture}[scale = 0.8]
+% \node (0) at (-2,-1) {0};
+
+% \node (1) at (0,0) {1};
+% \node (2) at (3,0) {2};
+% \node (3) at (6,0) {3};
+% \node (4) at (9,0) {4};
+% \node (5) at (12,0) {5};
+
+% \node (6) at (0,-2) {6};
+% \node (7) at (3,-2) {7};
+% \node (8) at (6,-2) {8};
+% \node (9) at (9,-2) {9};
+% \node (10) at (12,-2) {10};
+
+% \node (11) at (15,0) {11};
+% \node (12) at (15,-2) {12};
+
+% \node (13) at (0,-4) {13};
+% \node (14) at (3,-4) {14};
+% \node (15) at (6,-4) {15};
+% \node (16) at (9,-4) {16};
+% \node (17) at (12,-4) {17};
+% \node (18) at (15,-4) {18};
+
+
+
+% \path[->,>=triangle 90] (0) edge[] node [swap] {} (1);
+% \path[->,>=triangle 90] (0) edge[] node [swap] {} (2);
+% \path[->,>=triangle 90] (0) edge[out=60, in =120] node [swap] {} (3);
+
+% \path[->,>=triangle 90] (1) edge[] node [swap] {} (2);
+% \path[->,>=triangle 90] (1) edge[] node [swap] {} (6);
+% \path[->,>=triangle 90] (1) edge[] node [swap] {} (7);
+% \path[->,>=triangle 90] (2) edge[] node [swap] {} (7);
+% \path[->,>=triangle 90] (2) edge[] node [swap] {} (6);
+
+% \path[->,>=triangle 90] (2) edge[loop] node [swap] {} (2);
+
+% \path[->,>=triangle 90] (3) edge[] node [swap] {} (7);
+% \path[->,>=triangle 90] (3) edge[] node [swap] {} (4);
+% \path[->,>=triangle 90] (3) edge[] node [swap] {} (2);
+
+% \path[->,>=triangle 90] (4) edge[] node [swap] {} (9);
+% \path[->,>=triangle 90] (5) edge[] node [swap] {} (9);
+% \path[->,>=triangle 90] (5) edge[] node [swap] {} (11);
+% \path[->,>=triangle 90] (5) edge[] node [swap] {} (12);
+% \path[->,>=triangle 90] (3) edge[out=45,in=135] node [swap] {} (5);
+
+
+
+% \path[->,>=triangle 90] (6) edge[] node [swap] {} (14);
+% \path[->,>=triangle 90] (6) edge[out=-20, in =-160] node [swap] {} (9);
+
+% \path[->,>=triangle 90] (7) edge[] node [swap] {} (13);
+% \path[->,>=triangle 90] (7) edge[] node [swap] {} (15);
+
+
+% \path[->,>=triangle 90] (8) edge[out=-20, in =-160] node [swap] {} (10);
+
+% \path[->,>=triangle 90] (8) edge[] node [swap] {} (2);
+% \path[->,>=triangle 90] (8) edge[] node [swap] {} (4);
+% \path[->,>=triangle 90] (8) edge[] node [swap] {} (14);
+% \path[->,>=triangle 90] (8) edge[] node [swap] {} (15);
+
+% \path[->,>=triangle 90] (9) edge[] node [swap] {} (3);
+% \path[->,>=triangle 90] (9) edge[] node [swap] {} (8);
+% \path[->,>=triangle 90] (9) edge[] node [swap] {} (16);
+
+% \path[->,>=triangle 90] (10) edge[] node [swap] {} (4);
+% \path[->,>=triangle 90] (10) edge[] node [swap] {} (5);
+% \path[->,>=triangle 90] (10) edge[] node [swap] {} (17);
+
+% \path[->,>=triangle 90] (12) edge[] node [swap] {} (10);
+
+% \path[->,>=triangle 90] (13) edge[] node [swap] {} (0);
+% \path[->,>=triangle 90] (16) edge[] node [swap] {} (17);
+% \path[->,>=triangle 90] (17) edge[] node [swap] {} (18);
+% \path[->,>=triangle 90] (18) edge[out=-160, in =-20] node [swap] {} (16);
+
+% \end{tikzpicture}
+
+\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}
+
+\end{document}
