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 de l’arbre recouvrant 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.

arbre9

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

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

Kruskal pas à pas

kruskal1

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

Arête ED AB CD AE BC EF CF AF BF FD
Poids 2 3 4 4 5 5 6 7 8 8

______________

kruskal2

Pas de cycle détecté

Arête ED AB CD AE BC EF CF AF BF FD
Poids 2 3 4 4 5 5 6 7 8 8

______________

kruskal3

Pas de cycle détecté

Arête ED AB CD AE BC EF CF AF BF FD
Poids 2 3 4 4 5 5 6 7 8 8

______________

kruskal4

Pas de cycle détecté

Arête ED AB CD AE BC EF CF AF BF FD
Poids 2 3 4 4 5 5 6 7 8 8

______________

kruskal5

Pas de cycle détecté

Arête ED AB CD AE BC EF CF AF BF FD
Poids 2 3 4 4 5 5 6 7 8 8

______________

kruskal6

Arête ED AB CD AE BC EF CF AF BF FD
Poids 2 3 4 4 5 5 6 7 8 8
  • Cycle détecté: ne pas utiliser BC

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

Arête ED AB CD AE BC EF CF AF BF FD
Poids 2 3 4 4 5 5 6 7 8 8

Prim pas à pas

prim1prim2prim3prim4prim5prim6

Publicités