Version interactive avec LaTeX compilé

Centrale Option Informatique MP 2021

Notez ce sujet en cliquant sur l'étoile

0.0(0 votes)

🔗 Explorer

Centrale MP Centrale 2021 MP Info Info 2021

2025_08_29_91a6940d27a9d1cfd244g

Option informatique

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

(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é

. Plus généralement, les objets mathématiques seront notés

et représentés en Caml par g, s, adj... sans que cela soit systématiquement explicité.

Dans ce problème, un graphe

est un couple (

) où :

est un ensemble fini dont les éléments sont les sommets de ;
est la suite des arêtes de , une arête étant une partie de de cardinal 2 . Les sommets et sont appelés les extrémités de l'arête et on dira que a relie et . Si et 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 (respectivement ) le nombre de sommets (respectivement d'arêtes) du graphe et nous supposerons que .
Un graphe sera représenté par le type
type graphe = int list array
Si est un graphe représenté par , alors le nombre de sommets du graphe est donné par la longueur du tableau g. De plus, si , alors g. (s) est une liste contenant les indices des sommets voisins de , dans un ordre quelconque, chaque sommet apparaissant autant de fois qu'il existe d'arêtes vers .

Les complexités temporelles demandées sont des complexités dans le pire des cas et seront exprimées sous la forme

, où

est une fonction la plus simple possible.

Nous utiliserons la représentation graphique habituelle des graphes. Le graphe

, défini par l'instruction
let

;
peut être représenté par le graphique de la figure 1.

Figure 1 Exemple de graphe

Pour

entiers naturels non nuls, nous noterons

le graphe, appelé graphe quadrillage, dont les sommets sont placés sur

colonnes et

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

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ù

. Le rang d'une arête a de

est l'indice

tel que

Figure 2 Le graphe

Soit

un graphe.

Si , le tableau d'adjacence de est le tableau, dans un ordre quelconque, des voisins de , chaque sommet apparaissant autant de fois qu'il existe d'arêtes vers . On note le tableau de taille tel que, pour tout est le tableau d'adjacence du sommet . Adj est donc représenté par une variable adj de type int array array.
Un chemin dans est une suite où pour tout compris entre 1 et et sont des sommets voisins. On dira que est un chemin de à de longueur . Par convention, pour sommet de , il existe un chemin de longueur nulle de à .
La composante connexe d'un sommet de , notée , est l'ensemble des sommets de tels qu'il existe un chemin de à .
On dit que est connexe si pour tous sommets et de , il existe un chemin de à .
Un cycle dans est un chemin de longueur d'un sommet à lui-même et dont les arêtes sont deux à deux distinctes. On dit que est acyclique s'il ne contient aucun cycle.
Un arbre est un graphe connexe acyclique.

I Quelques fonctions auxiliaires

Q 1. Écrire une fonction
nombre_aretes : graphe -> int
qui, appliquée à g représentant un graphe

, renvoie le cardinal de

.
Q 2. Écrire une commande Caml permettant de créer le tableau des tableaux d'adjacence Adj associé au graphe

.
On rappelle que la fonction Array.of_list : 'a list

'a array prend en argument une liste

d'éléments de type 'a et renvoie le tableau

.
Q 3. Écrire une fonction
adjacence : graphe -> int array array
qui, appliquée à g représentant un graphe

, renvoie adj représentant le tableau des tableaux d'adjacence Adj associé à

. La fonction adjacence devra être de complexité

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

dans le graphe quadrillage

. Par exemple, rang

renvoie 13 . On suppose que

sont adjacents et

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 (

) i renvoie le couple (

) tel que

dans le graphe

.
Q 6. Écrire une fonction
quadrillage : int -> int -> graphe
telle que l'instruction quadrillage p q renvoie le graphe représentant

II Caractérisation des arbres

Soit

un graphe à

sommets et

arêtes, représenté par g. Les arêtes de

sont donc numérotées

II.A - Propriétés sur les arbres

Q 7. Montrer que les composantes connexes de

forment une partition de

, c'est-à-dire que:

;

;
pour tous sommets et , soit , soit .

Q 8. Montrer que si

sont deux sommets de

tels que

, il existe un plus court chemin de

et que les sommets d'un plus court chemin sont deux à deux distincts.
Pour

désigne le graphe (

) obtenu en ne conservant que les

premières arêtes de

.
Q 9. On suppose que

est un arbre. Montrer que pour tout

, les extrémités de

appartiennent à deux composantes connexes différentes de

. En déduire que

.
Q 10. Montrer que les trois propriétés suivantes sont équivalentes:
(i)

est un arbre ;
(ii)

est connexe et

;
(iii)

est acyclique et

II.B - Manipulation de partitions

Nous souhaitons é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

est une partition de

, on choisit dans chaque partie

, un élément particulier

, appelé représentant de

. Notre structure de données doit nous permettre :

de calculer, pour , le représentant de la partie contenant ; cet élément sera également appelé représentant de ;
pour deux entiers et représentant des parties distinctes et , de transformer en réunissant et ou devenant le représentant de la partie .
Nous représenterons une partition de par une forêt: chaque est représenté par un arbre dont les noeuds sont étiquetés par les éléments de et de racine le représentant de , les arcs étant orientés vers la racine. Nous noterons la hauteur de l'arbre , c'est-à-dire la longueur de sa plus longue branche. Ainsi, est une partition de et peut par exemple être représentée par la forêt de la figure 3.

Figure 3 Une représentation de

Le calcul du représentant d'un entier

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

sera représentée par un tableau d'entiers

de taille

de sorte que pour tout

est le père de

n'est pas un représentant, et est égal à

est un représentant. La partition

peut ainsi être représentée par le tableau
[I -2; 5; 0; 7; 7; 6; -3; -2; 6 I]

La réunion de deux parties

de représentants

distincts se fait selon la méthode suivante :

si est choisi pour représentant de la partie et devient le père de ;
si est choisi pour représentant de la partie et devient le père de .

Par exemple, la réunion des parties

de la partition

peut donner la nouvelle forêt représentée figure 4.

Figure 4 Une représentation de

Q 11. Écrire une fonction

representant : int array -> int -> int

qui, appliquée à un tableau représentant une partition de

et à

, renvoie le représentant de

.
Q 12. Écrire une fonction

union : int array -> int -> int -> unit

qui, appliquée à un tableau représentant une partition de

et à deux représentants

distincts, modifie la partition en réunissant les arbres associés à

, selon la méthode expliquée ci-dessus, sans oublier, si nécessaire, de modifier

.
On note

la partition de

où toutes les parties sont des singletons, c'est-à-dire

.
Q 13. Soit

une partition de

construite à partir de

par des réunions successives selon la méthode précédente. Montrer que si

est le représentant d'une partie

, alors le cardinal de

vérifie

.
Q 14. En déduire les complexités des deux fonctions précédentes dans le pire des cas en fonction de

pour une partition

construite à partir de

.
Q 15. Écrire une fonction
est_un_arbre : graphe -> bool
qui, appliquée à un graphe g représentant un graphe

, renvoie true si

est un arbre et false sinon.

III Algorithme de Wilson : arbre couvrant aléatoire

est un graphe connexe et si

, un arbre couvrant de

enraciné en

est un arbre

tel que

et dont

a été choisi pour racine. On convient alors d'orienter les arêtes de l'arbre en direction de la racine

et de représenter

par un tableau parent de taille

, parent. (s) étant égal au père de

dans

, et à -1 si

.
La figure 5 représente deux arbres couvrants du graphe

, enracinés respectivement en 0 et 2 , et leurs représentations.

Figure 5 Deux arbres couvrants enracinés de

et leurs représentations

Dans cette partie, nous supposons que

est un graphe connexe, représenté par g, que

est un sommet de

et nous cherchons à construire un arbre couvrant aléatoire de

enraciné en

.
Nous allons pour cela faire évoluer dynamiquement un arbre

, représenté par un tableau parent de longueur

vérifiant:

parent. (r) = -1;
si n'est pas un sommet de , parent. (s) = -2;
si est un sommet de autre que la racine, parent. (s) est le père de dans l'arbre .

Nous partons de l'arbre réduit à la racine

, en posant parent.

et parent.

pour tout sommet

. Pour tout sommet

, quand

n'est pas déjà dans l'arbre, on construit un chemin aléatoire

sans boucle qui part de

et qui s'arrête dès qu'il a atteint un sommet de

. La méthode de construction est la suivante:

au début du calcul, est réduit à ;
à tout moment, est de la forme ( ) où les sommets sont deux à deux distincts et les sommets ne sont pas des sommets de ;
tant que l'extrémité n'est pas un sommet de , on choisit aléatoirement et uniformément un voisin de et on distingue,
si , on supprime le cycle qui vient d'être formé et devient le nouveau point d'arrivée du chemin ;
sinon, devient le chemin ;
on renvoie le chemin ( ) 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

est représenté par c , alors c .debut est égal à

, c.fin (qui est un champ mutable) est égal à

, et c. suivant est un tableau de taille

tel que pour

, la case d'indice

de c.suivant contient le sommet

. Pour tout autre sommet

, 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

, 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

à un sommet

obtenu comme décrit précédemment. On rappelle que adj représente le tableau des tableaux d'adjacence Adj du graphe

, que parent représente l'arbre (en construction)

et on supposera que

n'appartient pas à

L'algorithme d'évolution de

, appelé algorithme de Wilson, est alors le suivant : à partir de l'arbre

réduit à

, pour

variant de 0 à

, si

n'est pas dans

, on calcule un chemin de

à un sommet

codé par c grâce à la fonction marche_aleatoire et on greffe

, en ajoutant à

les arêtes du chemin

, orientées de

vers

é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

sur

.
Q 20. Écrire une fonction
wilson : graphe -> int -> int array
tel que wilson gr renvoie un arbre couvrant aléatoire du graphe

de racine

IV Arbres couvrants et pavages par des dominos

Soient

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

d'un échiquier à

colonnes et

lignes privé de son coin inférieur gauche (il reste bien un nombre pair de cases à recouvrir). Nous noterons

cet échiquier, dont les cases sont repérées par des couples de coordonnées entières (

), avec

, et

l'échiquier

privé de son coin inférieur gauche, c'est-à-dire de la case ( 0,0 ). Les cases de

sont colorées en noir, gris et blanc, comme dans l'exemple de l'échiquier

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

est un pavage de

, chaque case noire ou grise de

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.

Figure 6 L'échiquier

Nous définissons le type
type direction

S | W | N | E
et nous codons

par une matrice pavage de taille

, avec, pour

si et ont la même parité et si , p. (i). (j) est la direction du domino qui recouvre la case (cette case est soit noire, soit grise) ;
sinon, pavage. (i). (j) prend la valeur (ces valeurs ne jouent aucun rôle).

Ainsi, si p1 est la matrice associée au pavage

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)

, comme indiqué par les sens des flèches.

Figure 7 Le pavage

Les cases noires de l'échiquier

seront vues comme les sommets du graphe

(la case noire située en bas à gauche est identifiée au sommet 0 du graphe

). Un résultat de Neville Temperley explicite une bijection canonique

entre les pavages de

et les arbres couvrants de

. La construction de

à partir d'un pavage

s'obtient en ne conservant que les dominos recouvrant une case noire.
Pour toute la suite du sujet, les valeurs de

seront supposées contenues dans les variables globales p et q . On suppose de plus définie une variable globale g , représentant

, par l'instruction
let

quadrillage p q ;;

IV.A - Exemples

Q 21. Dessiner l'arbre couvrant non enraciné

.
Q 22. Considérons inversement l'arbre couvrant

décrit figure 8. Par un procédé réciproque à celui utilisé à la question précédente, dessiner le pavage

IV.B - Calcul de l'arbre couvrant associé à un pavage

Q 23. Soit

un pavage de

, associé à l'arbre couvrant

. Décrire un procédé permettant de calculer le père d'un sommet

dans l'arbre

enraciné en 0 . On ne demande pas de démontrer que la structure ainsi obtenue est bien un arbre de racine 0 .

Figure 8 L'arbre couvant

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

du graphe

. Par exemple, dans le graphe

représenté figure 2 , coord_noire 6 renverra ( 4,2 ).
Q 25. Écrire une fonction

sommet_direction : int -> direction -> int

telle que sommet_direction

d renvoie le sommet

qui se trouve directement dans la direction d du sommet

. Cette fonction renverra -1 si un tel sommet n'existe pas. Par exemple, dans le graphe

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

, renvoie le tableau parent représentant l'arbre

enraciné en 0 (cette représentation est définie au début de la partie III).

V Utilisation du dual pour la construction d'un pavage

Graphe dual de

Le graphe

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

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

, noté

, est alors le graphe à

sommets (chaque sommet correspond à une des faces délimitées par la représentation de

) et qui possède autant d'arêtes que

: chaque arête

donne une arête

entre les deux faces du plan qu'elle sépare. Ce graphe est également planaire. Attention, contrairement au graphe

, le graphe

peut posséder plusieurs arêtes entre les mêmes sommets. Les sommets de

ont déjà été identifiés aux cases noires de

; les cases grises seront identifiées aux sommets de

distincts de 0 et les cases blanches aux arêtes de

(et donc également aux arêtes de

, puisque

est une bijection). La figure 9 explicite ces identifications dans le cas du graphe

. Les sommets de

sont identifiés par des sommets gris foncés, ceux de

par des sommets gris clairs, les arêtes de

par des traits pleins et celles de

par des traits hachurés. L'intersection de chaque (

) est marquée par un carré symbolisant une case blanche de

.
Ainsi, le sommet 6 de

correspond à la case ( 4,2 ) de

, le sommet 4 de

correspond à la case ( 1,3 ) et les arêtes

correspondent à la case ( 3,0 ).
Dans la suite du problème, nous notons :

le nombre de sommets de ;
le nombre de sommets de ;
le nombre d'arêtes de et de ;
l'ensemble des arêtes de ;
l'ensemble des arêtes de .

Nous supposerons définies pour la suite :

une fonction coord_grise : int -> int * int qui, appliquée à un sommet de 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 ( ) représentant une case noire ou grise de l'échiquier , renvoie le sommet du graphe ou associé à cette case. On supposera également que dans tous les autres cas, numero renvoie la valeur 0 , y compris si les coordonnées sont en dehors de l'échiquier. Quand et , nous avons par exemple : numero , numero , et numero .

Figure

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

. On respectera la numérotation des sommets de

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

est le graphe

.
Soit

une partie de

. On note

la partie de

définie par

Q 29. Montrer que si le graphe (

) possède un cycle, le graphe (

) n'est pas connexe.
Q 30. En déduire que (

) est un arbre couvrant de

si et seulement si (

) est un arbre couvrant de

.
Si

est un arbre couvrant de

, nous noterons

l'arbre couvrant (

) de

.
Pour construire l'arbre

, nous utiliserons une représentation différente des arbres que celle introduite en partie III : on pourra représenter un arbre couvrant

enraciné en

par un couple ( r , b) où b est un tableau de booléens de longueur

représentant

, c'est-à-dire tel que b. (i) prend la valeur true si et seulement si

.
La figure 10 représente les deux arbres couvrants du graphe

, présenté en figure 5 , enracinés respectivement en 0 et 2 , et leurs représentations par un couple.

Figure 10 Deux arbres couvrants enracinés de

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

, renvoie le couple (

, b) décrit ci-dessus.

Q 32. Détailler en français un algorithme permettant de construire parent à partir du couple (

) et de la représentation du graphe

par listes d'adjacences. Cet algorithme est-il applicable à un arbre couvrant du graphe

? Justifier.
Q 33. Écrire une fonction
vers_parent : int * bool array -> int array
telle que l'instruction vers_parent (

), où b désigne un ensemble

tel que (

) est un arbre de

enraciné en

, renvoie le tableau parent représentant cet arbre.
Q 34. Déterminer les complexités de ces deux fonctions de conversion en fonction de

.
On supposera écrite une fonction vers_parent_etoile : int * bool array -> int array, ayant un fonctionnement similaire à vers_parent, qui prend en argument un couple (r, b_etoile) correspondant à un arbre couvrant

et renvoie un tableau parent_etoile décrivant l'arbre en utilisant la représentation décrite partie III.
Q 35. Écrire une fonction
arbre_dual : int array -> int array
qui, appliquée au tableau parent représentant un arbre couvrant

enraciné en 0 , renvoie le tableau parent_etoile représentant l'arbre couvrant

enraciné en 0 .
V.C - Calcul du pavage associé à un arbre couvrant

Soit

un arbre couvrant de

.
Q 36. Décrire un procédé de construction, à partir des arbres

enracinés en 0 , du pavage

. On expliquera en détail comment traiter les arêtes d'un sommet de

vers 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 (

)(

) représentant un pavage aléatoire de

par des dominos.
Q 38. Comment adapter cette méthode à la construction de pavages aléatoires d'un échiquier à

colonnes et

lignes (respectivement à

colonnes et

lignes) ?