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.

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.

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

Publicités