Corrigé Mines-Ponts 2025 Informatique II MPI — Section 2.2 (Q19 à Q25) : Échange d'arêtes entre arbres couvrants et stratégie de Positus

Deux faits sur les forêts.

(F1) Une forêt (graphe sans cycle) à $p$ sommets et $q$ arêtes a exactement $p-q$ composantes connexes : chacune est un arbre, et un arbre à $p_i$ sommets a $p_i-1$ arêtes ; on somme sur les composantes. (F2) Si $T$ est un arbre couvrant, $e\notin T$ et $f\in C(T,e)$, alors $T\cup \{e\}\setminus \{f\}$ est un arbre couvrant : il a $n-1$ arêtes, et un cycle de cet ensemble serait un cycle de $T\cup \{e\}$ ne contenant pas $f$, donc distinct de l'unique cycle $C(T,e)$. Ces faits valent dans tout graphe connexe, en particulier dans $G_U$.

Q19. $T\setminus \{\alpha \}$ est sans cycle, avec $n$ sommets et $n-2$ arêtes : d'après (F1), il a exactement deux composantes connexes, d'ensembles de sommets $A$ et $B$, avec $A\cup B=V$. Choisissons $a\in A$ et $b\in B$. Comme $(V,T^{\prime })$ est connexe, un chemin de $T^{\prime }$ relie $a$ à $b$ ; en le parcourant, on passe de $A$ à $B$, donc l'une de ses arêtes, $\beta$, a une extrémité dans $A$ et l'autre dans $B$.

$T^{\prime \prime }=T\setminus \{\alpha \}\cup \{\beta \}$ a $n-1$ arêtes ($\beta \notin T\setminus \{\alpha \}$, car aucune arête de $T\setminus \{\alpha \}$ ne relie $A$ à $B$). Il est sans cycle : $T\setminus \{\alpha \}$ n'en a pas, donc un cycle de $T^{\prime \prime }$ passerait par $\beta$, et le reste de ce cycle serait un chemin de $T\setminus \{\alpha \}$ entre les extrémités de $\beta$, qui sont dans deux composantes différentes : c'est impossible. $T^{\prime \prime }$ est donc un arbre couvrant. (Si $\alpha \in T^{\prime }$, on peut obtenir $\beta =\alpha$ et $T^{\prime \prime }=T$.)

Ce que le correcteur attend : les deux composantes de $T\setminus \{\alpha \}$ et la connexité de $T^{\prime }$ ; le jury signale la confusion fréquente entre arbre couvrant et ensemble d'arêtes qui touche tous les sommets.

Q20. On traduit la preuve de Q19 avec la structure unir & trouver de Q4 et Q5. Les arêtes de $T$ sont les $\{v,\text{T[v]}\}$ pour $v\ne 0$, et $\alpha =\{u,\text{T[u]}\}$ où $u=\text{alpha.first}$. On calcule les deux composantes de $T\setminus \{\alpha \}$, puis on cherche une arête $\{v,\text{Tprime[v]}\}$ de $T^{\prime }$ qui les relie.

pair_t edge_find(int n, int * T, int * Tprime, pair_t alpha) {
    assert(alpha.first != 0 && T[alpha.first] == alpha.second);
    int * A = malloc(n * sizeof(int));
    assert(A != NULL);
    for (int v = 0; v < n; v++) {
        A[v] = v;
    }
    /* classes = composantes connexes de T prive de alpha */
    for (int v = 1; v < n; v++) {
        if (v != alpha.first) {
            uf_unite(n, A, v, T[v]);
        }
    }
    /* premiere arete de T' qui relie les deux composantes */
    pair_t beta = {-1, -1};
    for (int v = 1; v < n && beta.first == -1; v++) {
        if (uf_find(n, A, v) != uf_find(n, A, Tprime[v])) {
            beta.first = v;
            beta.second = Tprime[v];
        }
    }
    free(A);
    assert(beta.first != -1);   /* garanti par Q19 */
    return beta;
}

Après la première boucle, deux sommets ont le même identifiant si et seulement s'ils sont reliés dans $T\setminus \{\alpha \}$ : il y a deux classes, $A$ et $B$. La seconde boucle passe en revue les arêtes de $T^{\prime }$ et s'arrête sur la première dont les extrémités sont dans des classes différentes ; Q19 garantit qu'elle existe, et la preuve de Q19 montre qu'elle convient. Coût : $n-2$ unions et au plus $2(n-1)$ recherches, chacune en $O(h)$ où $h⩽n$ est la hauteur des arbres de la structure, soit $O(n^2)$ au pire, $O(n\log n)$ avec l'union par rang. Exécution : sur $26002$ couples $(T,\alpha )$ tirés au hasard dans des graphes de $2$ à $13$ sommets, l'arête renvoyée est dans $T^{\prime }$ et $T\cup \{\beta \}\setminus \{\alpha \}$ est un arbre couvrant ; le tableau A est libéré (aucune fuite).