Centrale Informatique optionnelle MP 2021

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