Corrigé CCINP 2025 Informatique MP — Partie III (2) (Q18 à Q25) : Algorithme de Borůvka

Sujet officiel du concours CCINP, session 2025, épreuve Informatique MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

$G = (S, A, p)$ est connexe, de pondération injective, et $T^{*} = (S, A^{*})$ est son unique arbre couvrant de poids maximal (partie II). Soient $H = (S, B)$ un sous-graphe acyclique de $G$ et $C$ une composante connexe de $H$ . Une arête est sûre pour $C$ si elle a exactement une extrémité dans $C$ et un poids maximal parmi les arêtes de $A$ ayant exactement une extrémité dans $C$ . Si $H$ n'est pas connexe, chaque composante a exactement une arête sûre, et une même arête peut être sûre pour deux composantes.

Figure 4 du sujet : un sous-graphe $H$ à quatre composantes (arêtes de $H$ en trait plein, autres arêtes de $G$ en pointillés). Pour ${1, 4, 5, 6}$ , les arêtes sortantes ont pour poids $4, 7, 17, 21, 22$ : l'arête de poids $22$ est sûre, et elle l'est aussi pour ${0, 2}$ .

Q18. Donner l'arête sûre de ${3}$ et celle de ${7, 8}$ .
Q19. Si $B \subseteq A^{*}$ , montrer que $A^{*}$ contient les arêtes sûres de toutes les composantes de $H$ .

Algorithme 1 (Borůvka) : partir de $H = (S, \emptyset)$ ; tant que $H$ n'est pas connexe, ajouter à $H$ toutes les arêtes sûres de ses composantes. On renvoie $H$ .

Q20. Dérouler l'algorithme 1 sur le graphe $G$ de la figure 2 (toutes les arêtes de la figure 4) : à chaque étape, l'arête sûre de chaque composante et l'ensemble des arêtes ajoutées.
Q21. Montrer que l'algorithme termine.
Q22. Montrer qu'il renvoie $T^{*}$ .

Le sujet donne (avec les fonctions de Q10 à Q17), pour h acyclique non connexe :


let aretes_sures g h =
  let c = composantes_connexes h in
  let p = max_tab c + 1 in
  let aretes = toutes_les_aretes g in
  let sures = Array.make p (min_arete aretes) in
  let traite a =
    let (_, i, j) = a in
    if c.(i) <> c.(j) then begin
      sures.(c.(i)) <- max a sures.(c.(i));
      sures.(c.(j)) <- max a sures.(c.(j));
    end
  in
  List.iter traite aretes;
  sures

Q23. Type de cette fonction ; ce qu'elle calcule (structure et contenu du résultat) ; complexité en fonction de $∣ A ∣$ , sachant que $∣ S ∣ - 1 ⩽ ∣ A ∣$ .

On dispose de ajoute_aretes_sures : graphe -> (float * int * int) array -> unit, en $O (∣ A ∣)$ , qui ajoute à h les arêtes du tableau renvoyé par aretes_sures g h, chacune une seule fois.

Q24. Écrire borukva : graphe -> graphe, qui renvoie l'arbre couvrant de poids maximal.
Q25. (a) Montrer qu'à chaque tour de boucle le nombre de composantes de $H$ est au moins divisé par $2$ . (b) En déduire la complexité dans le pire cas. (c) Quelle est la complexité dans le meilleur cas ?

Corrigé

Q18. Composante ${3}$ : les arêtes issues de $3$ ont pour poids $11$ (vers $8$ ), $9$ (vers $2$ ) et $17$ (vers $1$ ). L'arête sûre est ${1, 3}$ , de poids $17$ .

Composante ${7, 8}$ : l'arête ${7, 8}$ (poids $19$ ) a ses deux extrémités dans la composante, elle ne compte pas. Les arêtes sortantes sont ${0, 7}$ ( $18$ ), ${0, 8}$ ( $6$ ), ${2, 8}$ ( $16$ ) et ${3, 8}$ ( $11$ ) : l'arête sûre est ${0, 7}$ , de poids $18$ (et non l'arête de poids $19$ , confusion signalée par le jury).

Q19. Soit $C$ une composante de $H$ (avec $C \neq = S$ , sinon il n'y a pas d'arête sûre) et $a = {u, v}$ son arête sûre, avec $u \in C$ , $v \in / C$ . Elle existe : $G$ étant connexe, un chemin de $G$ relie un sommet de $C$ à un sommet hors de $C$ , et l'une de ses arêtes a exactement une extrémité dans $C$ . Supposons par l'absurde $a \in / A^{*}$ .

D'après Q7(a), $T^{*} + a$ possède un cycle, qui contient $a$ (l'arbre $T^{*}$ n'a pas de cycle). Écrivons-le $u = x_{0}, x_{1} = v, x_{2}, \dots, x_{n} = u$ : le chemin $x_{1} x_{2} \dots x_{n}$ va de $v \in / C$ à $u \in C$ et n'emprunte que des arêtes du cycle autres que $a$ , donc des arêtes de $A^{*}$ . Soit $i$ le premier indice tel que $x_{i + 1} \in C$ (on a $i ⩾ 1$ car $x_{1} \in / C$ ) : l'arête $a^{'} = {x_{i}, x_{i + 1}}$ a exactement une extrémité dans $C$ , appartient à $A^{*}$ et au cycle, et $a^{'} \neq = a$ . Comme $a$ est sûre et $p$ injective, $p (a^{'}) < p (a)$ .

D'après Q7(b), $T^{*} + a - a^{'}$ est un arbre couvrant de $G$ , de poids $p (T^{*}) + p (a) - p (a^{'}) > p (T^{*})$ : c'est absurde. Donc $a \in A^{*}$ , et ce pour chaque composante de $H$ . L'argument d'échange n'a utilisé de $C$ que le fait d'être un ensemble de sommets distinct de $S$ (c'est la « propriété de coupure » des arbres couvrants) ; l'hypothèse $B \subseteq A^{*}$ est celle dont on disposera en Q22.

Q20. Les poids désignent les arêtes (ils sont distincts).

Étape 1. $H$ n'a aucune arête : neuf composantes, réduites à un sommet. L'arête sûre de chaque sommet est son arête de poids maximal :

${0}$ : $24$ ( ${0, 2}$ ) ; ${1}$ : $17$ ( ${1, 3}$ ) ; ${2}$ : $24$ ; ${3}$ : $17$ ; ${4}$ : $23$ ( ${4, 5}$ ) ;
${5}$ : $23$ ; ${6}$ : $22$ ( ${2, 6}$ ) ; ${7}$ : $19$ ( ${7, 8}$ ) ; ${8}$ : $19$ .

Arêtes ajoutées : ${24, 17, 23, 22, 19}$ . Composantes : ${0, 2, 6}$ , ${1, 3}$ , ${4, 5}$ , ${7, 8}$ .

Étape 2.

${0, 2, 6}$ : arêtes sortantes $18, 6, 4, 9, 7, 16, 8, 5$ ; arête sûre $18$ ( ${0, 7}$ ) ;
${1, 3}$ : sortantes $4, 13, 12, 9, 11$ ; arête sûre $13$ ( ${1, 4}$ ) ;
${4, 5}$ : sortantes $13, 7, 8, 12, 5$ ; arête sûre $13$ ;
${7, 8}$ : sortantes $18, 6, 16, 11$ ; arête sûre $18$ .

Arêtes ajoutées : ${18, 13}$ . Composantes : ${0, 2, 6, 7, 8}$ et ${1, 3, 4, 5}$ .

Étape 3. Les arêtes entre les deux composantes ont pour poids $4, 9, 7, 11, 8, 5$ : l'arête $11$ ( ${3, 8}$ ) est sûre pour les deux. On l'ajoute ; $H$ est connexe et l'algorithme s'arrête.

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →