\documentclass[]{report}
\usepackage[a4paper]{geometry}
\geometry{hmargin=1.5cm, vmargin=1.5cm }
\documentclass[]{report}
\usepackage[a4paper]{geometry}
\geometry{hmargin=1.5cm, vmargin=1.5cm }
\usepackage[T1]{fontenc}
\usepackage[french]{babel}
\usepackage{amsmath,amssymb,latexsym,eufrak,euscript,array}
\usepackage[T1]{fontenc}
\usepackage[french]{babel}
\usepackage{amsmath,amssymb,latexsym,eufrak,euscript,array}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\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
\end{itemize}
Par exemple $\left(\{1,2,3\},\{(1,2),(2,2),(3,1)\}\right)$ est un graphe
-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{enumerate}
\item $V=\{1,2,3\}$ et $E=\{(1,3)\}$~?
\item $V=\{1,2,3\}$ et $E=\{(1,6),(2,4)\}$~?
\begin{enumerate}
\item $V=\{1,2,3\}$ et $E=\{(1,3)\}$~?
\item $V=\{1,2,3\}$ et $E=\{(1,6),(2,4)\}$~?
-{\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
-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
$$(\{1,2,3,4\},\{(1,1),(1,2),(3,1),(2,4),(3,4)\})$$ peut se dessiner comme sur la
\begin{tikzpicture}
\node (1) at (0,0) {$1$};
\node (2) at (4,0) {$2$};
\begin{tikzpicture}
\node (1) at (0,0) {$1$};
\node (2) at (4,0) {$2$};
-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$.
-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)$.
$(x,y)\in E$ si et seulement $x$ est avant $y$ dans l'ordre du dictionnaire.
Dessiner le graphe $(V,E)$.
$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~?
$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~?
-$(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,
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,
-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.
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.
\begin{enumerate}
\item Un circuit de taille $1$,
\item Une boucle de longueur $9$ passant par $4$,
\begin{enumerate}
\item Un circuit de taille $1$,
\item Une boucle de longueur $9$ passant par $4$,
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~?
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~?
-\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
-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.
- 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
-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.
-\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
-\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
-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
-\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
-\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.
-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.
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 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.
-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
\item Il y a deux enfants qui se voient l'un l'autre.
\item Tout enfant voit au moins un autre enfant.
\end{enumerate}
\item Il y a deux enfants qui se voient l'un l'autre.
\item Tout enfant voit au moins un autre enfant.
\end{enumerate}
-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,
-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~:
-\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
-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.
\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}
\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}
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
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~?
%\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}
%\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}
-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
-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
$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
-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
$$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
$$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
-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$
- 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
seconde la liste des voisins de $2$, etc.
Par exemple, le graphe de la figure~\ref{fig:g1} se code par le tableau de
-\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.
{\tt ([1,2,3],\{1:[2],2:[2,3],3:[1,3]\})}
{\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
- 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
-\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).
-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.
-\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
- 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?
- 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,
- 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
- 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
-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
\item[(2)] Si $(x,y)$ et $(z,y)$ sont dans $E$, alors $x=z$.
\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$.
-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
-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
-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}.
- 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}.
-% \begin{exo}
-% On considère dans cet exercice des arbres codés par liste d'adjacence comme
-% dans l'exercice en Python de la page~\pageref{titi}. On suppose que la
-% racine est le premier sommet de la liste $V$.
-
-% \begin{enumerate}
-% \item Écrire une fonction qui compte le nombre de feuille d'un arbre.
-% \item Écrire une fonction qui compte le nombre de descendants d'un sommet
-% donné.
-% \end{enumerate}
-% \end{exo}
+\begin{exo}
+On considère dans cet exercice des arbres codés par liste d'adjacence comme
+dans l'exercice en Python de la page~\pageref{titi}. On suppose que la
+racine est le premier sommet de la liste $V$.
+
+\begin{enumerate}
+\item Écrire une fonction qui compte le nombre de feuille d'un arbre.
+\item Écrire une fonction qui compte le nombre de descendants d'un sommet
+ donné.
+\end{enumerate}
+\end{exo}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Parcours d'arbres}
Parcourir un arbre, c'est appliquer un algorithme qui va visiter, une et une
seule fois chaque sommet de l'arbre. Les deux parcours les plus connus, sont
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Parcours d'arbres}
Parcourir un arbre, c'est appliquer un algorithme qui va visiter, une et une
seule fois chaque sommet de l'arbre. Les deux parcours les plus connus, sont
-les parcours préfixes et suffixes. A chaque visite de noeud, une fonction
-{\tt Traiter} est appliquée, selon ce que l'on souhaite faire.
+les parcours préfixes et suffixes. A chaque visite de noeud, une fonction
+{\tt Traiter} est appliquée, selon ce que l'on souhaite faire.
-Le parcours Préfixe est l'algorithme récursif suivant. Initialement, le
-parcours est lancé à la racine.
+Le parcours Préfixe est l'algorithme récursif suivant. Initialement, le
+parcours est lancé à la racine.
-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{exo}
-% Avec le même codage que précédemment, écrire en Python des fonctions de
-% parcours préfixe et suffixe.
-% \end{exo}
+\begin{exo}
+Avec le même codage que précédemment, écrire en Python des fonctions de
+parcours préfixe et suffixe.
+\end{exo}
-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)$.
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)$.
\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.
\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.
-% \begin{exo}
-% Écrire une fonction qui étant donné un graphe et un arbre codé en Python
-% comme précédemment, teste si l'arbre est un arbre couvrant du graphe (on ne
-% testera pas si c'est bien un arbre).
-% \end{exo}
+\begin{exo}
+Écrire une fonction qui étant donné un graphe et un arbre codé en Python
+comme précédemment, teste si l'arbre est un arbre couvrant du graphe (on ne
+testera pas si c'est bien un arbre).
+\end{exo}
L'objectif des algorithmes de parcours de graphes est de construire des
arbres couvrants de graphes afin, ensuite, d'appliquer des parcours (type
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
-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~:
-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
$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
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, 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
-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{exo}
-% Écrire en Python une fonction qui teste si un graphe donné par liste
-% d'adjacence est un arbre dont la racine est le plus petit sommet.
-% \end{exo}
+\begin{exo}
+Écrire en Python une fonction qui teste si un graphe donné par liste
+d'adjacence est un arbre dont la racine est le plus petit sommet.
+\end{exo}
-$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.
-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~:
-\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.
-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}.
savoir $1$. A nouveau, on va introduire $6$, puis $9$. On obtient alors
l'arbre de la figure~\ref{fig:prof1}.
