t

[cours-maths-dis.git] / graphes / S2MD.tex

\documentclass[]{report}
\usepackage[a4paper]{geometry}
\geometry{hmargin=1.5cm, vmargin=1.5cm }
\usepackage[utf8]{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}{Définition}
\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}