Corrigé CCINP 2026 Informatique PC-PSI — Partie IV (Q23 à Q33) : Filaments galactiques : arbre couvrant minimal (Prim), élagage, séparation

Un arbre couvrant de poids minimal d'un graphe connexe pondéré à $N$ sommets garde $N-1$ arêtes, reste connexe et minimise la somme des poids. Algorithme glouton : partir d'un sommet, puis ajouter tant qu'il en reste le sommet relié à l'arbre par l'arête de poids minimal.

Graphe-jouet du document réponse.

Q23. Partant de D : ordre d'ajout, arbre, poids total.
Q24. Même chose en partant de F ; commenter.

coords : liste des triplets $(x_i,y_i,z_i)$ de $N$ galaxies ; le graphe complet relie $i$ et $j$ avec le poids $p_{ij}=(x_i-x_j{)}^2+(y_i-y_j{)}^2+(z_i-z_j{)}^2$.

Q25. Écrire poids(coords, i, j) (exemple : poids([(0,1,5), (-1,2,-4), (3,2,5)], 0, 2) vaut $10$).
Q26. Écrire matrice_adjacence(coords) (liste de listes, $m_{ij}=p_{ij}$).

Algorithme de Prim : arbre_couvrant_minimal(G, depart) initialise dist = initialisation_distance(G, depart) et pred = \{\}, puis, tant que dist est non vide, fait x = recherche_distance_minimale(dist) et mise_a_jour(dist, pred, x, G) ; elle renvoie pred (galaxie $\mapsto$ prédécesseur ; dist : galaxie hors de l'arbre $\mapsto$ distance à l'arbre). mise_a_jour : pour tout y clé de dist avec dist[y] > G[x][y], fait dist[y] = G[x][y] et pred[y] = x.

Q27. Écrire initialisation_distance(G, depart) : tout à float('inf') sauf depart à $0$.
Q28. Compléter recherche_distance_minimale(dist) (DR) : retire de dist la galaxie la plus proche et la renvoie.
Q29. Prouver la terminaison de arbre_couvrant_minimal par un variant.
Q30. Complexité au pire en fonction de $N$, fonction par fonction.

L'arbre pred est un dictionnaire galaxie $\mapsto$ prédécesseur ; les successeurs de x sont les y tels que arbre[y] == x.

Q31. Écrire dico_galaxies_avec_successeurs(arbre) : galaxie $\mapsto$ nombre de successeurs, pour les galaxies qui en ont (racine comprise), en $O(n)$.
Q32. Décrire elagage(arbre, nb_etapes) (code page 14 du sujet) et son intérêt (figure 5).
Q33. Écrire separation(G, arbre, alpha) : nouvel arbre sans les sommets dont la distance au prédécesseur dépasse $\alpha {\ell }_m$ (${\ell }_m$ : longueur moyenne des liaisons de l'arbre).

Figure 5 (schéma) — (a) arbre couvrant : deux amas (cercles, buissons de petites branches) reliés par un filament, et un amas isolé relié par une longue arête ; (b) après élagage.