Corrigé CCINP 2025 Informatique MP — Partie II (Q4 à Q9) : Arbre couvrant de poids maximal

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

Énoncé

Un graphe non orienté $G = (S, A)$ a un ensemble fini non vide $S$ de sommets et un ensemble $A$ d'arêtes (parties de $S$ à deux éléments). Un chemin est une suite $x_{0} x_{1} \dots x_{n}$ de sommets avec ${x_{i}, x_{i + 1}} \in A$ pour tout $i \in [[0, n - 1]]$ ; il est élémentaire si ses sommets sont deux à deux distincts, simple si ses arêtes le sont. Un cycle est un chemin simple avec $n ⩾ 3$ et $x_{0} = x_{n}$ ; un graphe sans cycle est acyclique. Un graphe est connexe si deux sommets quelconques sont reliés par un chemin ; un arbre est un graphe connexe acyclique. Pour une paire $a$ de sommets, $G + a = (S, A \cup {a})$ et $G - a = (S, A ∖ {a})$ .

Proposition 1 (admise). (a) Si $G$ est connexe, $∣ A ∣ ⩾ ∣ S ∣ - 1$ ; (b) si $G$ est acyclique, $∣ A ∣ ⩽ ∣ S ∣ - 1$ .

Q4. Si $G$ est connexe et si l'arête $a \in A$ appartient à un cycle de $G$ , montrer que $G - a$ est connexe.
Q5. Si $G$ est connexe et $∣ A ∣ = ∣ S ∣ - 1$ , montrer que $G$ est un arbre.

Un sous-graphe de $G$ est un graphe $(S, A^{'})$ avec $A^{'} \subseteq A$ (mêmes sommets) ; un arbre couvrant est un sous-graphe qui est un arbre.

Q6. Montrer que $G$ est connexe si et seulement s'il admet un arbre couvrant.
Q7. Soit $T = (S, A^{'})$ un arbre couvrant de $G$ , avec $A^{'} ⊊ A$ , et $a \in A ∖ A^{'}$ . (a) Justifier que $T + a$ n'est pas acyclique. (b) Si $a^{'} \in A^{'}$ est sur un cycle de $T + a$ , montrer que $T + a - a^{'}$ est un arbre couvrant de $G$ .

Un graphe pondéré $(S, A, p)$ porte une pondération $p : A \to R$ ; son poids est $p (G) = \sum_{a \in A} p (a)$ . Dans toute la suite, $G$ est connexe et $p$ est injective (poids deux à deux distincts).

Proposition 2. $G$ admet un unique arbre couvrant de poids maximal, noté $T^{*} = (S, A^{*})$ .

Q8. Montrer l'existence d'un arbre couvrant de poids maximal.
Q9. Unicité, par l'absurde : soient $T_{1} = (S, A_{1})$ et $T_{2} = (S, A_{2})$ deux arbres couvrants de poids maximal distincts, et $a_{2}$ l'arête de poids maximal de $(A_{1} ∖ A_{2}) \cup (A_{2} ∖ A_{1})$ , avec par exemple $a_{2} \in A_{2} ∖ A_{1}$ . (a) Montrer qu'une arête $a_{1} \in A_{1} ∖ A_{2}$ est sur un cycle de $T_{1} + a_{2}$ . (b) Conclure avec $T_{1} + a_{2} - a_{1}$ .

Corrigé

Q4. Écrivons le cycle $x_{0} x_{1} \dots x_{n}$ ( $x_{n} = x_{0}$ , $n ⩾ 3$ ) et soit $k$ l'indice tel que $a = {x_{k}, x_{k + 1}}$ . Les arêtes d'un cycle sont deux à deux distinctes : $a$ n'y figure qu'en position $k$ . Le chemin

$x_{k + 1} x_{k + 2} \dots x_{n} = x_{0} x_{1} \dots x_{k},$

qui fait le tour du cycle dans l'autre sens, n'emprunte que les arêtes du cycle autres que $a$ : c'est un chemin de $G - a$ qui relie les deux extrémités de $a$ .

Soient maintenant $u, v \in S$ quelconques. Comme $G$ est connexe, il existe un chemin $c$ de $u$ à $v$ dans $G$ . On y remplace chaque passage par l'arête $a$ (dans un sens ou dans l'autre) par le chemin précédent, parcouru dans le sens voulu. On obtient un chemin de $u$ à $v$ qui n'emprunte plus $a$ , donc un chemin de $G - a$ . Ainsi $G - a$ est connexe.

Q5. Supposons que $G$ ait un cycle et soit $a$ une arête de ce cycle. D'après Q4, $G - a$ est connexe, et il a $∣ A ∣ - 1 = ∣ S ∣ - 2$ arêtes, ce qui contredit la proposition 1(a) appliquée à $G - a$ . Donc $G$ est acyclique ; connexe par hypothèse, c'est un arbre.

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 →