From: couchot Date: Thu, 6 Feb 2014 12:48:32 +0000 (+0100) Subject: ajout fichier pch X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-maths-dis.git/commitdiff_plain/7e16643d8ba519bcc6512c70661b4ffa8ca521a0 ajout fichier pch --- diff --git a/graphes/S2MD.tex b/graphes/S2MD.tex new file mode 100644 index 0000000..a86b2b9 --- /dev/null +++ b/graphes/S2MD.tex @@ -0,0 +1,1773 @@ +\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} diff --git a/main13.log b/main13.log index 95ac4d9..7d9a72e 100644 --- a/main13.log +++ b/main13.log @@ -1,4 +1,4 @@ -This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013/Debian) (format=pdflatex 2013.11.13) 15 NOV 2013 08:37 +This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013/Debian) (format=pdflatex 2013.11.13) 24 JAN 2014 11:19 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -1374,11 +1374,11 @@ Package rerunfilecheck Info: File `main13.out' has not changed. Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 336. ) Here is how much of TeX's memory you used: - 12395 strings out of 495002 - 167172 string characters out of 6180261 + 12398 strings out of 495002 + 167203 string characters out of 6180261 283229 words of memory out of 5000000 - 14738 multiletter control sequences out of 15000+600000 - 109186 words of font info for 111 fonts, out of 8000000 for 9000 + 14740 multiletter control sequences out of 15000+600000 + 109807 words of font info for 113 fonts, out of 8000000 for 9000 14 hyphenation exceptions out of 8191 30i,13n,32p,479b,676s stack positions out of 5000i,500n,10000p,200000b,80000s {/usr/share/texlive/texmf-dist/fonts/enc/dvips/base/8r.enc}{/usr/share/texmf/ @@ -1401,7 +1401,7 @@ texmf-dist/fonts/type1/urw/times/utmbi8a.pfb> -Output written on main13.pdf (43 pages, 369126 bytes). +Output written on main13.pdf (43 pages, 370852 bytes). PDF statistics: 1150 PDF objects out of 1200 (max. 8388607) 1073 compressed objects within 11 object streams diff --git a/main13.pdf b/main13.pdf index cfe3e89..401ddcb 100644 Binary files a/main13.pdf and b/main13.pdf differ