Corrigé Mines-Ponts 2025 Informatique II MPI — Section 3.1 (Q26 à Q29) : Arbres couvrants éloignés : chaînes d'échanges

Rappels et convention.

(F2) Si $X$ est un arbre couvrant, $x\notin X$ et $y\in C(X,x)$, alors $X\cup \{x\}\setminus \{y\}$ est un arbre couvrant (il a $n-1$ arêtes, et un cycle y serait un cycle de $X\cup \{x\}$ distinct de $C(X,x)$, puisqu'il ne contient pas $y$). Pour $\alpha \in X$, l'ajout de $\alpha$ ne crée rien : on convient que $C(X,\alpha )=\{\alpha \}$. C'est la seule lecture qui rende la suite $(L_k)$ croissante, comme l'affirme l'énoncé, car $L_1$ contient des arêtes de $T$ dès la définition de $L_3$. Avec cette convention, $\alpha \in C(X,\alpha )$ pour toute arête $\alpha$, donc $L_{j-1}\subseteq L_j$.

Q26. ${\alpha }_1\ne {\alpha }_0$ puisque ${\alpha }_0\notin T$, et ${\alpha }_1\in C(T,{\alpha }_0)$. On pose

$$\tilde{T}=T\cup \{{\alpha }_0\}\setminus \{{\alpha }_1\},{\tilde{T}}^{\prime }=T^{\prime }.$$

$\tilde{T}$ est un arbre couvrant d'après (F2). Comme ${\alpha }_0\notin T^{\prime }$, on a $\tilde{T}\cap {\tilde{T}}^{\prime }=(T\setminus \{{\alpha }_1\})\cap T^{\prime }=(T\cap T^{\prime })\setminus \{{\alpha }_1\}$, d'où $\delta (\tilde{T},{\tilde{T}}^{\prime })=\delta (T,T^{\prime })-1$.

Q27. D'abord $L_1\cap T^{\prime }=\varnothing$ : $L_1$ est formé de ${\alpha }_0\notin T^{\prime }$ et d'arêtes de $T$, qui ne sont pas dans $T\cap T^{\prime }$ par hypothèse, donc pas dans $T^{\prime }$. Ainsi chaque $C(T^{\prime },\alpha )$, $\alpha \in L_1$, est un vrai cycle. Soit ${\alpha }_1\in L_1$ tel que ${\alpha }_2\in C(T^{\prime },{\alpha }_1)$ ; ${\alpha }_2\ne {\alpha }_1$, car ${\alpha }_2\in T^{\prime }$ et ${\alpha }_1\notin T^{\prime }$.

• Si ${\alpha }_1={\alpha }_0$ : $\tilde{T}=T$ et ${\tilde{T}}^{\prime }=T^{\prime }\cup \{{\alpha }_0\}\setminus \{{\alpha }_2\}$, arbre couvrant d'après (F2). Comme ${\alpha }_0\notin T$, $\tilde{T}\cap {\tilde{T}}^{\prime }=(T\cap T^{\prime })\setminus \{{\alpha }_2\}$.
• Si ${\alpha }_1\ne {\alpha }_0$ : ${\alpha }_1\in C(T,{\alpha }_0)\setminus \{{\alpha }_0\}\subseteq T$, et ${\alpha }_1\notin T^{\prime }$. On fait deux échanges :

$$\tilde{T}=T\cup \{{\alpha }_0\}\setminus \{{\alpha }_1\},{\tilde{T}}^{\prime }=T^{\prime }\cup \{{\alpha }_1\}\setminus \{{\alpha }_2\},$$

arbres couvrants d'après (F2), puisque ${\alpha }_1\in C(T,{\alpha }_0)$ et ${\alpha }_2\in C(T^{\prime },{\alpha }_1)$. Or ${\alpha }_0\notin {\tilde{T}}^{\prime }$ (car ${\alpha }_0\notin T^{\prime }$ et ${\alpha }_0\ne {\alpha }_1$) et ${\alpha }_1\notin \tilde{T}$ ; donc $\tilde{T}\cap {\tilde{T}}^{\prime }=(T\setminus \{{\alpha }_1\})\cap (T^{\prime }\setminus \{{\alpha }_2\})=(T\cap T^{\prime })\setminus \{{\alpha }_2\}$, car ${\alpha }_1\notin T^{\prime }$.

Dans les deux cas $\delta (\tilde{T},{\tilde{T}}^{\prime })=\delta (T,T^{\prime })-1$. Ce que le correcteur attend : l'adaptation de Q26. Le seul échange dans $T^{\prime }$ ferait entrer ${\alpha }_1\in T$ dans $T^{\prime }$ : l'intersection perdrait ${\alpha }_2$ mais gagnerait ${\alpha }_1$, et $\delta$ ne diminuerait pas. Il faut aussi sortir ${\alpha }_1$ de $T$, ce que permet ${\alpha }_0$.

Q28. Notations. Pour $j⩾1$, on note $X_j=T$ si $j$ est impair, $X_j=T^{\prime }$ si $j$ est pair, et $Y_j$ l'autre arbre : $L_j={\bigcup }_{\beta \in L_{j-1}}C(X_j,\beta )$ dès que $L_{j-1}$ ne rencontre pas $T\cap T^{\prime }$. Soit $K$ le plus petit indice tel que $L_K$ rencontre $T\cap T^{\prime }$, s'il existe ($K⩾1$ car ${\alpha }_0\notin T$) : la suite est alors définie jusqu'à $L_K$ exactement. Sinon elle est définie pour tout $k$, et l'on pose $K=+\infty$. Le niveau $\nu (\alpha )$ d'une arête atteinte est le plus petit $j$ tel que $\alpha \in L_j$. Par définition :