Arbres couvrants

Arbres couvrants

Un sous-graphe de G est dit couvrant s’il contient tous les sommets de G.
Un sous-graphe couvrant n’est pas forcément connexe. Un arbre couvrant de G est un sous-graphe couvrant de G, et ce sous-graphe est un arbre.

Afin de minimiser le coût des réseaux électriques, des connexions de câblage, de la tuyauterie, de la reconnaissance vocale automatique, etc., nous utilisons des algorithmes qui construisent progressivement un arbre couvrant (ou plusieurs de ces arbres) comme étapes intermédiaires du processus de recherche des arbres couvrants minimum.

L’Internet et de nombreux autres réseaux de télécommunication ont des liens de transmission qui relient les nœuds ensemble dans une topologie maillée qui inclut certaines boucles. Afin d’éviter les boucles de pont et les boucles de routage, de nombreux protocoles de routage conçus pour de tels réseaux exigent que chaque routeur se souvienne d’un arbre couvrant.

arbre couvrant

Il est facile de construire un arbre couvrant :

  • tant qu’on a pas ajouter n-1 arêtes à G’, avec n le nombre de sommets du graphe, on choisit une arête de G de telle façon que son ajout ne crée pas un cycle dans G’.
  • tant que le nombre d’arêtes restantes est supérieur à n-1, on retire une arête de G tel que G soit toujours connexe.

La problématique des arbres couvrants est très utilisée dans le cadre d’arêtes pondérées.

On parle alors d’arbre couvrant à poids minimal. Ce problème est un problème de création de réseau : soient n lieux à connecter, nous connaissons les coûts pour connecter un lieu à un autre, on recherche à connecter tous les lieux au plus petit coût.

Pour fabriquer un arbre couvrant de poids minimal, nous énoncerons deux algorithmes gloutons.

Algorithme de Kruskal

Au début, le graphe G’ ne contient que les sommets  de G et nous possédons une file (fifo) vide f :

  • pour chaque sommet v de G
    • ajouter v à f
  • trier f par ordre croissant
  • tant que la file n’est pas vide
    • défiler f -> arête a
    • si l’ajout de a ne crée pas de cycle dans G’ alors ajouter a dans G’
  • retourner G’

Pour savoir si l’on crée un cycle, il suffit de savoir si l’on peut atteindre un sommet de l’arête en partant de l’autre sommet dans G’. Pour rappel, dans un arbre il n’existe qu’un seul chemin d’un sommet à un autre.

 kruskal arbre couvrant

Algorithme de Prim

Le principe consiste à agrandir un arbre en ajoutant une arête de poids minimum incidente à l’arbre.

Au début, le graphe G’ ne contient qu’un sommet de G :

  • tant que G’ ne contient pas tous les sommets de G
    • mettre dans une file toutes les arêtes de G qui relient un sommet de G’ à un sommet qui n’est pas dans G’
    • trier par ordre croissant la file
    • tant que la file n’est pas vide ou qu’on n’a pas rajouté d’arête
      • défiler la file -> arête a
      • si l’ajout de a ne crée par de cycle dans G’ alors ajouter a dans G’

L’algorithme étant complexe à comprendre par l’écrit, nous allons montrer un exemple :

prim arbre couvrant

Kruskal pas à pas

kruskal arbre couvrant

Ci-dessous la liste des arêtes triées par ordre de poids :

ArêteEDABCDAEBCEFCFAFBFFD
Poids2344556788

______________

kruskal arbre couvrant

Pas de cycle détecté

ArêteEDABCDAEBCEFCFAFBFFD
Poids2344556788

______________

kruskal arbre couvrant

Pas de cycle détecté

ArêteEDABCDAEBCEFCFAFBFFD
Poids2344556788

______________

kruskal arbre couvrant

Pas de cycle détecté

ArêteEDABCDAEBCEFCFAFBFFD
Poids2344556788

______________

kruskal arbre couvrant

Pas de cycle détecté

ArêteEDABCDAEBCEFCFAFBFFD
Poids2344556788

______________

kruskal arbre couvrant

ArêteEDABCDAEBCEFCFAFBFFD
Poids2344556788
  • Cycle détecté: ne pas utiliser BC

Pas de cycle détecté, n-1 arête-> END

ArêteEDABCDAEBCEFCFAFBFFD
Poids2344556788

Prim pas à pas

prim arbre couvrantprim arbre couvrantprim arbre couvrantprim arbre couvrantprim arbre couvrantprim arbre couvrant