Centrale Informatique optionnelle MP 2021

Corrigé

(c'est payant, sauf le début) : - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                          

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


Option informatique
MP

4 heures Calculatrice autorisée

2021

Arbres couvrants et pavages

Le seul langage de programmation autorisé dans cette épreuve est Caml.

Toutes les fonctions des modules Array et List, ainsi que les fonctions de la 
bibliothèque standard (celles qui
s'écrivent sans nom de module, comme max ou incr ainsi que les opérateurs comme 
/ ou mod) peuvent être
librement utilisés.

On utilisera également le générateur pseudo-aléatoire int du module Random. 
Quand n est un entier supérieur
ou égal à 1, l'appel Random.int n renvoie un entier dans l'intervalle [0,n] 
(compris entre 0 inclus et n exclu)
en simulant une loi uniforme. Les appels successifs à cette fonction 
fournissent des résultats indépendants.

Les candidats ne devront faire appel à aucun autre module.

En Caml, les tableaux d'objets d'un certain type 'a sont représentés par le 
type 'a array. L'expression tab. (i)
permet d'accéder à l'élément situé en i-ème position du tableau tab. Dans le 
texte, en dehors du code Caml, cet
élément sera noté T'abli]. Plus généralement, les objets mathématiques seront 
notés G, s, Adj... et représentés
en Caml par g, s, adj... sans que cela soit systématiquement explicité.

Dans ce problème, un graphe G est un couple ($, À) où :
-- S'est un ensemble fini dont les éléments sont les sommets de G :

-- À = (ap,4,....., 4m_1) est la suite des arêtes de G, une arête étant une 
partie a = {s,t} de S de cardinal 2.
Les sommets s et t sont appelés les extrémités de l'arête a et on dira que a 
relie s et t. Si s et t sont reliés
par une arête, on dit qu'ils sont voisins ou adjacents.

Ainsi, les graphes sont non orientés et il n'y a pas d'arête reliant un sommet 
à lui-même. Par contre, à partir

de la partie V, il est possible que plusieurs arêtes aient les mêmes extrémités.

Par convention, nous noterons n (respectivement m) le nombre de sommets 
(respectivement d'arêtes) du graphe

et nous supposerons que S = {0,1,..,n--1}=S,.

Un graphe sera représenté par le type

type graphe = int list array

Si G est un graphe représenté par g, alors le nombre de sommets n du graphe est 
donné par la longueur du

tableau g. De plus, si s EUR S, alors g.(s) est une liste contenant les indices 
des sommets voisins de s, dans un

ordre quelconque, chaque sommet apparaissant autant de fois qu'il existe 
d'arêtes vers s.

Les complexités temporelles demandées sont des complexités dans le pire des cas 
et seront exprimées sous la
forme O(f(n,m)), où f est une fonction la plus simple possible.
Nous utiliserons la représentation graphique habituelle des graphes. Le graphe 
G, défini par l'instruction
let g = [l [l; (3; 41; (31; [1; 2; 4; 4]; [1; 3; 31 |];;
peut être représenté par le graphique de la figure 1.

Figure 1 Exemple de graphe

Pour p, q entiers naturels non nuls, nous noterons G,,, le graphe, appelé 
graphe quadrillage, dont les sommets
sont placés sur p colonnes et q lignes, chaque sommet étant relié à ses voisins 
directs. On convient de numéroter
les sommets de gauche à droite et de bas en haut.

Par ailleurs, l'ordre des arêtes ayant une importance en partie V, on convient 
de numéroter les p(q--1)+q(p--1)
arêtes en commençant par les arêtes verticales, de bas en haut et de gauche à 
droite, puis les arêtes horizontales,
de gauche à droite et de bas en haut, comme le montre la figure 2, où p = 4 et 
q = 3. Le rang d'une arête a de

Gp,g et l'indice à tel que a -- a;.

N006/2021-03-05 19:02:42 Page 1/9 CHELLES
di4 15 d16

,

ds

dj d12 di3

+
Q----g-

j

&

ao da

ag ag d10

D
Li. à

Figure 2 Le graphe G, 3

Soit G = ($S,, A) un graphe.

-- is EUR S,, le tableau d'adjacence de s est le tableau, dans un ordre 
quelconque, des voisins de s, chaque
sommet apparaissant autant de fois qu'il existe d'arêtes vers s. On note Adj le 
tableau de taille n tel que.
pour tout s EUR {0,1,..,n--1}, Adjls] est le tableau d'adjacence du sommet s. 
Adj est donc représenté par
une variable adj de type int array array.

-- Un chemin dans G est une suite EUR = (89,81,..., Si 18... Sp]; 5.) où pour 
tout j compris entre 1 et k, S_]

et s; sont des sommets voisins. On dira que c est un chemin de sç à s, de 
longueur k. Par convention, pour

s sommet de @, il existe un chemin de longueur nulle de s à 5.

-- La composante connexe d'un sommet s de @&, notée C",, est l'ensemble des 
sommets { de G tels qu'il existe
un chemin de s à t.

-- On dit que G est connexe si pour tous sommets s et t de G, il existe un 
chemin de s à £.

-- Un cycle dans G est un chemin de longueur k > 2 d'un sommet à lui-même et 
dont les arêtes sont deux à
deux distinctes. On dit que G est acyclique s'il ne contient aucun cycle.

-- Un arbre est un graphe connexe acyclique.

Ï Quelques fonctions auxiliaires

Q 1. Écrire une fonction
nombre_aretes : graphe -> int

qui, appliquée à g représentant un graphe G = (S, À), renvoie le cardinal de À.

Q 2. Écrire une commande Caml permettant de créer le tableau des tableaux 
d'adjacence Adj associé au
graphe G3 9.
On rappelle que la fonction Array.of_list : 'a list -> 'a array prend en 
argument uneliste [x,;x,;...; xx |

d'éléments de type 'a et renvoie le tableau [[x,:x%,;...:x7 |].
Q 3. Écrire une fonction

adjacence : graphe -> int array array
qui, appliquée à g représentant un graphe G, renvoie adj représentant le 
tableau des tableaux d'adjacence
Adj associé à G. La fonction adjacence devra être de complexité Om + n) et on 
demande de justifier cette
complexité.
Q 4. Écrire une fonction

rang : int * int -> int * int -> int
telle que rang (p, q) (s, t) renvoie le rang de l'arête {s,t} dans le graphe 
quadrillage G,,. Par exemple,
rang (4, 3) (6, 7) renvoie 13. On suppose que s et { sont adjacents et s < t et on ne demande pas de le vérifier. Q 5. Écrire de même sa fonction réciproque sommets : int * int -> int -> int * int
telle que sommets (p, q) i renvoie le couple (s, +) tel que a; = {s,t} et s < + dans le graphe G,,,. Q 6. Écrire une fonction quadrillage : int -> int -> graphe

telle que l'instruction quadrillage p q renvoie le graphe représentant G, ,:

N006/2021-03-05 19:02:42 Page 2/9 (cc) BY-NC-SA
II Caractérisation des arbres

Soit G = ($,,, À) un graphe à n sommets et m arêtes, représenté par g. Les 
arêtes de G& sont donc numérotées
A -- (ap; d;, cs Ayn_1)-

IT. À --- Propriétés sur les arbres
Q 7. Montrer que les composantes connexes de G forment une partition de 5,,, 
c'est-à-dire que :
-- VsES,, C0. 0:
-- S,= |] C,:
ses,

-- pour tous sommets s et #, soit C!, = C,, soit C, NC, = Ü.

Q 8. Montrer que si s et & sont deux sommets de G tels que t{ EUR C,, il existe 
un plus court chemin de s à t
et que les sommets d'un plus court chemin sont deux à deux distincts.

Pour k EUR {0,1,...,m}, G, désigne le graphe (5, , (ap, &,....., ax )) obtenu 
en ne conservant que les £ premières
arêtes de G.

Q 9. On suppose que G est un arbre. Montrer que pour tout k EUR {0,1,...,m -- 
1}, les extrémités de ay
appartiennent à deux composantes connexes différentes de G,. En déduire que 
m=n--1l.

Q 10. Montrer que les trois propriétés suivantes sont équivalentes :
(i) Gest un arbre;
(ii) Gest connexe et m--=n--1:
(ii) G est acyclique et m = n--1.

IT.B --- Manipulation de partitions

Nous souhaiïtons écrire une fonction qui teste si un graphe est un arbre. Nous 
allons pour cela utiliser une
structure de données permettant de manipuler les partitions de l'ensemble $,, : 
si P={X,,X,,..,X,} est une
partition de $,,, on choisit dans chaque partie X,, un élément particulier r,;, 
appelé représentant de X;. Notre
structure de données doit nous permettre :

-- de calculer, pour s EUR $,,, le représentant de la partie X; contenant s ; 
cet élément sera également appelé
représentant de s ;

-- pour deux entiers s et { représentant des parties distinctes X; et À, de 
transformer ? en réunissant X; et

X;, s ou t devenant le représentant de la partie À; U X..

Nous représenterons une partition P = {X,,..., X,} de S, par une forêt : chaque 
X,; est représenté par un arbre
dont les noeuds sont étiquetés par les éléments de X, et de racine le 
représentant r, de X,;, les arcs étant orientés
vers la racine. Nous noterons A(r;) la hauteur de l'arbre X;, c'est-à-dire la 
longueur de sa plus longue branche.
Ainsi, Po -- {{0,2},{1,5,6,8},{3,4,7}} est une partition de S, et peut par 
exemple être représentée par la
forêt de la figure 3.

h(O) = 1 h(6) = 2 h(7) =1

(8) | (De)

Figure 3 Une représentation de P, -- {{0,2},{1,5,6,8},{3,4,7}}

[I

Le calcul du représentant d'un entier s EUR S, se fait donc en remontant 
jusqu'à la racine de l'arbre (ce qui justifie
l'orientation des arcs). Dans l'exemple, les représentants de 2, 1 et 7 sont 
respectivement 0, 6 et 7.

Une partition P de $, -- {0,1,..,n -- 1} sera représentée par un tableau 
d'entiers P de taille n de sorte que
pour tout s EUR 40,1,..,n--1}, Pfs] est le père de s si s n'est pas un 
représentant, et est égal à --1 -- h(s) si s est
un représentant. La partition P, peut ainsi être représentée par le tableau

[| -2; 5: 0; 7; 7: 6; -3; -2; 6 |]
La réunion de deux parties X; et X; de représentants s et { distincts se fait 
selon la méthode suivante :
-- sih(s) > h(t), s est choisi pour représentant de la partie X; U X; et 
devient le père de t ;
-- sih(s) < h(t), t est choisi pour représentant de la partie X; U X, et devient le père de s. N006/2021-03-05 19:02:42 Page 3/9 (cc) BY-NC-SA Par exemple, la réunion des parties À, et X, de la partition ?, peut donner la nouvelle forêt représentée figure 4. h(6) = 2 h(7) = 2 O7} (4) (B)--"(6) _ Figure 4 Une représentation de {{0,2}U {3,4,7},{1,5,6,8}} Q 11. Écrire une fonction representant : int array -> int -> int
qui, appliquée à un tableau représentant une partition de $,, et à s EUR $,,, 
renvoie le représentant de s.
Q 12. Écrire une fonction
union : int array -> int -> int -> unit
qui, appliquée à un tableau représentant une partition de 5, et à deux 
représentants s et { distincts, modifie

la partition en réunissant les arbres associés à s et t, selon la méthode 
expliquée ci-dessus, sans oublier, si
nécessaire, de modifier h(s) ou h(t).

On note po la partition de $,, où toutes les parties sont des singletons, 
c'est-à-dire po) = {{0},{1},...{n--1}}.
Q 13. Soit P une partition de 5, construite à partir de po) par des réunions 
successives selon la méthode
précédente. Montrer que si s est le représentant d'une partie X EUR P, alors le 
cardinal de X vérifie [X| > 2h(s),
Q 14. En déduire les complexités des deux fonctions précédentes dans le pire 
des cas en fonction de n pour
une partition P construite à partir de PO.
Q 15. Écrire une fonction

est_un_arbre : graphe -> bool

qui, appliquée à un graphe g représentant un graphe G&, renvoie true si G est 
un arbre et false sinon.

IIT Algorithme de Wilson : arbre couvrant aléatoire

SiG = ($5,,, À) est un graphe connexe et sir EUR $,,, un arbre couvrant de G 
enraciné en r est un arbre TJ = ($,,,B)
tel que B EUR À et dont r a été choisi pour racine. On convient alors 
d'orienter les arêtes de l'arbre en direction
de la racine r et de représenter 7 par un tableau parent de taille n, 
parent.(s) étant égal au père de s dans
T'sisæ£r,etàa--1lsis=r.

La figure 5 représente deux arbres couvrants du graphe G:,, enracinés 
respectivement en 0 et 2, et leurs

représentations.
Qu)

r = 0 r = 2

[I -1; 0; 1; 0; 1; 4 |] [1 1; 2; -1; 0; 1; 2 1]
Figure 5 Deux arbres couvrants enracinés de G,2 et leurs représentations

Dans cette partie, nous supposons que G = (5,,,A) est un graphe connexe, 
représenté par g, que r est un
sommet de G et nous cherchons à construire un arbre couvrant aléatoire de G 
enraciné en r.

Nous allons pour cela faire évoluer dynamiquement un arbre 7, représenté par un 
tableau parent de longueur
n vérifiant :

-- parent.(r) = -1;
-- sis ES, n'est pas un sommet de J, parent.(s) = -2:

-- sis ES, est un sommet de 7 autre que la racine, parent.(s) est le père de s 
dans l'arbre J.

N006/2021-03-05 19:02:42 Page 4/9 (cc) BY-NC-SA
Nous partons de l'arbre réduit à la racine r, en posant parent.(r) = -1et 
parent.(s) = -2 pour tout sommet

s Æ r. Pour tout sommet s, quand s n'est pas déjà dans l'arbre, on construit un 
chemin aléatoire c sans boucle

qui part de s et qui s'arrête dès qu'il a atteint un sommet de 7. La méthode de 
construction est la suivante :

-- au début du calcul, c est réduit à s ;

-- à tout moment, c est de la forme (s = 54,81,-., 82 1,81) où les sommets 
5,,...,s, sont deux à deux distincts
et les sommets 8,,...,8, , ne sont pas des sommets de Y :

-- tant que l'extrémité s, n'est pas un sommet de 7, on choisit aléatoirement 
et uniformément un voisin u de
s, et on distingue,

e siu EUR {S9,81,...,8,}, On supprime le cycle qui vient d'être formé et u 
devient le nouveau point d'arrivée
du chemin c ;
e sinon, c devient le chemin (s = 8p,8,,,Sx 1,87, u):
-- on renvoie le chemin (s = 8,,8,,-.,8, ,,s,) une fois le calcul terminé.

On représentera un chemin en Caml par le type :
type chemin = {debut : int; mutable fin : int; suivant : int array}

de telle sorte que si le chemin EUR = (s,,5,,--, 82 ,8,) est représenté par c, 
alors c.debut est égal à s,, c.fin
(qui est un champ mutable) est égal à s,, et c.suivant est un tableau de taille 
n tel que pour j EUR {0,...,k--1},

la case d'indice s; de c.suivant contient le sommet s,,,. Pour tout autre 
sommet { EUR {S80,51,..., 8% 1},

c.suivant.(t) pourra prendre une valeur arbitraire.

On rappelle que si c est un objet de type chemin et u un entier représentant un 
sommet, la modification du
champ mutable c.fin pour y mettre u peut se faire avec la commande :

c.fin <- u Q 16. Déterminer, dans le graphe G3, le chemin représenté par l'objet {debut = 1; fin = 4; suivant = [|-5; 2; 5; 3; -1; 4|]} Q 17. Que peut-on dire de la terminaison de cet algorithme ? Q 18. Écrire une fonction marche_aleatoire : int array array -> int array -> int -> chemin

telle que l'appel marche _aleatoire adj parent s renvoie l'objet c représentant 
un chemin de s à un sommet
t E TJ obtenu comme décrit précédemment. On rappelle que adj représente le 
tableau des tableaux d'adjacence
Adj du graphe G, que parent représente l'arbre (en construction) 7 et on 
supposera que 8 EUR $,, n'appartient
pas à 7.

L'algorithme d'évolution de 7, appelé algorithme de Wilson, est alors le 
suivant : à partir de l'arbre 7 réduit à
r, pour s variant de 0 à n -- 1, si s n'est pas dans 7, on calcule un chemin de 
s à un sommet t{ EUR JT codé par c
grâce à la fonction marche _aleatoire et on greffe c à J, en ajoutant à J les 
arêtes du chemin c, orientées de
s vers u, üu étant le dernier sommet du chemin.
Q 19. Écrire une fonction

greffe : int array -> chemin -> unit
telle que l'instruction greffe parent c modifie parent de sorte à représenter 
l'arbre obtenu après la greffe du
chemin EUR sur 7.
Q 20. Écrire une fonction

Wilson : graphe -> int -> int array

tel que wilson g r renvoie un arbre couvrant aléatoire du graphe G de racine r.

IV Arbres couvrants et pavages par des dominos

Soient p et qg deux entiers strictement supérieurs à 1. Le but des deux 
dernières parties est de construire des
pavages aléatoires par des dominos de taille 2 X 1 d'un échiquier à 2p -- 1 
colonnes et 2q -- 1 lignes privé de son
coin inférieur gauche (il reste bien un nombre pair de cases à recouvrir). Nous 
noterons E,,, cet échiquier, dont
les cases sont repérées par des couples de coordonnées entières (x, y), avec 0 
< x < 2(p --1) et 0 < y < 2(q--1), et E,,, l'échiquier Æ,,, privé de son coin inférieur gauche, c'est-à-dire de la case (0,0). Les cases de E,,4 Sont colorées en noir, gris et blanc, comme dans l'exemple de l'échiquier E, , présenté figure 6. Les cases dont les deux coordonnées sont paires sont colorées en noir, celles dont les deux coordonnées sont impaires sont colorées en gris, les autres sont colorées en blanc. Si P est un pavage de E, a chaque case noire ou grise de E" est recouverte par un domino, qui est orienté, à partir de la case noire ou grise considérée, vers le sud, l'ouest, le nord ou l'est. N006/2021-03-05 19:02:42 Page 5/9 (cc) BY-NC-SA Figure 6 L'échiquier Ë, 3 Nous définissons le type type direction = S | WINIE et nous codons P par une matrice pavage de taille (2p -- 1) x (2q -- 1), avec, pour à EUR 4{0,..,2p -- 2} et jEUR {0,.,2q--1}: -- siiet j ont la même parité et si (à, j) Æ (0,0), p.(i).(j) est la direction du domino qui recouvre la case (à, j) (cette case est soit noire, soit grise) : -- sinon, pavage.(i).(j) prend la valeur N (ces valeurs ne jouent aucun rôle). Ainsi, si pi est la matrice associée au pavage P, de E, 3 représenté figure 7 (pour mieux distinguer les dominos, les cases ont été remplacées par des ronds colorés) on a par exemple p1.(2).(4) = S,p1.(4).(2) = W,p1.(3).(3) = N,pi.(5).(1) = E, comme indiqué par les sens des flèches. ( VY VV D e | © @ N Ne À À / ( Y Y NV à © @e - © @ W E K A À J f Y à ------+ S KL D -- KL A ) Figure 7 Le pavage P, de E7, Les cases noires de l'échiquier E,, seront vues comme les sommets du graphe G,,, (la case noire située en bas à gauche est identifiée au sommet 0 du graphe Ga): Un résultat de Neville Temperley explicite une bijection canonique & entre les pavages de E,,, et les arbres couvrants de G,,,. La construction de p(P) à partir d'un pavage P s'obtient en ne conservant que les dominos recouvrant une case noire. Pour toute la suite du sujet, les valeurs de p et q seront supposées contenues dans les variables globales p et q. On suppose de plus définie une variable globale g, représentant G,,, par l'instruction let g = quadrillage p q ;; IV.A -- Exemples Q 21. Dessiner l'arbre couvrant non enraciné T1 = Y(P;) de Gy3. Q 22. Considérons inversement l'arbre couvrant J, de G,3 décrit figure 8. Par un procédé réciproque à celui utilisé à la question précédente, dessiner le pavage P, = w71(T,) de F7, à. IV.B - Calcul de l'arbre couvrant associé à un pavage Q 23. Soit P un pavage de FE, x associé à l'arbre couvrant J = 4(P) de G,,,. Décrire un procédé permettant de calculer le père d'un sommet 5 EUR {1,...,pq--1} dans l'arbre Y enraciné en 0. On ne demande pas de démontrer que la structure ainsi obtenue est bien un arbre de racine (0. N006/2021-03-05 19:02:42 Page 6/9 (cc) BY-NC-SA Figure 8 L'arbre couvant J; Q 24. Écrire une fonction coord noire : int -> int * int
telle que l'instruction coord_ noire s renvoie le couple des coordonnées de la 
case correspondant au sommet s
du graphe G,,,. Par exemple, dans le graphe G, ; représenté figure 2, 
coord_noire 6 renverra (4, 2).
Q 25. Écrire une fonction
sommet direction : int -> direction -> int

telle que sommet direction s d renvoie le sommet { qui se trouve directement 
dans la direction d du sommet
s de G,,,. Cette fonction renverra -1 si un tel sommet n'existe pas. Par 
exemple, dans le graphe G, 4 représenté
figure 2, sommet _direction 5 W renverra 4.

Q 26. Écrire une fonction

phi : direction array array -> int array
qui, appliquée à une matrice pavage représentant un pavage P de E,, renvoie le 
tableau parent représentant
l'arbre T = G(P) enraciné en 0 (cette représentation est définie au début de la 
partie I).

V Utilisation du dual pour la construction d'un pavage

V.A --- Graphe dual de G,,,

Le graphe G,,, est un graphe planaire, c'est-à-dire qu'il possède une 
représentation graphique dans laquelle deux
arêtes distinctes ne se coupent pas, sauf peut-être en leurs extrémités. Cette 
représentation planaire sépare le
plan en (p -- 1)(q -- 1) +1 faces, que l'on va numéroter de gauche à droite et 
de bas en haut, la face non bornée
portant le numéro 0. Le graphe dual de G, ., noté (EUR est alors le graphe à (p 
-- 1)(q-- 1) +1 sommets (chaque

pq?
sommet correspond à une des faces délimitées par la présentation de G p.q) et 
qui possède autant d'arêtes que
GA: chaque arête a de G,,, donne une arête a" entre les deux faces du plan 
qu'elle sépare. Ce graphe est

également planaire. Attention, contrairement au graphe G@, le graphe G, , peut 
posséder plusieurs arêtes entre

P,4q?

les mêmes sommets. Les sommets de G,,, ont déjà été identifiés aux cases noires 
de ÆE,,, ; les cases grises seront

identifiées aux sommets de Cr distincts de 0 et les cases blanches aux arêtes 
de G,,, (et donc également aux
arêtes de Co puisque a + a* est une bijection). La figure 9 explicite ces 
identifications dans le cas du graphe
G13. Les sommets de G,, sont identifiés par des sommets gris foncés, ceux de G 
, par des sommets gris clairs,
les arêtes de G,,3 par des traits pleins et celles de G 1,3 Par des traits 
hachurés. L' intersection de chaque (a, a*)
est marquée par un carré symbolisant une case blanche de Es.

Ainsi, le sommet 6 de G,3 correspond à la case (4,2) de E, 2, le sommet 4 de 
Gi, correspond à la case (1,3)
et les arêtes a, de G,3 et aç de G4, correspondent à la case (3,0).

Dans la suite du problème, nous notons :

-- n = pq le nombre de sommets de G!,, ;

-- n° = (p--1)(g--1) +1 1e nombre de sommets de G7,, :
-- Mm=p(q--1)+4q(p-- 1) 1e nombre d'arêtes de G,,, et de G, a

-- À l'ensemble des arêtes de G,,, :

-- A* l'ensemble des arêtes de Ca d

Nous supposerons définies pour la suite :
-- une fonction coord_grise : int -> int * int qui, appliquée à un sommet de G, 
, autre que 0, renvoie
les coordonnées de la case grise qui correspond à ce sommet :

-- une fonction numero : int * int -> int qui, appliquée à un couple (x,y) 
représentant une case noire
ou grise de l'échiquier E,,,, renvoie le sommet du graphe G,,, ou G, associé à 
cette case. On supposera
également que dans tous les autres cas, numero renvoie la valeur 0, F compris 
si les coordonnées sont en
dehors de l'échiquier. Quand p = 4 et q = 3, nous avons par exemple : numero 
(4, 2) = 6, numero (1, 3)

= 4, et numero (3, 0) =

N006/2021-03-05 19:02:42 Page 7/9 (cc) BY-NC-SA
= ---------- ---- ---- -- -- ---- -- ---- ---- -- -- -- -- -- ---- -- ---- ---- 
-- -- -- -- -- -- ------ ---- ---- ------------ -- -- -- --

o

F---©--FH------

S
î
F

(ee)

= ------ -- -- -- +

T--@--+H--©--t
EUR o )
---F--6-----0--1----

-- ---- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- ------ -- -- --

[7 @.--

_

= ------ -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- ---------- -- -- --

Figure 9 Gyzs et Gi 3

Q 27. En utilisant les fonctions précédentes, écrire une fonction
dual : unit -> graphe
telle que l'instruction dual () renvoie le graphe représentant c, a On 
respectera la numérotation des sommets

de G, décrite ci-dessus (figure 9). Par ailleurs, les listes d'adjacence du 
graphe dual contiendront des sommets
en doublon s'il existe plusieurs arêtes entre des mêmes sommets.

On suppose désormais définie une variable globale g_etoile par l'instruction
let g_etoile = dual () ;;

V.B --- Dual d'un arbre couvrant
Q 28. Montrer que, quitte à renuméroter les sommets, le dual de G, a St le 
graphe G,, 4:

Soit B une partie de À. On note B* la partie de A* définie par
Vie {0,1,..,m--1}, ae < a, B. Q 29. Montrer que si le graphe ($,,, B) possède un cycle, le graphe ($,,., B*) n'est pas connexe. Q 30. En déduire que (S,, B) est un arbre couvrant de G,,, si et seulement si (5,,., B*) est un arbre couvrant de G* . pq SiT = (S,,B) est un arbre couvrant de G,,,, Pour construire l'arbre J*, nous utiliserons une représentation différente des arbres que celle introduite en partie IT: on pourra représenter un arbre couvrant 7 = ($S, B) enraciné en r par un couple (r, b) où b est un tableau de booléens de longueur m représentant B, c'est-à-dire tel que b.(i) prend la valeur true si et seulement si a, EUR B. nous noterons J* l'arbre couvrant (5,,., B*) de a La figure 10 représente les deux arbres couvrants du graphe G:;, présenté en figure 5, enracinés respectivement en 0 et 2, et leurs représentations par un couple. Te LOT T r = 0 Tr = 2 (O, [| true; true; false; true; true; false; true |]) (2, [| true; true; true; true; true; false; false |]) Figure 10 Deux arbres couvrants enracinés de G, , et leurs représentations Q 31. Écrire une fonction vers_couple : int array -> int * bool array

telle que l'instruction vers_couple parent, où parent est un tableau 
représentant un arbre enraciné de G,,,,
renvoie le couple (r, b) décrit ci-dessus.

N006/2021-03-05 19:02:42 Page 8/9 (cc) BY-NC-SA
Q 32.  Détailler en français un algorithme permettant de construire parent à 
partir du couple (r, B) et de la
représentation du graphe G&,, par listes d'adjacences. Cet algorithme est-il 
applicable à un arbre couvrant du
graphe G, , ? Justifier.
Q 33. Écrire une fonction

vers_parent : int * bool array -> int array

telle que l'instruction vers_parent (r, b), où b désigne un ensemble B tel que 
($,, B) est un arbre de G,,,
enraciné en r, renvoie le tableau parent représentant cet arbre.

Q 34. Déterminer les complexités de ces deux fonctions de conversion en 
fonction de n et m.

On supposera écrite une fonction vers_parent_ etoile : int * bool array -> int 
array, ayant un fonc-
tionnement similaire à vers_parent, qui prend en argument un couple (r, 
b_etoile) correspondant à un
arbre couvrant J* = ($5,,.,B*) de CG, et renvoie un tableau parent_etoile 
décrivant l'arbre en utilisant la
représentation décrite partie IIT.

Q 35. Écrire une fonction
arbre_dual : int array -> int array

qui, appliquée au tableau parent représentant un arbre couvrant J de G,,, 
enraciné en 0, renvoie le tableau
parent_etoile représentant l'arbre couvrant 7* de G, û enraciné en 0.

V.C - Calcul du pavage associé à un arbre couvrant
Soit J -- (5, B) un arbre couvrant de G,,.,.
Q 36. Décrire un procédé de construction, à partir des arbres T et T* enracinés 
en 0, du pavage P = o71(T)

de E". On expliquera en détail comment traiter les arêtes d'un sommet de G, q 
VETS le sommet 0. On justifiera
brièvement que l'on obtient bien un pavage.

Q 37. Écrire une fonction

pavage_aleatoire : unit -> direction array array
telle que l'instruction pavage_aleatoire () renvoie une matrice de taille (2p 
-- 1)(2q -- 1) représentant un
pavage aléatoire de E,,, par des dominos.

Q 38. Comment adapter cette méthode à la construction de pavages aléatoires 
d'un échiquier à 2p colonnes
et 2q -- 1 lignes (respectivement à 2p colonnes et 2q lignes) ?

ee eFINeee

N006/2021-03-05 19:02:42 Page 9/9 (cc) BY-NC-SA

Extrait du corrigé obtenu par reconnaissance optique des caractères



Centrale Informatique optionnelle MP 2021
Corrigé
Ce corrigé est proposé par Titouan Leclercq (ENS Lyon) ; il a été relu par 
Vincent
Puyhaubert (professeur en CPGE) et Benjamin Monmege (enseignant-chercheur à
l'université).

Ce sujet porte sur la génération aléatoire de pavages d'un échiquier par des 
dominos. L'énoncé utilise pour cela une bijection entre ces pavages et les 
arbres couvrants
d'un certain type de graphe. Les parties dépendent les unes des autres et le 
sujet est
de difficulté croissante.
· Dans la partie I, on introduit les fonctions de base qui servent à manipuler
et générer des graphes non orientés en forme de quadrillage. Elle comporte
quelques questions de réindexation sur lesquelles il convient d'être 
particulièrement vigilant.
· La partie suivante introduit la notion d'arbre couvrant d'un graphe non 
orienté.
Elle demande d'établir quelques résultats classiques qui caractérisent ces 
sousgraphes connexes et acycliques, et s'achève par la rédaction d'une fonction 
qui
permet de vérifier si un sous-graphe donné est un arbre.
On notera à cet effet plusieurs questions portant sur la structure de données
union-find qui permet de manipuler efficacement des partitions d'ensembles.
· La partie III étudie et implémente l'algorithme de Wilson, qui permet de 
générer
un arbre couvrant aléatoire d'un graphe quelconque. La structure utilisée pour
représenter les arbres couvrants sera conservée dans tout le reste du sujet.
· Dans la partie IV, on introduit la notion de pavage d'un échiquier par des
dominos rectangulaires. On s'intéresse uniquement au cas où l'échiquier est un
rectangle de dimensions impaires, privé de son coin inférieur gauche. L'énoncé
admet l'existence d'une bijection entre les pavages de ce dernier et les arbres
couvrants d'un graphe dont la forme est celle étudiée en première partie. À 
l'aide
d'une réprésentation simple d'un pavage en Caml, on construit une première
fonction bijective associant un arbre couvrant à un pavage.
· La dernière partie, longue et difficile, s'intéresse à la génération 
aléatoire d'un
pavage. On s'intéresse pour cela au problème réciproque de celui de la partie 
IV :
construire un pavage à partir d'un arbre couvrant, ce qui nécessite 
l'introduction
de la notion d'arbre dual des graphes de quadrillage. Cette dernière partie
s'achève sur un code de longueur assez considérable, qui combine les fonctions
des cinq parties pour aboutir à la génération aléatoire attendue.
Ce sujet est un très bon sujet de révision sur les graphes et sur les 
structures de
données, malgré quelques imprécisions, notamment une définition du dual d'un 
dual
peu claire à la question 28. Sur les 38 questions composant le sujet, 20 
demandent
d'écrire du code, de difficulté variable. Il est sans doute un peu long pour 
une épreuve
de quatre heures et nécessite de rester concentré jusqu'à la fin.

Indications
1 Utiliser une relation entre le nombre d'arêtes et les degrés des sommets d'un
graphe.
4 Différencier les cas d'une arête verticale et d'une arête horizontale, puis 
trouver
comment situer l'arête dans le graphe.
7 Pour montrer que deux parties sont égales ou disjointes, montrer une double
inclusion s'il y a un élément commun à deux parties.
8 Montrer l'existence d'un plus court chemin de s à t en considérant l'ensemble 
des
longueurs des chemins de s à t. Montrer ensuite qu'un chemin qui passe deux fois
par le même sommet peut être réduit.
9 Le caractère acyclique d'un graphe se traduit par le fait qu'un chemin au 
plus peut
relier deux sommets, ce qui signifie que sans une arête {x, y}, les deux sommets
x et y ne sont plus reliés dans G.
10 Montrer d'abord qu'ajouter une arête dans un graphe diminue le nombre de 
composantes connexes ou crée un cycle.
11 Un élément est un représentant quand sa case est négative, et un élément qui 
n'est
pas un représentant pointe dans le tableau parent soit vers un représentant, 
soit
vers un élément dont on peut chercher le représentant.
13 Raisonner en terme d'invariant de la partition ou par récurrence sur le 
nombre
de réunions effectuées pour construire la partition.
15 Utiliser la caractérisation de la question 10. Le test de connexité se fait 
à l'aide
de la structure de partition étudiée dans la partie.
20 Utiliser les fonctions précédentes pour générer un chemin aléatoire et le 
greffer
pour chaque sommet qui n'est pas dans l'arbre.
24 Utiliser une division euclidienne.
25 Faire un pattern matching sur les directions possibles.
26 Utiliser la fonction de la question précédente pour déterminer le parent de 
chaque
sommet autre que 0.
29 Par l'absurde, considérer un cycle de (Sn , B ) et distinguer les faces 
intérieures et
extérieures.
30 Réutiliser la caractérisation de la question 10, en remarquant que si B a n 
- 1
arêtes alors B a n - 1 arêtes. Utiliser enfin le résultat de la question 28 pour
passer de G à G.
31 Vérifier pour chaque arête si l'un des deux sommets est parent de l'autre.
32 Effectuer un parcours en profondeur en partant de la racine pour associer à 
chaque
sommet son parent.
35 Convertir l'arbre en son arbre dual en utilisant le tableau de booléens, 
grâce
aux fonctions vers_parent et vers_couple. Pour construire le dual, dans la
représentation par tableau, appliquer la définition.
36 Commencer par traiter les sommets noirs, puis les gris. Distinguer les 
sommets gris
au bord de l'échiquier et ceux dans les coins, en utilisant les directions 
indiquées
par les sommets noirs autour lorsqu'un sommet gris a comme père le sommet 0.

I. Quelques fonctions auxiliaires
1 Pour un sommet s, notons d(s) le degré de s, à savoir le nombre d'arêtes dont 
s
est une extrémité. Les graphes étant représentés par listes d'adjacence, la 
quantité
|A| peut se calculer à partir des degrés des sommets à l'aide de la formule 
suivante :
P
2|A| =
d(s)
sS

En effet, compter le degré des sommets pour tous les sommets revient à compter 
les
arêtes deux fois : {x, y} est comptée une fois lorsque x apparaît comme voisin 
de y,
et une seconde fois lorsque y apparaît comme voisin de x. Cette formule mène au
programme suivant :
let nombre_aretes g =
let n = Array.length g in
let k = ref 0 in
for i = 0 to n - 1 do
k := !k + List.length g.(i)
(*List.length g.(i) représente le degré de i dans g*)
done;
!k /2 ;;
2 Commençons par dessiner le graphe G3,2 :
3

4

5

0

1

2

On liste alors aisément les voisins de chaque sommet, d'où l'instruction 
suivante :
let g = [|[|1;3|];[|0;2;4|];[|1;5|];[|0;4|];[|1;3;5|];[|2;4|]|];;
3 Le programme consiste simplement à construire un tableau dans lequel chaque
liste du tableau donné en entrée est convertie en tableau :
let adjacence g =
let n = Array.length g in
let sortie = Array.make n [||] in
for i = 0 to n - 1 do
sortie.(i) <- Array.of_list g.(i) done; sortie;; Évaluons la complexité de cette fonction : · les fonctions Array.length et Array.make s'exécutent en temps constant ; · la boucle for contient n itérations, sa complexité est la somme des complexités des appels à Array.of_list ; · la fonction Array.of_list a une complexité linéaire en la taille de la liste. La complexité de la fonction adjacence est donc linéaire en la somme des tailles des listes de son graphe d'entrée, ce qui correspond à la somme des degrés des sommets, valant 2m. On en conclut que La complexité de la fonction adjacence est en O(n + m). 4 Pour déterminer le rang de {s, t}, on procède en plusieurs étapes : · On détermine en premier lieu si l'arête est verticale. Pour ce faire, on sait déjà que s et t sont adjacents, donc t - s vaut 1 ou p, et il suffit ainsi seulement de tester si leur différence vaut p. · Si l'arête est verticale, il suffit de compter les arêtes qui se situent à gauche ou en-dessous de l'arête donnée. Notons a (resp. b) le numéro de ligne (resp. de colonne) de s en partant du bas (resp. de la gauche). il y a b · (q - 1) arêtes à gauche de {s, t}, car il y a q - 1 arêtes par colonne ; il y a a arêtes en-dessous de {s, t}. L'arête est donc de rang a + (q - 1) · b. · De façon similaire, on calcule le rang d'une arête horizontale mais en comptant d'abord par ligne, puis par colonne. Il ne faut bien sûr pas oublier d'ajouter p · (q - 1) pour tenir compte de toutes les arêtes verticales comptées avant. Le code résultant de ce raisonnement est le suivant : let rang (p,q) (s,t) = let a, b = s / p, s mod p in if t-s=p then a + b * (q-1) else a * (p-1) + b + p * (q-1) ;; 5 Comme précédemment, pour déterminer les sommets correspondant au rang i, raisonnons par étapes : · Déterminons d'abord si l'arête cherchée est verticale ou horizontale : il suffit de regarder si son rang est plus ou moins grand que le nombre d'arêtes verticales du graphe, soit p · (q - 1). · Si l'arête est verticale, on sait qu'elle est précédée de i arêtes. Cherchons alors la valeur de l'indice de s, à laquelle on ajoutera p pour trouver la valeur de l'indice de t. En notant à nouveau a l'indice de ligne de s et b l'indice de colonne de s, on sait que s = a + b · p. Pour trouver a et b, on effectue la division euclidienne de i par q - 1 puisque la question précédente assure que i = a + b · (q - 1) avec 0 6 a < q. · Un raisonnement analogue, en enlevant p × (q - 1) au rang de l'arête, permet de trouver l'indice de l'extrémité gauche d'une arête horizontale (on ajoute alors 1 pour obtenir l'indice de l'extrémité droite). Ce code s'en déduit directement : let sommets (p,q) i = if i < p * (q-1) then let a, b = i mod (q-1), i / (q-1) in let s = a * p + b in s, s + p else let i' = i - p * (q-1) in let a, b = i' / (p-1), i' mod (p-1) in let s = a * p + b in s, s + 1 ;;