Arbre couvrant de poids minimal
Un certain nombre de problèmes issus de la théorie des graphes sont appelés arbre à portée minimale. Dans la théorie des graphes, un arbre est un moyen de relier tous les sommets entre eux, de sorte qu'il y ait exactement un chemin d'un sommet à un autre de l'arbre. Si le graphe représente un certain nombre de villes reliées par des routes, on pourrait sélectionner un certain nombre de routes, de sorte que chaque ville puisse être atteinte à partir de toutes les autres, mais qu'il n'y ait pas plus d'un chemin pour aller d'une ville à une autre.
Un graphique peut comporter plus d'un arbre, tout comme il peut y avoir plus d'une façon de sélectionner les routes entre les villes.
La plupart du temps, les graphiques sont pondérés ; chaque liaison entre deux villes a un poids : il peut en coûter quelque chose pour voyager sur une route donnée, ou une liaison peut être plus longue que l'autre, ce qui signifie qu'il faut plus de temps pour voyager sur cette liaison. Dans le langage de la théorie des graphes, les liaisons sont appelées "arêtes".
Un arbre d'une portée minimale est un arbre. Il se distingue des autres arbres en ce qu'il minimise le total des poids attachés aux bords. Selon l'aspect du graphique, il peut y avoir plus d'un arbre à portée minimale. Dans un graphique où toutes les bordures ont le même poids, chaque arbre est un arbre à portée minimale. Si toutes les arêtes ont des poids différents (c'est-à-dire qu'il n'y a pas deux arêtes ayant le même poids), il y a exactement un arbre à portée minimale.
L'arbre à portée minimale d'un graphique planaire. Chaque bord est marqué de son poids, qui est ici à peu près proportionnel à sa longueur.
Trouver l'arbre à portée minimale
Un premier essai
Il peut être très simple de créer un algorithme qui découvrira un arbre à portée minimale :
fonction MST(G,W) : T = { } alors que T ne forme pas un arbre de couverture : trouver le bord minimum pondéré dans E qui est sûr pour l'union T T = T {(u,v)} renvoie TDans ce cas, "sûr" signifie que l'inclusion du bord ne forme pas un cycle dans le graphique. Un cycle signifie que l'on part d'un sommet, que l'on se rend à plusieurs autres sommets et que l'on se retrouve au point de départ sans utiliser deux fois la même arête.
Histoire
Le scientifique tchèque Otakar Borůvka a développé le premier algorithme connu pour trouver un arbre à portée minimale, en 1926. Il voulait résoudre le problème de la couverture efficace de la Moravie par l'électricité. Aujourd'hui, cet algorithme est connu sous le nom d'algorithme de Borůvka. Deux autres algorithmes sont couramment utilisés aujourd'hui. L'un d'eux a été développé par Vojtěch Jarník en 1930, et mis en pratique par Robert Clay Prim en 1957. Edsger Wybe Dijkstra l'a redécouvert en 1959, et l'a appelé l'algorithme de Prim. L'autre algorithme est appelé algorithme de Kruskal, et a été pulbisé par Joseph Kruskal en 1956. Les trois algorithmes sont gourmands et fonctionnent en temps polynomial.
L'algorithme de l'arbre à portée minimale le plus rapide à ce jour a été développé par Bernard Chazelle. L'algorithme est basé sur le soft heap, une file d'attente de priorité approximative. Son temps de fonctionnement est O(m α(m,n)), où m est le nombre d'arêtes, n le nombre de sommets et α est l'inverse fonctionnel classique de la fonction d'Ackermann. La fonction α croît extrêmement lentement, de sorte qu'à toutes fins pratiques, elle peut être considérée comme une constante ne dépassant pas 4 ; l'algorithme de Chazelle prend donc un temps très proche du temps linéaire.
Quel est l'algorithme le plus rapide possible pour ce problème ? C'est l'une des plus anciennes questions ouvertes en informatique. Il y a clairement une limite inférieure linéaire, puisque nous devons au moins examiner tous les poids. Si les poids de bord sont des entiers avec une longueur de bit limitée, alors les algorithmes déterministes sont connus avec un temps de fonctionnement linéaire. Pour les poids généraux, il existe des algorithmes randomisés dont le temps de fonctionnement prévu est linéaire.
Le problème peut également être abordé de manière distribuée. Si chaque nœud est considéré comme un ordinateur et qu'aucun nœud ne sait rien d'autre que ses propres liens connectés, on peut toujours calculer l'arbre de couverture minimum distribué.
Questions et réponses
Q : Qu'est-ce qu'un arbre à portée minimale en théorie des graphes ?
R : Un arbre à recouvrement minimal est un arbre qui minimise les poids totaux attachés aux arêtes dans la théorie des graphes.
Q : Qu'est-ce qu'un arbre en théorie des graphes ?
R : Un arbre est un moyen de relier tous les sommets entre eux dans la théorie des graphes, de sorte qu'il n'y ait qu'un seul chemin d'un sommet à un autre sommet de l'arbre.
Q : Quel est l'intérêt de sélectionner des routes dans un scénario de théorie des graphes représentant des villes ?
R : Le but de la sélection des routes dans un scénario de théorie des graphes représentant des villes est de permettre à chaque ville d'être accessible depuis toutes les autres villes, mais sans qu'il n'y ait plus d'un chemin possible pour aller d'une ville à l'autre.
Q : Un graphe peut-il avoir plus d'un arbre couvrant ?
R : Oui, un graphe peut avoir plus d'un arbre couvrant.
Q : Quelle est la différence entre un arbre à enjambement minimal et les autres arbres de la théorie des graphes ?
R : Un arbre à recouvrement minimal minimise le poids total des arêtes, alors que les autres arbres n'ont pas cette caractéristique.
Q : Que sont les arêtes dans la théorie des graphes ?
R : Les arêtes sont les connexions entre deux sommets dans la théorie des graphes.
Q : Peut-il y avoir plus d'un arbre à recouvrement minimal dans un graphe avec des arêtes pondérées différentes ?
R : Oui, selon l'aspect du graphe, il peut y avoir plus d'un arbre couvrant minimal.
