# Projet : Arbre couvrant de valeur minimale

Fatima Zahra Merimi / Thomas Delépine / Alexis Delplace

## Introduction

On cherche à construire un réseau constitué de terminaux et de serveurs. Chaque connexion entre deux périphériques du réseau a un coût. Le but est de minimiser le coût total du réseau. Afin de minimiser le plus possible le coût total du réseau, on divise le réseau en sous-réseaux. En pratique, cela implique que chaque client est connecté à un unique serveur.

## Etude du Problème

### Modélisation et Réflexion

Par la suite, on notera *t* le nombre de terminaux et *s* le nombre de serveurs.

Pour résoudre numériquement ce problème, on va modéliser notre réseau par un graphe simple, dont les noeuds sont les terminaux et les serveurs, les arêtes représentent les connexions. Les arêtes sont pondérées et leur poids représentant le coût de leur lien associé.

De là, on va chercher un sous-graphe couvrant tous les noeuds, en minimisant le poids des arêtes. On peut se convaincre qu'un tel graphe sera acyclique. S'il y avait un cycle, alors on pourrait supprimer une arête du cycle ce qui améliorerait le coût sans isoler de noeuds. La solution avec cycle ne serait donc pas minimale.

Ce problème est donc la recherche d'un arbre couvrant de poids minimal. Cet arbre couvrant tous les noeuds, on aura *t* + *s* noeuds, et *t* + *s* - 1 liens.

On pourra enrichir ce problème en demandant à ce que chaque terminal soit relié (directement ou indirectement) à un unique serveur. Cela correspond à trouver une forêt couvrante (plusieurs arbres couvrants).

On définit le nombre cyclomatique du graphe G par V(G) = *m* - *n* + *p*, avec *m* le nombre d'arêtes, *n* le nombre de noeuds, *p* le nombre de parties. Si G est acyclique, alors V(G) = 0.
On remarque que la seconde contrainte nous force à avoir une partie par serveur. En écrivant *m'* le nombre d'arête de la solution du problème enrichie, on a *m'* - (*t* + *s*) + *s* = 0 d'où *m'* = *t*.

Globalement, notre problème consiste donc à la recherche d'un arbre couvrant de poids minimal dans un premier temps, puis dans un second temps à la recherche d'une forêt couvrante de poids minimal.

## Résolution

On utilise l'algorithme de Prim. Cet algorithme détermine une solution optimale et unique à notre problème, avec *n*-1 arêtes. L'algorithme propose une solution de coût minimal, unique, sans cycle. L'exactitude de cet algorithme a été prouvée. Sa complexité est polynomiale $O$(|V|²) avec V, le nombre de noeud, mais sa complexité peut être améliorée en utilisant des tas pour trouver les arêtes de poids minimal, il n'est cependant pas parallélisable.

L'algorithme de Prim est glouton. Il propose une solution optimale pour la première contrainte (tous les terminaux relié à tous les serveurs). L'algorithme construit un arbre en ajoutant une arête de poids minimal par étape. On lie ce sommet à l'arbre. On peut commence par un sommet quelconque.

Pour la seconde contrainte, on va modifier l'arbre couvrant obtenue préalablement.

## Algorithme

Notre solution se décompose en deux étapes :
1) Calculer un arbre couvrant de poids minimal
2) Supprimer des arêtes de l'arbre couvrant pour créer notre forêt couvrante

La première partie de l'algorithme se fait par l'algorithme de Prim. Le pseudocode de l'algorithme est le suivant :

Déroulement de l'algorithme de Prim :


Pour la seconde partie, l'idée est de procéder à une coloration des noeuds de notre arbre couvrant. Chaque couleur correspond au serveur le plus proche. Pour ce faire, on effectue un parcours en profondeur à partir de chacun des serveurs. Enfin, on parcours les arêtes et on supprime toute arête reliant deux noeuds de couleurs différentes.

L'algorithme à donc la structure suivante :
* On définie une coloration $(S, W)$ comme étant une paire, $S$ étant un identifiant de serveur, et $W$ la distance entre le noeud coloré et le serveur $S$
* On initialise pour chaque serveurs s la couleur $(S, W)$ = $(s, 0)$
* On initialise pour chaque terminal t la couleur $(S, W)$ = $(Null, Inf)$
* On lance un parcours en profondeur à partir de chaque serveur
* Quand on arrive sur un fils $f$ de couleur $(S_f, W_s)$, on reçoit $(S_p, W_p)$ la coloration du père $p$
* Si $W_p + W_{[p, f]} < W_f$ : On recolorie $f$ de couleur $(S_p, W_p + W_{[p, f]})$
* De cette façon, on connait pour chaque terminal, son serveur le plus proche
* On parcours toutes les arêtes $[u, v]$, et on regarde les colorations $(S_u, W_u)$ $(S_v, W_v)$. Si $S_u \neq S_v$, on supprime l'arête $[u, v]$ du graphe

Déroulement de l'algorithme de la seconde contrainte :


## Conclusion

Globalement, les grandes étapes de l'algorithme sont les suivantes :


On a bien la construction d'une forêt couvrante de poids minimal, avec un serveur par composantes connexes.