Corrigé Mines-Ponts 2025 Informatique II MPI — Section 3.2 (Q30 à Q33) : Arêtes principales et stratégie gagnante

Lecture de l'énoncé.

Toute la section 3 se place dans $\hat{G}$ : les arbres couvrants sont ceux de $\hat{G}$, et $\Lambda ({\alpha }_0)$ est défini pour toute arête ${\alpha }_0\in \hat{E}\setminus (T\cup T^{\prime })$. Nous lisons donc $\hat{E}$ au lieu de $E$ dans les définitions de $P$, $c$ et ${\tilde{c}}_1$, comme dans Q28, qui écrit d'ailleurs indifféremment $E$ et $\hat{E}$. À la lettre, Q32 serait fausse : si $G$ est la réunion de deux arbres couvrants disjoints ne contenant pas $\{s,t\}$ (par exemple, sur $\{s,t,a,b,c\}$, les chemins $s$–$a$–$t$–$b$–$c$ et $a$–$b$–$s$–$c$–$t$), ces deux arbres forment dans $\hat{G}$ un couple éloigné ($\delta =0$) qui évite $\{s,t\}$, donc $\{s,t\}$ est principale, alors que $E\setminus (T\cup T^{\prime })=\varnothing$ donnerait $P=\varnothing$. De même, $U$ désigne l'ensemble des sommets extrémités des arêtes de $P$, et $n_U$ son cardinal.

Q30. Un parcours du graphe, en largeur ou en profondeur, depuis $s=0$ : en suivant les listes d'adjacence, on note pour chaque sommet découvert le sommet depuis lequel il l'a été. Les arcs (sommet, découvreur) forment un arbre couvrant, puisque le graphe est connexe, et le tableau des découvreurs, avec T[0] = 0, est exactement le codage de la section 2.2. Coût $O(n+m)$, linéaire, chaque liste d'adjacence étant parcourue une fois. L'algorithme de Kruskal convient aussi, mais il est moins adapté : le graphe n'est pas pondéré, et Kruskal demande une liste d'arêtes, un tri et une structure unir & trouver (le jury a valorisé le simple parcours).

Q31. Pour tout couple d'arbres couvrants, $|T\cup T^{\prime }|=2(n-1)-\delta (T,T^{\prime })$, donc

$$c=|\hat{E}\setminus (T\cup T^{\prime })|=|\hat{E}|-2(n-1)+\delta (T,T^{\prime }).$$

Nous établissons trois points, les deux premiers pour un couple $(T,T^{\prime })$ quelconque (où $P$ a un sens) et un couple éloigné $(\tilde{T},{\tilde{T}}^{\prime })$ ; on note $\tilde{c}=|\hat{E}\setminus (\tilde{T}\cup {\tilde{T}}^{\prime })|$.

(a) $c⩾\tilde{c}⩾{\tilde{c}}_1$. $\delta (T,T^{\prime })⩾\delta (\tilde{T},{\tilde{T}}^{\prime })$ par minimalité, d'où $c⩾\tilde{c}$ ; et ${\tilde{c}}_1$ compte une partie des $\tilde{c}$ arêtes hors de $\tilde{T}\cup {\tilde{T}}^{\prime }$. Si $(T,T^{\prime })$ est éloigné, on a $c=\tilde{c}$.

(b) ${\tilde{c}}_1⩾m_P-2(n_U-\kappa )$. D'une part ${\tilde{c}}_1=m_P-|P\cap (\tilde{T}\cup {\tilde{T}}^{\prime })|⩾m_P-|P\cap \tilde{T}|-|P\cap {\tilde{T}}^{\prime }|$. D'autre part $P\cap \tilde{T}$ est sans cycle et ses arêtes relient des sommets de $U$ : c'est une forêt sur $U$, dont chaque composante est contenue dans une composante de $(U,P)$. Elle a donc au moins $\kappa$ composantes, et au plus $n_U-\kappa$ arêtes, d'après le fait (F1) de la section 2.2 (une forêt à $p$ sommets et $q$ arêtes a $p-q$ composantes). Même chose pour $P\cap {\tilde{T}}^{\prime }$.