Exercices Alternatifs

Groupes de TD, composantes connexes d’un graphe

\begin{matrix}c \\ ◯ \end{matrix}2002 Vincent Guirardel (copyleft LDL : Licence pour Documents Libres).

     Source: groupes de TD.tex.

Version imprimable: groupes de TD.pdf

Théorie des ensembles, et structures de base. DEUG première année. Angle pédagogique : Découverte.

Objectifs et commentaires. Cet exercice part d’un algorithme de parcours d’un graphe qui est donné aux étudiants sous forme d’un algorithme de création de groupe de TD. La première question est volontairement déroutante : un seul groupe suffit !

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 à 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ésence de (A,B) dans la liste signifie que Arwen veut être dans le même groupe que Bilbo.

a. Quel est le nombre minimum de groupes de TD qui permet de satisfaire tout le monde ?

b. On cherche plutôt à former des groupes nombreux et petits.

(i). — Si x est l’un des 26 étudiants ci-dessus, on note f(x) l’ensemble des étudiants qui figurent nécessairement dans le même groupe que x d’après la liste ci-dessus, soit parce que ils ont été demandés par x, soit parce qu’ils ont demandé x. Par exemple, f(A) = {B, F } et f(H) = {C, I}. Ecrire tous les f(x).

(ii). — Montrer que pour chaque étudiant isolé (c’est à dire tel que f(x) = ∅), on satisfait les demandes des étudiants en mettant x tout seul dans un groupe, et en mettant tous les autres ensemble.

c. On propose l’algorithme suivant de constitution du groupe de TD d’un étudiant donné x_{0} :

     groupe := {x_{0}}

\underline{répéter}

       delta := ( ∪_{x∈groupe}f(x)) − groupe ; groupe := groupe ∪ delta

\underline{jusqu’à ce que :} delta = ∅.

(i). — Executer l’algorithme sur Arwen.

(ii). — Que conclure ? d. Quel est le lien de cet exercice avec les relations d’équivalence ?

2