\Annee{2002}
\Titre{Groupes de TD, composantes connexes d'un graphe}
\Auteur{Vincent \textsc{Guirardel}}

\Date{2002/12/04} % Format AAAA/MM/JJ. pour le 5 mars 2001: \Date{2001/03/05}

\Niveau{\DEUGi} %Le niveau principal. Typiquement: \DEUGi (=1ere annee), \DEUGii (=2eme annee), \Licence, ...

\AnglePedagogique{\Decouverte} %l'angle pedagogique principal. Typiquement: \AQuoiCaSert, \Experimental, ...

\AnglesSecondaires{} %Eventuellement, les angles pedagogiques secondaires separes par des virgules

\Theme{\Ensembles} %Theme principal. Typiquement: \AlgLin, \Suites, \Series, ...

\ThemesSecondaires{Relations d'equivalence, Graphes} %Eventuellement, les themes secondaires separes par des virgules

\Objectif{Cet exercice part d'un algorithme de parcours d'un graphe qui est donn\'e aux \'etudiants
sous forme d'un algorithme de cr\'eation de groupe de TD.

La premi\`ere question est volontairement d\'eroutante: un seul groupe suffit !
} % Partie objectifs et commentaires.


\begin{exo}

Arwen, Bilbo, Celebrindal, Dunadan, Eowyn, Frodon, Galadriel, Hurin, Isil,
James Bond, Karine, Legolas, Morwen, Nimroth, Onomatopee, Peregrin, 
Quinine, Radagast, Silmarien, Thorin, Uinen, Voronwe, Wendy, Xerxes,
Yavanna et Zorglub sont inscrits en UD Maths et ont leurs propres opinions
sur les regroupements souhaitables en TD. Ils soumettent \`a l'administration 
la liste de leurs desiderata sous la forme suivante: (A,B), (A,F), (E,P),
(G,L), (G,R), (G,T), (C,H), (I,H), (M,H), (S,N), (U,V), (Y,V). Par exemple,
la pr\'esence de (A,B) dans la liste signifie que Arwen veut \^etre dans
le m\^eme groupe que Bilbo. 

\sq Quel est le nombre minimum de groupes de TD qui permet de satisfaire
tout le monde ? 

\sq On cherche plut\^ot \`a former des groupes nombreux et petits. 

\ssq Si $x$ est l'un des 26 \'etudiants ci-dessus, on note $f(x)$ l'ensemble
des \'etudiants qui figurent n\'ecessairement dans le m\^eme groupe que $x$
d'apr\`es la liste ci-dessus, soit parce que ils ont \'et\'e demand\'es
par $x$, soit parce qu'ils ont demand\'e $x$. Par exemple, 
$f(A) = \{B,F\}$ et $f(H) = \{C,I\}$. Ecrire tous les $f(x)$. 

\ssq Montrer que pour chaque \'etudiant isol\'e (c'est \`a dire tel que $f(x) = \emptyset$), 
on satisfait les demandes des \'etudiants en mettant $x$ tout seul dans un groupe,
et en mettant tous les autres ensemble. 

\sq On propose l'algorithme suivant de constitution du groupe de TD
d'un \'etudiant donn\'e $x_{0}$: 
\begin{quote}  
\texttt{groupe} $:= \{x_{0}\}$ \newline
$\underline{\text{r\'ep\'eter}}$ \newline
\hspace*{0.3cm} \texttt{delta} $:= \left(\underset{x \in\text{\texttt{groupe}}}{\cup} f(x)\right) - \text{\texttt{groupe}} \;;\;
\text{\texttt{groupe}} := \text{\texttt{groupe}} \cup \text{\texttt{delta}}$ \newline
$\underline{\text{jusqu'\`a ce que:}} \; \text{\texttt{delta}} = \emptyset$. 
\end{quote}

\ssq Executer l'algorithme sur Arwen. 

\ssq Que conclure ?

\sq Quel est le lien de cet exercice avec les relations d'\'equivalence ?

\end{exo}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
