From: couchot Date: Tue, 25 Mar 2014 14:50:25 +0000 (+0100) Subject: t X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-maths-dis.git/commitdiff_plain t --- diff --git a/ensembles/IntroAuxEnsembles13.tex b/ensembles/IntroAuxEnsembles13.tex index 7439ae9..bf41543 100755 --- a/ensembles/IntroAuxEnsembles13.tex +++ b/ensembles/IntroAuxEnsembles13.tex @@ -1,4 +1,4 @@ -\section{Rappels de théorie des ensembles} +\section{Des Définitions} \subsection{Notion première d'ensemble} @@ -44,13 +44,13 @@ On note $\N_n$ l'ensemble des entiers inférieurs ou égaux à $n$. L'ensemble vide ne correspond pas à rien ; c'est en fait un ensemble qui ne contient rien, mais en tant qu'ensemble il n'est pas rien : un sac vide est vide, mais le sac en lui même existe. -\paragraph{Dernière règle de fonctionnement des ensembles.} \textcolor{red}{Un ensemble ne peut pas s'appartenir à lui-même}. +\paragraph{Dernière règle de fonctionnement des ensembles.}Un ensemble ne peut pas s'appartenir à lui-même. \subsection{Sous-ensembles, ensemble des parties} -Les sous-ensembles sont définis par la relation d'inclusion\index{inclusion}... +Les sous-ensembles sont définis par la relation d'inclusion\index{inclusion}. \begin{Def} $A$ est un sous-ensemble de $B$ ($A \subset B$)\fg{} si et seulement si tout élément de $A$ appartient à $B$. On dit aussi que $A$ est une partie de $B$. @@ -81,7 +81,8 @@ Soit $A$ un ensemble. L'ensemble des parties de $A$, noté $\mathcal{P}(A)$, est \begin{Th} -Pour tout ensemble $A$, on a $\varnothing, A \in \mathcal{P}(A)$. +Pour tout ensemble $A$, on a $\varnothing\in \mathcal{P}(A)$ et +$A \in \mathcal{P}(A)$. \end{Th} @@ -134,15 +135,15 @@ Deux ensembles sont \emph{égaux} si et seulement si ils ont les mêmes élémen -$A \subset B$ et $B \subset A \Longleftrightarrow A = B$. +$ A = B\Longleftrightarrow A \subset B \land B \subset A$. \begin{Exo} Dans chacun des cas suivants, déterminer si les ensembles sont égaux : \begin{enumerate} \item $A = \{ x \in \R | x > 0 \}$ et $ B = \{x \in \R | x \geqslant |x| \}$; \item $A = \{ x \in \R | x > 0 \}$ et $ B = \{x \in \R | x \leqslant |x| \}$; -\item $A = \Z$ et $B = \{ x \in \Z | x(x-1) \textrm{ pair } \}$; -on pourra réfléchir sur la parité de $x(x-1)$. +\item $A = \Z$ et $B = \{ x \in \Z | x^2-x \textrm{ pair } \}$; +on pourra réfléchir sur la parité de $x^2-x$. \end{enumerate} \end{Exo} @@ -183,12 +184,15 @@ La réunion de deux ensembles possède certaines propriétés : \end{Exo} \begin{Exo} -Faire la réunion des ensembles $A$ et $B$, quand $A = \{x \in \N | x \textrm{ impair } \}$, et $B = \{ x \in \N | x \textrm{ pas divisible par 3 } \}$. +Construire la réunion des ensembles $A$ et $B$ +définis par +$$A = \{x \in \N | x \textrm{ est impair } \} \textrm{ et } +B = \{ x \in \N | x \textrm{ n'est pas divisible par 3 } \}.$$ \end{Exo} \begin{Th}[Distributivités de $\cup$ et $\cap$] -On a les distributivités : +On a les distributivités suivantes: \begin{itemize} \item de $\cup$ sur $\cap$ : $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ \item de $\cap$ sur $\cup$ : $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ @@ -221,12 +225,11 @@ La complémentation a plusieurs propriétés remarquables : \begin{Exo} Pour deux ensembles $A$ et $B$ inclus dans $E$, on appelle différence symétrique, note $A\Delta B$, -l'ensemble défini par -$A \Delta B = (A \cup B) \setminus (A \cap B)$ -c'est-à-dire que $A \Delta B$ est constitué des éléments qui appartiennent soit à $A$, soit à $B$, mais pas aux deux. +l'ensemble constitué des éléments de $E$ qui appartiennent soit à $A$, +soit à $B$, mais pas aux deux. \begin{enumerate} -\item Montrez que $A\Delta B = [A\inter(E\moins B)]\union[(E\moins A) \inter B]$. -\item Simplifier les expressions $A \Delta A$, $A \Delta (E\moins A)$, $A \Delta E$ et $E\moins (A\triangle B)$. +\item Montrez que $A\Delta B = (A\inter \overline{B})\union(\overline{A} \inter B)$. +\item Simplifier les expressions $A \Delta A$, $A \Delta \overline{A}$, $A \Delta E$ et $\overline{A\triangle B}$. \item Montrer que, si $A\triangle B=C$, alors $A\triangle C=B$ et $B\triangle C=A$. \item Montrer que si $A \Delta B = A \Delta C$ alors $B = C$. \end{enumerate} diff --git a/graphes/S2MD.tex b/graphes/S2MD.tex index 0db9d34..5c52021 100644 --- a/graphes/S2MD.tex +++ b/graphes/S2MD.tex @@ -1,12 +1,10 @@ \documentclass[]{report} \usepackage[a4paper]{geometry} \geometry{hmargin=1.5cm, vmargin=1.5cm } -\usepackage[latin1]{inputenc} +\usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage[french]{babel} \usepackage{amsmath,amssymb,latexsym,eufrak,euscript,array} - - \usepackage{pgf} \usepackage{tikz} \usepackage{pdfpages} @@ -19,8 +17,8 @@ -\newtheorem{definition}{Definition} -\newtheorem{theoreme}[definition]{Théorème} +\newtheorem{definition}{Définition} +\newtheorem{theoreme}[definition]{Théorème} \newtheorem{proposition}[definition]{Proposition} \newtheorem{exemple}[definition]{Exemple} @@ -34,8 +32,8 @@ \def \A {\mathcal{A}} \def \B {\mathcal{B}} -\title{Cours Mathématiques Discrètes - \\IUT Belfort Montbéliard} +\title{Cours Mathématiques Discrètes + \\IUT Belfort Montbéliard} \author{{\sc Pierre-Cyrille HEAM}} @@ -50,30 +48,30 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\chapter{Graphes finis orientés} +\chapter{Graphes finis orientés} %%%%%%%%%%%%%%%% -\section{Premières définitions} +\section{Premières définitions} -Un {\bf graphe fini orienté} est un couple $(V,E)$ où +Un {\bf graphe fini orienté} est un couple $(V,E)$ où \begin{itemize} -\item $V$ est un ensemble fini dont les éléments sont appelés {\bf sommets} - ou {\bf noeuds} ou {\bf états}. -\item $E\subseteq V\times V$ est un ensemble de couples d'éléments de $V$, - appelés {\bf arêtes} ou {\bf transitions}. +\item $V$ est un ensemble fini dont les éléments sont appelés {\bf sommets} + ou {\bf noeuds} ou {\bf états}. +\item $E\subseteq V\times V$ est un ensemble de couples d'éléments de $V$, + appelés {\bf arêtes} ou {\bf transitions}. \end{itemize} Par exemple $\left(\{1,2,3\},\{(1,2),(2,2),(3,1)\}\right)$ est un graphe -fini orienté. Le choix des lettres $V$ et $E$ viennent de l'anglais pour +fini orienté. Le choix des lettres $V$ et $E$ viennent de l'anglais pour {\it vertice} et {\it edge}. On rappelle que dans un ensemble (entre $\{\}$) -les éléments ne sont pas ordonnés et n'apparaissent qu'au plus une fois. En -revanche dans un couple (deux éléments entre parenthèse), les éléments sont -ordonnés. Le couple $(1,2)$ est différent du couple $(2,1)$. +les éléments ne sont pas ordonnés et n'apparaissent qu'au plus une fois. En +revanche dans un couple (deux éléments entre parenthèse), les éléments sont +ordonnés. Le couple $(1,2)$ est différent du couple $(2,1)$. \begin{exo} -Les couples $(V,E)$ suivants sont-ils des graphes finis orienté~? +Les couples $(V,E)$ suivants sont-ils des graphes finis orienté~? \begin{enumerate} \item $V=\{1,2,3\}$ et $E=\{(1,3)\}$~? \item $V=\{1,2,3\}$ et $E=\{(1,6),(2,4)\}$~? @@ -83,20 +81,20 @@ Les couples $(V,E)$ suivants sont-ils des graphes finis orient \end{enumerate} \end{exo} -{\bf Sauf mention contraire, tous les graphes étudiés dans ce polycopié - seront des graphes finis orientés, que nous appellerons simplement {\it +{\bf Sauf mention contraire, tous les graphes étudiés dans ce polycopié + seront des graphes finis orientés, que nous appellerons simplement {\it graphes} par la suite.} -Un graphe se représente souvent par un dessin où les sommets sont des points -(parfois entourés d'un cercle) et les arêtes des flèches~: si $(x,y)$ est -une arête, on dessine une flèche entre $x$ et $y$. Par exemple le graphe +Un graphe se représente souvent par un dessin où les sommets sont des points +(parfois entourés d'un cercle) et les arêtes des flèches~: si $(x,y)$ est +une arête, on dessine une flèche entre $x$ et $y$. Par exemple le graphe $$(\{1,2,3,4\},\{(1,1),(1,2),(3,1),(2,4),(3,4)\})$$ peut se dessiner comme sur la -figure~\ref{fig:g1}. Comme on peut le voir, il n'y a pas unicité de la façon +figure~\ref{fig:g1}. Comme on peut le voir, il n'y a pas unicité de la façon de dessiner un graphe. \begin{figure}[h] \begin{center} -\subfigure[première possibilité]{ +\subfigure[première possibilité]{ \begin{tikzpicture} \node (1) at (0,0) {$1$}; \node (2) at (4,0) {$2$}; @@ -109,7 +107,7 @@ de dessiner un graphe. \path[->,>=triangle 90] (2) edge[] node [above] {} (4); \end{tikzpicture} }\hspace*{3cm} -\subfigure[deuxième possibilité]{ +\subfigure[deuxième possibilité]{ \begin{tikzpicture} \node (1) at (0,0) {$1$}; @@ -124,7 +122,7 @@ de dessiner un graphe. \end{tikzpicture} } \end{center} -\caption{Représentation d'un graphe}\label{fig:g1} +\caption{Représentation d'un graphe}\label{fig:g1} \end{figure} @@ -151,7 +149,7 @@ Donner sous forme ensembliste ($V$ et $E$) le graphe suivant~: \end{tikzpicture} \end{center} -Le dessin ci-dessous représente-t-il un graphe~? Si oui le donner +Le dessin ci-dessous représente-t-il un graphe~? Si oui le donner explicitement, sinon dire pourquoi. \begin{center} @@ -269,24 +267,24 @@ sont les voisins de $3$~? de $7$~? Quels sommets ont $9$ pour voisin~? \begin{exo} -On considère la fonction $f$ de $\{0,\ldots,7\}$ dans $\{0,\ldots,7\}$ qui à -$x$ associe son reste modulo $3$. Dessiner le graphe où $V=\{0,\ldots,7\}$ et -$(x,y)\in E$ si et seulement si $y=f(x)$. Mêmes question avec $(x,y)\in E$ -ssi $x^2=y \mod 5$ (c'est-à-dire si $x^2-y$ est un multiple de $5$). Même question avec $(x,y)\in E$ ssi $xy=1 \mod 6$. +On considère la fonction $f$ de $\{0,\ldots,7\}$ dans $\{0,\ldots,7\}$ qui à +$x$ associe son reste modulo $3$. Dessiner le graphe où $V=\{0,\ldots,7\}$ et +$(x,y)\in E$ si et seulement si $y=f(x)$. Mêmes question avec $(x,y)\in E$ +ssi $x^2=y \mod 5$ (c'est-à-dire si $x^2-y$ est un multiple de $5$). Même question avec $(x,y)\in E$ ssi $xy=1 \mod 6$. \end{exo} \begin{exo} -On considère $V=\{maison, voiture, poisson, porte, cartable, grue\}$ et +On considère $V=\{maison, voiture, poisson, porte, cartable, grue\}$ et $(x,y)\in E$ si et seulement $x$ est avant $y$ dans l'ordre du dictionnaire. Dessiner le graphe $(V,E)$. -Même question mais cette fois ci $(x,y)\in E$ si et seulement $x$ et +Même question mais cette fois ci $(x,y)\in E$ si et seulement $x$ et $y$ ont au moins deux lettres en commun. \end{exo} \begin{exo} Soit $G=(V,E)$ un graphe. Comment voit-on sur un dessin de $G$ que la relation $E$ est une application bijective~? que la relation $E$ est transitive~? -réflexive~? +réflexive~? \end{exo} @@ -296,24 +294,24 @@ r Soit $G=(V,E)$ un graphe. Un {\bf chemin} est une suite finie -$(x_1,x_2),(x_2,x_3),\ldots,(x_{n},x_{n+1})$ d'arêtes consécutives. L'entier -$n$ est appelé {\bf taille} ou {\bf longueur} du chemin. Le sommet $x_1$ est l'{\bf origine} +$(x_1,x_2),(x_2,x_3),\ldots,(x_{n},x_{n+1})$ d'arêtes consécutives. L'entier +$n$ est appelé {\bf taille} ou {\bf longueur} du chemin. Le sommet $x_1$ est l'{\bf origine} du chemin et $x_n$ sa {\bf destination}. On dit aussi que ce chemin part de $x_1$ pour arriver en $x_n$. Dans le graphe de la figure~\ref{fig:grapheexo1}, $(0,1),(1,2),(2,6)$ est un chemin partant de $0$, arrivant en $6$ et de longueur $3$. Par convention, -de tout point part un chemin vers lui même de longueur $0$ (qui n'utilise -aucune arête). +de tout point part un chemin vers lui même de longueur $0$ (qui n'utilise +aucune arête). Une {\bf boucle} est un chemin dont le sommet d'origine est aussi le sommet -d'arrivée. Une boucle qui ne passe pas deux fois par le même sommet (sauf à -l'origine et à la destination) est appelé un {\bf circuit}. Dans le graphe +d'arrivée. Une boucle qui ne passe pas deux fois par le même sommet (sauf à +l'origine et à la destination) est appelé un {\bf circuit}. Dans le graphe de la figure~\ref{fig:grapheexo1}, $(5,12),(12,10),(10,5)$ est un circuit. Le chemin $$(0,1),(1,7)(7,13)(13,0),(0,3),(3,7),(7,13),(13,0)$$ est une boucle mais n'est pas un circuit. -Un chemin qui ne passe jamais deux fois par le même sommet est dit {\bf sans +Un chemin qui ne passe jamais deux fois par le même sommet est dit {\bf sans boucle}. @@ -322,20 +320,20 @@ Dans le graphe de la figure~\ref{fig:grapheexo1} donner \begin{enumerate} \item Un circuit de taille $1$, \item Une boucle de longueur $9$ passant par $4$, -\item Un chemin sans boucle de $0$ à $18$, +\item Un chemin sans boucle de $0$ à $18$, \item Un chemin sans boucle de taille au moins $10$. \end{enumerate} \end{exo} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%ùù -\section{Graphe et modélisation} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%ùù +\section{Graphe et modélisation} -L'objectif de ce chapitre est de voir comment passer d'un problème concret à -un problème de graphe. +L'objectif de ce chapitre est de voir comment passer d'un problème concret à +un problème de graphe. \begin{exo} -On considère le plan ci-dessous d'un musée. La porte d'entrée est en bas à +On considère le plan ci-dessous d'un musée. La porte d'entrée est en bas à gauche. \bigskip @@ -366,24 +364,24 @@ gauche. \end{tikzpicture} \begin{enumerate} -\item Représenter sous forme de graphe ce musée, en mettant un sommet par +\item Représenter sous forme de graphe ce musée, en mettant un sommet par salle. \item On suppose qu'un gardien peut surveiller la salle dans laquelle il se trouve ainsi que les salles voisines. Combien faut-il de gardiens au minimum~? -Formuler ce problème, d'une manière générale, dans le vocabulaire des +Formuler ce problème, d'une manière générale, dans le vocabulaire des graphes. -\item Un groupe de visiteurs souhaite admirer toutes les salles du musée. -Peut-il le faire sans jamais passer deux fois par la même salle (on ne +\item Un groupe de visiteurs souhaite admirer toutes les salles du musée. +Peut-il le faire sans jamais passer deux fois par la même salle (on ne compte pas le chemin de retour; le groupe peut partir de n'importe quelle -salle aussi)~? Proposer une formulation générale de ce -problème en utilisant le vocabulaire des graphes. +salle aussi)~? Proposer une formulation générale de ce +problème en utilisant le vocabulaire des graphes. -\item Le soir, le conservateur souhaite avant de fermer le musée passer dans +\item Le soir, le conservateur souhaite avant de fermer le musée passer dans toutes les salles puis ressortir, tout en minimisant le trajet (il part de - l'entrée et ressort par l'entrée/sortie). Quel - chemin doit-il prendre~? Formuler ce problème de façon général en + l'entrée et ressort par l'entrée/sortie). Quel + chemin doit-il prendre~? Formuler ce problème de façon général en utilisant le vocabulaire des graphes. \end{enumerate} @@ -393,77 +391,77 @@ probl %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{exo} -On considère un ensemble fini $V$ de joueurs de tennis, et le graphe orienté -$(V,E)$ tel que $(x,y)\in E$ si et seulement si $x$ a déjà gagné un match -contre $y$. Donner des formulations dans le vocabulaire de la théorie des -graphes des propriétés suivantes. +On considère un ensemble fini $V$ de joueurs de tennis, et le graphe orienté +$(V,E)$ tel que $(x,y)\in E$ si et seulement si $x$ a déjà gagné un match +contre $y$. Donner des formulations dans le vocabulaire de la théorie des +graphes des propriétés suivantes. \begin{enumerate} \item Il y a un joueur qui n'a jamais perdu. -\item Il y a un joueur qui n'a jamais gagné. -\item Un joueur ne joue jamais contre lui-même. -\item Tous les joueurs ont déjà joué au moins un match conte un autre +\item Il y a un joueur qui n'a jamais gagné. +\item Un joueur ne joue jamais contre lui-même. +\item Tous les joueurs ont déjà joué au moins un match conte un autre joueur. -\item Il y a un joueur qui a déjà joué contre tout le monde. -\item Il y a un joueur qui a déjà gagné contre tout le monde. -\item Il y a un joueur qui a joué contre tout le monde et perdu tous +\item Il y a un joueur qui a déjà joué contre tout le monde. +\item Il y a un joueur qui a déjà gagné contre tout le monde. +\item Il y a un joueur qui a joué contre tout le monde et perdu tous ses matchs. \end{enumerate} \end{exo} \begin{exo} -On considère un graphe représentant la carte d'une ville~: chaque n\oe{}ud est -un croisement, chaque arête un tronçon de rue, codant le sens de -circulation. On considère de plus que les neouds sont coloriés, en rouge +On considère un graphe représentant la carte d'une ville~: chaque n\oe{}ud est +un croisement, chaque arête un tronçon de rue, codant le sens de +circulation. On considère de plus que les neouds sont coloriés, en rouge (s'il y a un feu de signalisation au croisement) ou en bleu (s'il n'y a pas de feu). -Exprimer, dans le vocabulaire de la théorie des graphes les -propriétés suivantes. +Exprimer, dans le vocabulaire de la théorie des graphes les +propriétés suivantes. \begin{enumerate} \item Il n'y a pas de sens unique. \item Il n'y a pas d'impasse. -\item De n'importe où, je peux aller partout. -\item De n'importe où, je peux aller partout en passant par au plus trois +\item De n'importe où, je peux aller partout. +\item De n'importe où, je peux aller partout en passant par au plus trois feux de signalisation. -\item Deux croisements consécutifs ne peuvent avoir tout deux des feux. -\item Il n'y a jamais plus de deux rues qui se croisent à la fois. +\item Deux croisements consécutifs ne peuvent avoir tout deux des feux. +\item Il n'y a jamais plus de deux rues qui se croisent à la fois. \item Il n'y a ni pont, ni tunnel. \end{enumerate} \end{exo} \begin{exo} -On considère le graphe $G$ dont les sommets sont les configurations possible -d'un rubics cube, et il y a une arête entre deux configurations si l'on peut -passer de l'une à l'autre en jouant un coup (c'est-à-dire une rotation d'un -quart de tour d'un coté). Exprimer avec le vocabulaire de la théorie des -graphes les propriétés suivantes (on ne cherche pas à savoir si elles sont +On considère le graphe $G$ dont les sommets sont les configurations possible +d'un rubics cube, et il y a une arête entre deux configurations si l'on peut +passer de l'une à l'autre en jouant un coup (c'est-à-dire une rotation d'un +quart de tour d'un coté). Exprimer avec le vocabulaire de la théorie des +graphes les propriétés suivantes (on ne cherche pas à savoir si elles sont vraies ou fausse)~: \begin{itemize} \item Il y a toujours une solution. \item A partir de certaines configurations, il n'y a pas de solution. -\item De toute position, si je modifie le cube, je peux revenir à cette +\item De toute position, si je modifie le cube, je peux revenir à cette position. -\item Il existe une position dans laquelle je peux résoudre le rubics cube, +\item Il existe une position dans laquelle je peux résoudre le rubics cube, mais pas en moins de 30 coups. -\item Si dans une position je peux résoudre le rubics cube, alors je peux le - résoudre en moins de 30 coups. +\item Si dans une position je peux résoudre le rubics cube, alors je peux le + résoudre en moins de 30 coups. \end{itemize} \end{exo} \begin{exo} -On considère un ensemble de $n$ enfants portant chacun un dossard différent, -numéroté de $1$ à $n$, et jouant à cache-cache. On considère le graphe dont -les sommets sont les entiers de $1$ à $n$ et il y a une arête entre $i$ et +On considère un ensemble de $n$ enfants portant chacun un dossard différent, +numéroté de $1$ à $n$, et jouant à cache-cache. On considère le graphe dont +les sommets sont les entiers de $1$ à $n$ et il y a une arête entre $i$ et $j$ si l'enfant avec le dossard $i$ peut voir l'enfant avec le dossard $j$. -Exprimer dans le vocabulaire de la théorie des graphes les propriétés +Exprimer dans le vocabulaire de la théorie des graphes les propriétés suivantes~: \begin{enumerate} -\item Il y a un enfant bien caché qu'aucun autre ne peut voir. +\item Il y a un enfant bien caché qu'aucun autre ne peut voir. \item Il y a un enfant qui ne voit personne. -\item Un enfant se voit toujours lui-même. +\item Un enfant se voit toujours lui-même. \item Il y a deux enfants qui se voient l'un l'autre. \item Tout enfant voit au moins un autre enfant. \end{enumerate} @@ -471,29 +469,29 @@ suivantes~: \begin{exo} -Un homme se trouve au bord d'une rivière avec un choux, une chèvre et loup. -Il possède une barque et veut traverser la rivière. Cependant, il ne peut -mettre en même temps, en plus de lui, dans la barque qu'un des trois. Et, +Un homme se trouve au bord d'une rivière avec un choux, une chèvre et loup. +Il possède une barque et veut traverser la rivière. Cependant, il ne peut +mettre en même temps, en plus de lui, dans la barque qu'un des trois. Et, malheureusement aussi, il ne peut laisser sur une rive seul le loup avec la -chèvre, ni la chèvre avec le choux. +chèvre, ni la chèvre avec le choux. -Modéliser le problème avec un graphe et proposer une solution. +Modéliser le problème avec un graphe et proposer une solution. \end{exo} \begin{exo} -On considère un site Web statique, installé sur un serveur. On se pose les -questions suivantes, liées à l'ergonomie du site~: +On considère un site Web statique, installé sur un serveur. On se pose les +questions suivantes, liées à l'ergonomie du site~: \begin{enumerate} -\item Puis-je à l'aide de la souris uniquement accéder à toutes les pages du - site à partir de la page d'accueil~? -\item Puis-je toujours en un clic retourner à la page d'accueil~? -\item Puis-je, à partir de n'importe quelle page, accéder à n'importe quelle +\item Puis-je à l'aide de la souris uniquement accéder à toutes les pages du + site à partir de la page d'accueil~? +\item Puis-je toujours en un clic retourner à la page d'accueil~? +\item Puis-je, à partir de n'importe quelle page, accéder à n'importe quelle autre page en moins de 3 clics~? \end{enumerate} -Proposer une modélisation de cette situation par un graphe, puis décrire des -algorithmes pour répondre aux questions posées. +Proposer une modélisation de cette situation par un graphe, puis décrire des +algorithmes pour répondre aux questions posées. \end{exo} @@ -524,20 +522,20 @@ algorithmes pour r \draw (1.5-0.1,3.25) [fill=white]rectangle +(0.2,.5); \draw (1.5-0.1,2.25) [fill=white]rectangle +(0.2,.5); \end{tikzpicture} -\caption{Plan du musée 1}\label{m1} +\caption{Plan du musée 1}\label{m1} \end{figure} \begin{exo} -On considère le musée décrit dans la figure~\ref{m1}. Le directeur +On considère le musée décrit dans la figure~\ref{m1}. Le directeur souhaite, pour une exposition exceptionnelle, placer un gardien dans chaque salle. Il recrute pour cela des gardiens espagnols (qui ne parlent que l'espagnol) et des gardiens italiens (qui ne parlent qu'italien). Afin qu'il -ne discutent pas entre eux, il ne veut pas que deux gardiens de la même -nationalité soient dans des salles voisines. Est-ce possible~? +ne discutent pas entre eux, il ne veut pas que deux gardiens de la même +nationalité soient dans des salles voisines. Est-ce possible~? \bigskip -Même question avec le musée de la figure~\ref{m2}. +Même question avec le musée de la figure~\ref{m2}. \begin{figure}[h] \begin{tikzpicture} @@ -564,33 +562,33 @@ M %\draw (1.5-0.1,3.25) [fill=white]rectangle +(0.2,.5); \draw (1.5-0.1,2.25) [fill=white]rectangle +(0.2,.5); \end{tikzpicture} -\caption{Plan du musée 2}\label{m2} +\caption{Plan du musée 2}\label{m2} \end{figure} \bigskip -Généraliser ce problème sur les graphes. Décrire un algorithme pour le -résoudre~? +Généraliser ce problème sur les graphes. Décrire un algorithme pour le +résoudre~? \end{exo} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Codage des graphes} -On s'intéresse maintenant à coder les graphes (en machine). Il y a deux -méthodes principales (qui admettent des variantes), le codage par liste +On s'intéresse maintenant à coder les graphes (en machine). Il y a deux +méthodes principales (qui admettent des variantes), le codage par liste d'adjacence et le codage par matrice d'adjacence. \subsection{Codage par matrices d'adjacence} -Soit $G=(V,E)$ un graphe. On suppose, sans perte de généralité, que +Soit $G=(V,E)$ un graphe. On suppose, sans perte de généralité, que $V=\{1,\ldots,n\}$. On appelle {\bf matrice d'adjacence} de $V$ le tableau (matrice) de taille $n$ sur $n$ ne contenant que des $0$ ou des $1$ et -défini par~: la case de la $i$-ème ligne et de la $j$-ième colonne contient +défini par~: la case de la $i$-ème ligne et de la $j$-ième colonne contient un $1$ si et seulement si $(i,j)\in E$. -On considère par exemple le graphe -$(\{1,2,3,4\},\{(1,1),(1,2),(3,1),(2,4),(3,4)\})$ dessiné sur la +On considère par exemple le graphe +$(\{1,2,3,4\},\{(1,1),(1,2),(3,1),(2,4),(3,4)\})$ dessiné sur la figure~\ref{fig:g1}. Sa matrice d'adjacence est $$\left( \begin{array}{cccc} @@ -602,7 +600,7 @@ $$\left( \right). $$ -Réciproquement, le graphe dont la matrice d'adjacence est +Réciproquement, le graphe dont la matrice d'adjacence est $\left( \begin{array}{cccc} 0 & 0 & 1 & 0\\ @@ -643,20 +641,20 @@ Dessiner le graphe dont la matrice d'adjacence est $\left( \right)$. \noindent -Quel est la matrice d'adjacence du graphe où $V=\{1,\ldots,7\}$ et +Quel est la matrice d'adjacence du graphe où $V=\{1,\ldots,7\}$ et $$E=\{(1,2),(4,2),(3,5),(7,1),(6,4),(1,5),(5,0) \}~?$$ \end{exo} \begin{exo} Soit $(V,E)$ un graphe. Comment lit-on sur la matrice d'adjacence de ce -graphe que la relation $E$ est réflexive~? symétrique~? antisymétrique~? +graphe que la relation $E$ est réflexive~? symétrique~? antisymétrique~? \end{exo} \begin{exo} -Pour tout graphe orienté $G$, on note $G^R$ le graphe défini par~: les -sommets de $G^R$ sont les mêmes que ceux de $G$ et $(x,y)$ est une arête de - $G^R$ si et seulement si $(y,x) $ est une arête de $G$. Le graphe $G^R$ +Pour tout graphe orienté $G$, on note $G^R$ le graphe défini par~: les +sommets de $G^R$ sont les mêmes que ceux de $G$ et $(x,y)$ est une arête de + $G^R$ si et seulement si $(y,x) $ est une arête de $G$. Le graphe $G^R$ s'appelle {\it miroir} de $G$. \begin{figure}[h] @@ -689,12 +687,12 @@ s'appelle {\it miroir} de $G$. \subsection{Codage par liste d'adjacence} -Le codage d'un graphe par liste d'adjacence consiste à coder, pour chaque +Le codage d'un graphe par liste d'adjacence consiste à coder, pour chaque sommet du graphe, l'ensemble de ses voisins par une liste {\it - triée}\footnote{Attention, le fait qu'elle soit triée n'est pas toujours - imposé dans la littérature, mais c'est le choix que nous prendrons.}. -On considère encore que $V=\{1,\ldots,n\}$. On dispose alors d'un tableau de -taille $n$ dont la première case contient la liste des voisins de $1$, la + triée}\footnote{Attention, le fait qu'elle soit triée n'est pas toujours + imposé dans la littérature, mais c'est le choix que nous prendrons.}. +On considère encore que $V=\{1,\ldots,n\}$. On dispose alors d'un tableau de +taille $n$ dont la première case contient la liste des voisins de $1$, la seconde la liste des voisins de $2$, etc. Par exemple, le graphe de la figure~\ref{fig:g1} se code par le tableau de @@ -743,7 +741,7 @@ liste~: \begin{exo} -Dessiner le graphe dont la représentation par liste d'adjacence est~: +Dessiner le graphe dont la représentation par liste d'adjacence est~: \medskip \begin{center} @@ -820,47 +818,47 @@ Dessiner le graphe dont la repr \end{exo} \begin{exo} -Dessiner la représentation par liste d'adjacence du graphe de la +Dessiner la représentation par liste d'adjacence du graphe de la figure~\ref{fig:grapheexo1}. \end{exo} \begin{exo}\label{titi} -On considère que l'on code en Python un graphe par liste d'adjacence de la -manière suivante~: +On considère que l'on code en Python un graphe par liste d'adjacence de la +manière suivante~: \begin{itemize} \item Un graphe un un couple de la forme $(V,E)$, -\item $V$ est une liste d'éléments tous différents, triés, -\item $E$ est un dictionnaire qui à chaque élément de $V$ associe la liste - triée de ses voisins. +\item $V$ est une liste d'éléments tous différents, triés, +\item $E$ est un dictionnaire qui à chaque élément de $V$ associe la liste + triée de ses voisins. \end{itemize} \begin{enumerate} -\item Dessiner le graphe correspondant à \\ +\item Dessiner le graphe correspondant à \\ {\tt ([1,2,3],\{1:[2],2:[2,3],3:[1,3]\})} -\item Écrire une fonction qui teste si un coupe $(V,E)$ où $V$ est une liste - d'entiers et $E$ un dictionnaire, représente bien un graphe par liste +\item Écrire une fonction qui teste si un coupe $(V,E)$ où $V$ est une liste + d'entiers et $E$ un dictionnaire, représente bien un graphe par liste d'adjacence. -\item Écrire une fonction qui compte le nombre d'arêtes d'un graphe. +\item Écrire une fonction qui compte le nombre d'arêtes d'un graphe. -\item Écrire une fonction qui teste si $(i,j)$ est une arête d'un graphe. +\item Écrire une fonction qui teste si $(i,j)$ est une arête d'un graphe. \item On appelle {\it sommet bloquant} un sommet $i$ tel que pour tout - sommet $j$, $(i,j)$ n'est pas une arête. Écrire une fonction qui teste + sommet $j$, $(i,j)$ n'est pas une arête. Écrire une fonction qui teste si un sommet est bloquant. \item On appelle {\it sommet puits} un sommet $i$ tel que pour tout - sommet $j\neq i$, $(i,j)$ n'est pas une arête et tel que $(i,i)$ soit - une arête. Écrire une fonction qui teste + sommet $j\neq i$, $(i,j)$ n'est pas une arête et tel que $(i,i)$ soit + une arête. Écrire une fonction qui teste si un sommet est un puits. -\item Écrire une fonction qui ajoute une arête $(i,j)$ à un graphe. +\item Écrire une fonction qui ajoute une arête $(i,j)$ à un graphe. -\item Écrire une fonction qui supprime une arête $(i,j)$ à un graphe (on - rappelle que la méthode {\tt remove} de python retire la première - occurrence d'une valeur donnée en paramètre). +\item Écrire une fonction qui supprime une arête $(i,j)$ à un graphe (on + rappelle que la méthode {\tt remove} de python retire la première + occurrence d'une valeur donnée en paramètre). \end{enumerate} @@ -883,40 +881,40 @@ mani L'exercice suivant est une introduction aux parcours de graphes. \begin{exo} -On considère le graphe de la figure~\ref{fig:zomb}. Il y a une flèche entre -$x$ et $y$ si $x$ connaît l'adresse de $y$. On considère aussi que certains -individus dans cette liste peuvent être des zombies. +On considère le graphe de la figure~\ref{fig:zomb}. Il y a une flèche entre +$x$ et $y$ si $x$ connaît l'adresse de $y$. On considère aussi que certains +individus dans cette liste peuvent être des zombies. \begin{enumerate} -\item On considère que chaque nuit, un zombie va mordre et donc transformer - en zombie des individus dont il connaît l'adresse et qui ne sont pas encore +\item On considère que chaque nuit, un zombie va mordre et donc transformer + en zombie des individus dont il connaît l'adresse et qui ne sont pas encore zombies. Si c'est possible, chaque zombie transforme au moins - un zombie par nuit. En supposant qu'au départ seule Karina est un zombie, - donner quelques possibilités indiquant, in fine, qui zombifie qui? - Dessiner les solutions à l'aide d'un graphe où $(x,y)$ est une arête si - $x$ a zombifié $y$. + un zombie par nuit. En supposant qu'au départ seule Karina est un zombie, + donner quelques possibilités indiquant, in fine, qui zombifie qui? + Dessiner les solutions à l'aide d'un graphe où $(x,y)$ est une arête si + $x$ a zombifié $y$. -\item On considère maintenant que chaque nuit, chaque zombie va transformer - tous les individus dont il connaît l'adresse et qui ne sont pas encore - zombies. En supposant qu'au départ seule Karina est un zombie, - donner quelques possibilités indiquant, in fine, qui zombifie qui? +\item On considère maintenant que chaque nuit, chaque zombie va transformer + tous les individus dont il connaît l'adresse et qui ne sont pas encore + zombies. En supposant qu'au départ seule Karina est un zombie, + donner quelques possibilités indiquant, in fine, qui zombifie qui? \item On suppose maintenant que chaque zombie doit non seulement transformer - tous les individus dont il connaît l'adresse et qui ne sont pas encore - zombies, mais aussi dans l'ordre croissant de leur numéros. Par exemple, + tous les individus dont il connaît l'adresse et qui ne sont pas encore + zombies, mais aussi dans l'ordre croissant de leur numéros. Par exemple, Karina transformera dans l'ordre Raph, Mike puis David. On suppose de plus - que chaque nuit les zombies vont mordre à tour de rôle, en commençant par - celui qui à été transformé en zombies le plus anciennement. En supposant - qu'au départ seule Karina est un zombie. Écrire qui zombifie qui, et dans + que chaque nuit les zombies vont mordre à tour de rôle, en commençant par + celui qui à été transformé en zombies le plus anciennement. En supposant + qu'au départ seule Karina est un zombie. Écrire qui zombifie qui, et dans quel ordre. \item On suppose maintenant que chaque nuit, un zombie dont aucun voisin (au sens des graphes) - n'est zombie va mordre le premier (par ordre de numéro) des individus non - zombies qu'il connaît qui n'est pas encore zombie. Un zombie qui a au moins + n'est zombie va mordre le premier (par ordre de numéro) des individus non + zombies qu'il connaît qui n'est pas encore zombie. Un zombie qui a au moins un voisin zombie ne fait rien la nuit, il attend. Un zombie dont tous les - voisins sont devenus eux aussi des zombies se transforme en poussière. + voisins sont devenus eux aussi des zombies se transforme en poussière. En supposant - qu'au départ seule Karina est un zombie, Écrire qui a zombifié qui, et dans + qu'au départ seule Karina est un zombie, Écrire qui a zombifié qui, et dans quel ordre. @@ -961,8 +959,8 @@ individus dans cette liste peuvent \end{exo} -Les graphes obtenus dans les questions de l'exercice précédent s'appellent -des {\it arbres couvrants}. La façon de procéder de la question~3 s'appelle +Les graphes obtenus dans les questions de l'exercice précédent s'appellent +des {\it arbres couvrants}. La façon de procéder de la question~3 s'appelle {\it parcours en largeur} et celle de la question~4 s'appelle {\it parcours en profondeur}. @@ -979,39 +977,39 @@ Un {\bf arbre} est un graphe $G=(V,E)$ tel que~: \item[(2)] Si $(x,y)$ et $(z,y)$ sont dans $E$, alors $x=z$. -\item[(3)] Il existe un sommet $x_0$, appelé {\bf racine}, tel que pour - tout sommet $y$, il existe une chemin de $x_0$ à $y$. +\item[(3)] Il existe un sommet $x_0$, appelé {\bf racine}, tel que pour + tout sommet $y$, il existe une chemin de $x_0$ à $y$. \end{enumerate} -Un exemple d'arbre dont la racine est $1$ est dessiné sur la +Un exemple d'arbre dont la racine est $1$ est dessiné sur la figure~\ref{fig:arbre}. \begin{exo} -Dessiner trois arbres différents à 6 sommets. +Dessiner trois arbres différents à 6 sommets. \end{exo} \begin{exo} -Dessiner un graphe qui vérifie $(1)$ et $(2)$ de la définition mais qui -n'est pas un arbre. Même question avec $(2)$ et $(3)$. Même question avec +Dessiner un graphe qui vérifie $(1)$ et $(2)$ de la définition mais qui +n'est pas un arbre. Même question avec $(2)$ et $(3)$. Même question avec $(3)$ et $(1)$. \end{exo} \medskip -Dans un arbre, on utilise à la fois une terminologie de type -\og {\it végétal}\fg{} et +Dans un arbre, on utilise à la fois une terminologie de type +\og {\it végétal}\fg{} et aussi -de type \og {\it arbre généalogique}\fg{}. +de type \og {\it arbre généalogique}\fg{}. On appelle {\bf feuille} tout sommet d'un arbre qui n'a pas de voisin. Tout -chemin de la racine à une feuille est appelée {\bf branche}. Les voisins -d'un noeud sont appelés ses {\bf fils}. +chemin de la racine à une feuille est appelée {\bf branche}. Les voisins +d'un noeud sont appelés ses {\bf fils}. Tous les sommets atteignables depuis un sommet $x$ sont dits les {\bf - descendants} de $x$ et ils constituent le {\bf sous-arbre} enraciné en $x$. -Si $y$ est atteignable depuis $x$, alors $x$ est un {\bf ancêtre} de $y$. -Si $y$ est un voisin de $x$, alors $x$ est le {\bf père} de $y$. Deux sommets -qui ont le même père sont {\bf frères}. + descendants} de $x$ et ils constituent le {\bf sous-arbre} enraciné en $x$. +Si $y$ est atteignable depuis $x$, alors $x$ est un {\bf ancêtre} de $y$. +Si $y$ est un voisin de $x$, alors $x$ est le {\bf père} de $y$. Deux sommets +qui ont le même père sont {\bf frères}. Par exemple, dans le dessin de la figure~\ref{fig:arbre}, -$6$ est le père de $7$, $3$ est un frère de $2$ et $5$ est une descendant de +$6$ est le père de $7$, $3$ est un frère de $2$ et $5$ est une descendant de $1$. \begin{figure} @@ -1046,19 +1044,19 @@ $1$. \begin{exo} Dans le graphe de la figure~\ref{fig:arbre}, quels sont les descendants de -$3$? Les fils de $1$? Les ancêtres de $6$? les feuilles? +$3$? Les fils de $1$? Les ancêtres de $6$? les feuilles? \end{exo} \begin{exo} -On considère dans cet exercice des arbres codés par liste d'adjacence comme +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é. +\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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -1067,11 +1065,11 @@ racine est le premier sommet de la liste $V$. Parcourir un arbre, c'est appliquer un algorithme qui va visiter, une et une seule fois chaque sommet de l'arbre. Les deux parcours les plus connus, sont -les parcours préfixes et suffixes. A chaque visite de noeud, une fonction -{\tt Traiter} est appliquée, selon ce que l'on souhaite faire. +les parcours préfixes et suffixes. A chaque visite de noeud, une fonction +{\tt Traiter} est appliquée, selon ce que l'on souhaite faire. -Le parcours Préfixe est l'algorithme récursif suivant. Initialement, le -parcours est lancé à la racine. +Le parcours Préfixe est l'algorithme récursif suivant. Initialement, le +parcours est lancé à la racine. \begin{verbatim} Parcours-Prefixe(V,E,x): @@ -1098,7 +1096,7 @@ $2$ $4$ $5$ \noindent -De même {\tt Parcours-Prefixe(3)} retourne +De même {\tt Parcours-Prefixe(3)} retourne $3$ $6$ $7$ $8$ $9$ @@ -1109,7 +1107,7 @@ $1$ $2$ $4$ $5$ $3$ $6$ $7$ $8$ $9$ \begin{exo} -Que retourne l'algorithme de parcours préfixe sur l'arbre de la figure~\ref{fig:arbre2}. +Que retourne l'algorithme de parcours préfixe sur l'arbre de la figure~\ref{fig:arbre2}. \begin{figure} @@ -1144,8 +1142,8 @@ Que retourne l'algorithme de parcours pr \end{exo} \medskip -La parcours suffixe est identique à la différence près que le traitement se -fait après l'appel récursif. +La parcours suffixe est identique à la différence près que le traitement se +fait après l'appel récursif. \begin{verbatim} Parcours-Suffixe(V,E,x): @@ -1160,28 +1158,28 @@ Que donne le parcours suffixe sur les arbres des figures~\ref{fig:arbre} et~\ref \end{exo} \begin{exo} -Avec le même codage que précédemment, écrire en Python des fonctions de -parcours préfixe et suffixe. +Avec le même codage que précédemment, écrire en Python des fonctions de +parcours préfixe et suffixe. \end{exo} %%%%%%%%%%%%%%%%%%%%% \subsection{Arbres couvrants} -Attention, ici, on parle d'arbres couvrants de graphes orientés. +Attention, ici, on parle d'arbres couvrants de graphes orientés. -Soit $G=(V,E)$. Un arbre couvrant pour $G$, enraciné en $x\in V$, est un +Soit $G=(V,E)$. Un arbre couvrant pour $G$, enraciné en $x\in V$, est un arbre $(V^\prime,E^\prime)$ tel que \begin{enumerate} \item[(1)] $V^\prime\subseteq V$ et $E^\prime\subseteq E$. \item[(2)] $x$ est la racine de $(V^\prime,E^\prime)$. -\item[(3)] On ne peut pas rajouter à l'arbre un sommet ou une arête de sorte +\item[(3)] On ne peut pas rajouter à l'arbre un sommet ou une arête de sorte que les conditions - $(1)$ et $(2)$ soient toujours vérifiées: l'arbre est maximal. + $(1)$ et $(2)$ soient toujours vérifiées: l'arbre est maximal. \end{enumerate} Intuitivement un arbre couvrant est un arbre que l'on peut calquer sur un graphe -- conditions (1) et (2) -- sans pouvoir le prolonger. -Considérons par exemple le graphe de la figure~\ref{fig:graphcouvrant}. +Considérons par exemple le graphe de la figure~\ref{fig:graphcouvrant}. \begin{figure}[h] \begin{center} @@ -1237,7 +1235,7 @@ Consid \end{figure} Dans ce graphe, l'arbre de gauche de la figure~\ref{fig:graphcouvrant2} -vérifie bien $(1)$ et $(2)$ mais +vérifie bien $(1)$ et $(2)$ mais pas $(3)$. En revanche celui de droite est bien un arbre couvrant. @@ -1298,41 +1296,41 @@ pas $(3)$. En revanche celui de droite est bien un arbre couvrant. \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 +Écrire une fonction qui étant donné un graphe et un arbre codé en Python +comme précédemment, teste si l'arbre est un arbre couvrant du graphe (on ne testera pas si c'est bien un arbre). \end{exo} L'objectif des algorithmes de parcours de graphes est de construire des arbres couvrants de graphes afin, ensuite, d'appliquer des parcours (type -préfixe/suffixe) sur les arbres obtenus. Il existe deux constructions -d'arbres couvrant très utilisées, appelées {\it parcours en largeur} et {\it +préfixe/suffixe) sur les arbres obtenus. Il existe deux constructions +d'arbres couvrant très utilisées, appelées {\it parcours en largeur} et {\it parcours en profondeur}. %%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Parcours en largeur} -On ne donne pas explicitement l'algorithme de parcours en largeur à partir +On ne donne pas explicitement l'algorithme de parcours en largeur à partir de $x$ qui -demanderait l'introduction des structures de données. On se contente d'un -pseudo-algorithme expliquant la méthode~: +demanderait l'introduction des structures de données. On se contente d'un +pseudo-algorithme expliquant la méthode~: \begin{enumerate} \item $x$ est la racine de l'arbre. -\item On insère dans l'arbre tous les voisins de $x$ (sauf éventuellement +\item On insère dans l'arbre tous les voisins de $x$ (sauf éventuellement $x$), dans l'ordre. -\item On insère (dans l'ordre) dans l'arbre tous les voisins de la feuille +\item On insère (dans l'ordre) dans l'arbre tous les voisins de la feuille la plus anciennement introduite dans l'arbre et pour laquelle c'est possible. -\item On recommence l'étape précédente tant que c'est possible. +\item On recommence l'étape précédente tant que c'est possible. \end{enumerate} -Si l'on exécute le parcours sur le graphe de la -figure~\ref{fig:graphcouvrant}, en partant du sommet $3$. Après les étapes +Si l'on exécute le parcours sur le graphe de la +figure~\ref{fig:graphcouvrant}, en partant du sommet $3$. Après les étapes $1$ et $2$ on a l'arbre $A_1$ de la figure~\ref{fig:parcourslargeur}. La feuille introduite le plus anciennement -(attention à l'ordre qui est l'ordre des numéro des sommets) est $2$. On -ajoute donc $1$ et $6$ -- et pas $7$ qui y est déjà. On obtient alors +(attention à l'ordre qui est l'ordre des numéro des sommets) est $2$. On +ajoute donc $1$ et $6$ -- et pas $7$ qui y est déjà. On obtient alors l'arbre $A_2$ de la figure~\ref{fig:parcourslargeur}. \begin{figure}[h] @@ -1389,11 +1387,11 @@ l'arbre $A_2$ de la figure~\ref{fig:parcourslargeur}. Ensuite, la feuille la plus anciennement introduite est $4$. Son seul voisin est $9$ qui n'est pas encore dans l'arbre. On obtient donc l'arbre $A_3$ de la figure~\ref{fig:parcourslargeurA3}. -Ensuite il s'agit du sommet $5$ dont l'unique fils $3$ est déjà dans -l'arbre. La construction n'évolue donc pas pour $5$. Ensuite, on a fini les -fils de $3$, on passe donc aux fils du premier fils de $3$, à savoir $2$. -Les fils de $1$ sont $2$, $6$ et $7$, qui sont déjà dans l'arbre. En -continuant ainsi, on voit qu'il n'y a plus rien à ajouter. On obtient donc +Ensuite il s'agit du sommet $5$ dont l'unique fils $3$ est déjà dans +l'arbre. La construction n'évolue donc pas pour $5$. Ensuite, on a fini les +fils de $3$, on passe donc aux fils du premier fils de $3$, à savoir $2$. +Les fils de $1$ sont $2$, $6$ et $7$, qui sont déjà dans l'arbre. En +continuant ainsi, on voit qu'il n'y a plus rien à ajouter. On obtient donc l'arbre de la figure~\ref{fig:parcourslargeurA3} \begin{figure}[ht] @@ -1435,8 +1433,8 @@ l'arbre de la figure~\ref{fig:parcourslargeurA3} \begin{exo} \begin{enumerate} \item Sur le graphe de la figure ci-dessous, dessiner les arbres -obtenus par un parcours en largeur à partir de $2$. Même question en partant -de $6$. Même question en partant de $9$. +obtenus par un parcours en largeur à partir de $2$. Même question en partant +de $6$. Même question en partant de $9$. \begin{center} \begin{tikzpicture}[scale = 0.8] @@ -1490,7 +1488,7 @@ de $6$. M \end{center} -\item Même question à partir de $3$, puis de $0$, puis de $8$ sur le graphe de +\item Même question à partir de $3$, puis de $0$, puis de $8$ sur le graphe de la figure~\ref{fig:exo}. \begin{figure}[h] @@ -1584,29 +1582,29 @@ la figure~\ref{fig:exo}. \begin{exo} -Écrire en Python l'algorithme de parcours en largeur pour un graphe codé par +É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 +Écrire en Python une fonction qui teste si un graphe donné par liste d'adjacence est un arbre dont la racine est le plus petit sommet. \end{exo} \begin{exo} Les {\em composantes fortement connexes} d'un graphe sont des sous-ensembles de -sommets telles que~: (1) tout sommet appartient à une composante fortement +sommets telles que~: (1) tout sommet appartient à une composante fortement connexe, (2) s'il existe un chemin de $p$ vers $q$ et un chemin de $q$ vers -$p$, alors $p$ et $q$ doivent appartenir à la même composante fortement -connexe~; et réciproquement. +$p$, alors $p$ et $q$ doivent appartenir à la même composante fortement +connexe~; et réciproquement. \begin{enumerate} -\item Deux composantes fortement connexes sont-elles forcément +\item Deux composantes fortement connexes sont-elles forcément disjointes? Pourquoi? \item Quels sont les composantes fortement connexes du graphe de la figure~\ref{fig:exo}. -\item Décrire une méthode algorithmique pour trouver les composantes +\item Décrire une méthode algorithmique pour trouver les composantes fortement connexe d'un graphe. \end{enumerate} \end{exo} @@ -1614,7 +1612,7 @@ connexe~; et r % \begin{exo} % Comment utiliser un parcours en largeur pour trouver un chemin de taille la -% plus courte possible entre deux sommets donnés? +% plus courte possible entre deux sommets donnés? % \end{exo} %%%%%%%%%%%%%%% @@ -1647,23 +1645,23 @@ connexe~; et r \end{figure} -On ne donne pas explicitement l'algorithme de parcours en profondeur à partir +On ne donne pas explicitement l'algorithme de parcours en profondeur à partir de $x$ qui -demanderait l'introduction des structures de données. On se contente d'un -pseudo-algorithme expliquant la méthode~: +demanderait l'introduction des structures de données. On se contente d'un +pseudo-algorithme expliquant la méthode~: \begin{enumerate} \item $x$ est la racine de l'arbre. -\item On insère dans l'arbre le premier voisin de $x$ (sauf éventuellement +\item On insère dans l'arbre le premier voisin de $x$ (sauf éventuellement $x$). -\item On insère dans l'arbre le premier voisins du sommet - le plus récemment introduit dans l'arbre et pour lequel c'est possible. -\item On recommence l'étape précédente tant que c'est possible. +\item On insère dans l'arbre le premier voisins du sommet + le plus récemment introduit dans l'arbre et pour lequel c'est possible. +\item On recommence l'étape précédente tant que c'est possible. \end{enumerate} -On va appliquer la méthode sur l'arbre de la figure~\ref{fig:graphcouvrant}, -en partant du sommet $3$. L'arbre commence par $3$ à la racine. Puis on -introduit le plus petit fils de $3$, c'est-à-dire $2$. La feuille la plus -récente de l'arbre est $2$, donc on introduit le plus petit fils de $2$, à +On va appliquer la méthode sur l'arbre de la figure~\ref{fig:graphcouvrant}, +en partant du sommet $3$. L'arbre commence par $3$ à la racine. Puis on +introduit le plus petit fils de $3$, c'est-à-dire $2$. La feuille la plus +récente de l'arbre est $2$, donc on introduit le plus petit fils de $2$, à savoir $1$. A nouveau, on va introduire $6$, puis $9$. On obtient alors l'arbre de la figure~\ref{fig:prof1}. @@ -1671,7 +1669,7 @@ l'arbre de la figure~\ref{fig:prof1}. \pagebreak[3] \begin{exo} -Donner les parcours en profondeur obtenus à partir de $0$, puis $8$, puis $7$ +Donner les parcours en profondeur obtenus à partir de $0$, puis $8$, puis $7$ sur le graphe de la figure~\ref{fig:exo}. @@ -1762,12 +1760,12 @@ sur le graphe de la figure~\ref{fig:exo}. \begin{exo} -Écrire en Python l'algorithme de parcours en profondeur pour un graphe codé par +Écrire en Python l'algorithme de parcours en profondeur pour un graphe codé par liste d'adjacence. \end{exo} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%ù -%\input{automates} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%ù +\input{automates} \end{document} diff --git a/main13.aux b/main13.aux index 9eb2c17..83da33a 100644 --- a/main13.aux +++ b/main13.aux @@ -171,7 +171,7 @@ \@writefile{toc}{\contentsline {chapter}{\numberline {3}Introduction \IeC {\`a} la th\IeC {\'e}orie des ensembles}{20}{chapter.3}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {I}Rappels de th\IeC {\'e}orie des ensembles}{20}{section.3.1}} +\@writefile{toc}{\contentsline {section}{\numberline {I}Des D\IeC {\'e}finitions}{20}{section.3.1}} \@writefile{toc}{\contentsline {subsection}{\numberline {I.1}Notion premi\IeC {\`e}re d'ensemble}{20}{subsection.3.1.1}} \@writefile{thm}{\contentsline {Notation}{{Notation}{3.{1}}{}}{20}{Notation.3.1}} \@writefile{thm}{\contentsline {Exo}{{Exercice}{3.{1}}{}}{20}{Exo.3.1}} @@ -344,8 +344,8 @@ \@writefile{thm}{\contentsline {Exo}{{Exercice}{5.{30}}{}}{35}{Exo.5.30}} \@writefile{toc}{\contentsline {part}{IV\hspace {1em}Annexes}{36}{part.4}} \@input{PPN.aux} +\@writefile{toc}{\contentsline {chapter}{Index}{38}{chapter.6}} \bibstyle{alpha} \bibdata{biblio} \bibcite{Dowek07}{Dow07} -\@writefile{toc}{\contentsline {chapter}{Index}{38}{chapter.6}} \@input{Bibliographie.aux} diff --git a/main13.blg b/main13.blg index d1b653f..8bab2e0 100644 --- a/main13.blg +++ b/main13.blg @@ -1,4 +1,4 @@ -This is BibTeX, Version 0.99d (TeX Live 2012/Debian) +This is BibTeX, Version 0.99d (TeX Live 2013/Debian) Capacity: max_strings=35307, hash_size=35307, hash_prime=30011 The top-level auxiliary file: main13.aux A level-1 auxiliary file: Remerciements.aux diff --git a/main13.log b/main13.log index da137fa..fd7c6ad 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) 12 FEB 2014 09:14 +This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013/Debian) (format=pdflatex 2013.11.13) 21 MAR 2014 10:57 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -1232,20 +1232,8 @@ m/it/10.95 H$ \T1/ptm/m/n/10.95 est une cons Chapitre 3. (./ensembles/IntroAuxEnsembles13.tex [20 -] [21] -Overfull \hbox (37.774pt too wide) in paragraph at lines 186--187 -[]\T1/ptm/m/it/10.95 Faire la réunion des en-sembles $\OML/lmm/m/it/10.95 A$ \T -1/ptm/m/it/10.95 et $\OML/lmm/m/it/10.95 B$\T1/ptm/m/it/10.95 , quand $\OML/lmm -/m/it/10.95 A \OT1/lmr/m/n/10.95 = \OMS/lmsy/m/n/10.95 f\OML/lmm/m/it/10.95 x \ -OMS/lmsy/m/n/10.95 2 \U/msb/m/n/10.95 N\OMS/lmsy/m/n/10.95 j\OML/lmm/m/it/10.95 - x[]\OMS/lmsy/m/n/10.95 g$\T1/ptm/m/it/10.95 , et $\OML/lmm/m/it/10.95 B \OT1/l -mr/m/n/10.95 = \OMS/lmsy/m/n/10.95 f\OML/lmm/m/it/10.95 x \OMS/lmsy/m/n/10.95 2 - \U/msb/m/n/10.95 N\OMS/lmsy/m/n/10.95 j\OML/lmm/m/it/10.95 x[]\OMS/lmsy/m/n/10 -.95 g$\T1/ptm/m/it/10.95 . - [] - -[22] -Overfull \hbox (2.81169pt too wide) in paragraph at lines 301--302 +] [21] [22] +Overfull \hbox (2.81169pt too wide) in paragraph at lines 304--305 []\T1/ptm/m/it/10.95 On ap-pelle fonc-tion ca-rac-té-ris-tique de la par- [] @@ -1339,9 +1327,10 @@ Chapitre 6. ) [37 -] -No file main13.ind. -(./main13.bbl) [38 +] (./main13.ind [38 + + +]) (./main13.bbl) [39 ] @@ -1350,7 +1339,7 @@ No file main13.ind. (./Bibliographie.tex LaTeX Font Info: Font shape `T1/ptm/bx/it' in size <10.95> not available (Font) Font shape `T1/ptm/b/it' tried instead on input line 5. -) [39 +) [40 ] @@ -1359,17 +1348,17 @@ LaTeX Font Info: Font shape `T1/ptm/bx/it' in size <10.95> not available Package atveryend Info: Empty hook `BeforeClearDocument' on input line 336. Package atveryend Info: Empty hook `AfterLastShipout' on input line 336. - (./main13.aux -(./Remerciements.aux) (./PPN.aux) (./Bibliographie.aux)) + +(./main13.aux (./Remerciements.aux) (./PPN.aux) (./Bibliographie.aux)) Package atveryend Info: Executing hook `AtVeryEndDocument' on input line 336. Package atveryend Info: Executing hook `AtEndAfterFileList' on input line 336. Package rerunfilecheck Info: File `main13.out' has not changed. -(rerunfilecheck) Checksum: 549A97A69E00F57B1ED5A217AD3094DF;3888. +(rerunfilecheck) Checksum: 641176623C294C8C81EC22757596E698;3871. Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 336. ) Here is how much of TeX's memory you used: - 12343 strings out of 495002 - 166720 string characters out of 6180261 + 12346 strings out of 495002 + 166749 string characters out of 6180261 281698 words of memory out of 5000000 14728 multiletter control sequences out of 15000+600000 109807 words of font info for 113 fonts, out of 8000000 for 9000 @@ -1394,10 +1383,10 @@ mb8a.pfb> -Output written on main13.pdf (40 pages, 358833 bytes). +Output written on main13.pdf (41 pages, 361094 bytes). PDF statistics: - 1076 PDF objects out of 1200 (max. 8388607) - 1003 compressed objects within 11 object streams - 523 named destinations out of 1000 (max. 500000) + 1132 PDF objects out of 1200 (max. 8388607) + 1058 compressed objects within 11 object streams + 524 named destinations out of 1000 (max. 500000) 417 words of extra memory for PDF output out of 10000 (max. 10000000) diff --git a/main13.out b/main13.out index 9e54e84..2b10539 100644 --- a/main13.out +++ b/main13.out @@ -19,7 +19,7 @@ \BOOKMARK [2][]{subsection.2.3.5}{Simplification du calcul des fonctions de v\351rit\351}{section.2.3}% 19 \BOOKMARK [-1][]{part.2}{II Th\351orie des ensembles}{}% 20 \BOOKMARK [0][]{chapter.3}{Introduction \340 la th\351orie des ensembles}{part.2}% 21 -\BOOKMARK [1][]{section.3.1}{Rappels de th\351orie des ensembles}{chapter.3}% 22 +\BOOKMARK [1][]{section.3.1}{Des D\351finitions}{chapter.3}% 22 \BOOKMARK [2][]{subsection.3.1.1}{Notion premi\350re d'ensemble}{section.3.1}% 23 \BOOKMARK [2][]{subsection.3.1.2}{R\350gles de fonctionnement}{section.3.1}% 24 \BOOKMARK [2][]{subsection.3.1.3}{Sous-ensembles, ensemble des parties}{section.3.1}% 25 diff --git a/main13.pdf b/main13.pdf index 40466c7..2c1e0c4 100644 Binary files a/main13.pdf and b/main13.pdf differ diff --git a/main13.toc b/main13.toc index acab1ef..eb5fe97 100644 --- a/main13.toc +++ b/main13.toc @@ -22,7 +22,7 @@ \contentsline {subsection}{\numberline {III.5}Simplification du calcul des fonctions de v\IeC {\'e}rit\IeC {\'e}}{17}{subsection.2.3.5} \contentsline {part}{II\hspace {1em}Th\IeC {\'e}orie des ensembles}{19}{part.2} \contentsline {chapter}{\numberline {3}Introduction \IeC {\`a} la th\IeC {\'e}orie des ensembles}{20}{chapter.3} -\contentsline {section}{\numberline {I}Rappels de th\IeC {\'e}orie des ensembles}{20}{section.3.1} +\contentsline {section}{\numberline {I}Des D\IeC {\'e}finitions}{20}{section.3.1} \contentsline {subsection}{\numberline {I.1}Notion premi\IeC {\`e}re d'ensemble}{20}{subsection.3.1.1} \contentsline {subsection}{\numberline {I.2}R\IeC {\`e}gles de fonctionnement}{20}{subsection.3.1.2} \contentsline {paragraph}{Relation d'appartenance.}{20}{section*.2}