Corrigé CCINP 2025 Informatique MP — Partie IV (Q26 à Q28) : Chemin de bande passante maximale

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

Énoncé

$G = (S, A, p)$ est un graphe pondéré, de pondération injective, pas nécessairement connexe. La bande passante d'un chemin $c = x_{0} x_{1} \dots x_{n}$ est le plus petit poids de ses arêtes :

$b (c) = 0 ⩽ i ⩽ n - 1 min p ({x_{i}, x_{i + 1}}),$

avec $b (c) = + \infty$ pour un chemin de longueur nulle. Pour $x, y \in S$ , on pose

$b_{m a x} (x, y) = max {b (c) ∣ c chemin de x a ˋ y},$

qui vaut $- \infty$ si aucun chemin ne relie $x$ à $y$ ; un chemin qui atteint ce maximum est un chemin de bande passante maximale. La bande passante limite de $G$ est

$b_{lim} (G) = min {b_{m a x} (x, y) ∣ x, y \in S} .$

Rappel de la figure 2 (sommet $0$ : Lurenberg, sommet $1$ : Veroja) :

Q26. Donner un chemin de bande passante maximale de Lurenberg ( $0$ ) à Veroja ( $1$ ) et sa bande passante.

On admet que, dans un arbre, deux sommets sont reliés par un unique chemin élémentaire.

Q27. Pour $x, y \in S$ , montrer que l'unique chemin élémentaire de $x$ à $y$ dans l'arbre couvrant de poids maximal $T^{*}$ est un chemin de bande passante maximale.
Q28. Justifier que $b_{lim} (G) = - \infty$ si $G$ n'est pas connexe, et $b_{lim} (G) = min {p (a) ∣ a \in A^{*}}$ sinon, où $T^{*} = (S, A^{*})$ .

Corrigé

Q26. Le chemin $0 \to 7 \to 8 \to 3 \to 1$ (Lurenberg, Atlanitkischer, Gasparländ, Stratord, Veroja) emprunte des arêtes de poids $18, 19, 11, 17$ : sa bande passante est $11$ . C'est le chemin de l'arbre $T^{*}$ obtenu en Q20, comme l'annonce Q27.

Il est optimal. Posons $U = {0, 2, 6, 7, 8}$ : tout chemin de $0 \in U$ à $1 \in / U$ emprunte au moins une arête ayant une extrémité dans $U$ et l'autre hors de $U$ . Ces arêtes sont ${1, 2}$ ( $4$ ), ${2, 3}$ ( $9$ ), ${2, 4}$ ( $7$ ), ${3, 8}$ ( $11$ ), ${4, 6}$ ( $8$ ) et ${5, 6}$ ( $5$ ), toutes de poids au plus $11$ : tout chemin de $0$ à $1$ a une bande passante au plus égale à $11$ . Donc $b_{m a x} (0, 1) = 11$ . Les chemins $02831$ et $062831$ conviennent aussi (une énumération des 61 chemins élémentaires de $0$ à $1$ n'en trouve pas d'autre de bande passante $11$ ). En revanche, le chemin $0231$ , proposé dans des copies, n'a qu'une bande passante de $9$ .

Q27. L'arbre $T^{*}$ n'existe que si $G$ est connexe : on le suppose donc ici. Notons $c^{*}$ le chemin élémentaire de $x$ à $y$ dans $T^{*}$ .

Premier cas : $x = y$ . Le chemin $c^{*} = x$ est de longueur nulle, de bande passante $+ \infty$ , la plus grande valeur possible : il est de bande passante maximale.

Second cas : $x \neq = y$ . Le chemin $c^{*}$ a au moins une arête ; soit $e$ une arête de $c^{*}$ de poids minimal, de sorte que $b (c^{*}) = p (e)$ . Supposons par l'absurde qu'un chemin $c = y_{0} y_{1} \dots y_{m}$ de $x$ à $y$ dans $G$ vérifie $b (c) > p (e)$ : toutes ses arêtes sont de poids strictement supérieur à $p (e)$ .

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 →