مسابقة دكتوراه 2016 — Université des Sciences et de la Technologie Houari Boumediène (USTHB)

التمرين 2

Exercice 2 — Arbre de poids maximum dans un graphe pondéré

#graph-theory#maximum-spanning-tree#greedy-algorithm#integer-programming

Soit $G=(V,E)$ un graphe simple et connexe, $p:E\to \mathbb{R}$ une pondération, $|V|=n$ , $E=\{e_1,\ldots,e_m\}$ avec $p(e_i) \leq p(e_{i+1})$ . On définit la famille $(T_i)$ par : $T_0=E$ , $T_i=T_{i-1}\setminus\{e_i\}$ si $i\gt 0$ et si $(V,T_{i-1}\setminus\{e_i\})$ est connexe, sinon $T_i=T_{i-1}$ .

Donner au moins trois caractérisations des arbres et montrer leur équivalence.
Montrer que si dans un graphe connexe, $T$ et $T'$ sont deux arbres distincts, alors $T$ contient une arête dont le rajout à $T'$ crée un unique cycle.
Montrer que $T_m$ est un arbre de poids maximum dans $G$ .
Donner la complexité de l'algorithme donnant $T_m$ .
Comment modifier cet algorithme pour déterminer une forêt de poids maximum de $G$ ?
Donner, dans le graphe fourni, un arbre et une forêt de poids maximums.
Prouver que si $p(e) \neq p(e')$ pour $e \neq e'$ , alors l'arbre de poids maximum est unique.
Montrer que si $G$ possède un cycle ayant une arête de poids inférieur à celui de toute autre arête de ce cycle, alors cette arête n'appartient à aucun arbre de poids maximum.
Montrer que les PLNE $(F_1)$ et $(F_2)$ formulent le problème de l'arbre de poids minimum et que $(F_2)$ est meilleure.

◀الحل

1.

Caractérisations classiques : graphe connexe sans cycle, graphe connexe à $n-1$ arêtes, graphe sans cycle à $n-1$ arêtes, existence d'un unique chemin entre deux sommets. Elles sont équivalentes par résultats standards.

2.

Si $T \neq T'$ , il existe une arête $e \in T \setminus T'$ . Comme $T'$ est un arbre, l'ajout de $e$ à $T'$ crée exactement un cycle.

3.

L'algorithme décrit est l'algorithme glouton inverse de Kruskal : on retire successivement les arêtes de plus petit poids qui ne déconnectent pas le graphe. Il produit un arbre couvrant de poids maximum.

4.

La complexité dépend des tests de connexité répétés : naïvement $O(m(m+n))$ . Avec structure union-find et tri, on obtient l'équivalent de Kruskal en $O(m \log m)$ .

5.

Pour une forêt de poids maximum, on supprime la contrainte de connexité globale et on applique l'algorithme composante par composante, en gardant simplement l'acyclicité.

6-8.

Application directe des propriétés des arbres couvrants maximums.

9.

$(F_1)$ et $(F_2)$ sont des formulations classiques du MST. $(F_2)$ , par contraintes de coupure, a en général un polyèdre plus fort.