| PANDORE Version 6 | GREYC-IMAGE |
L'opérateur pmst permet de calculer l'arbre de recouvrement minimal du graphe gr_in.
L'arbre de recouvrement minimal est l'arbre de recouvrement dont la somme des poids des arcs est minimum. Cette structure moins dense que le graphe d'origine ne contient que les arcs entre les sommets les plus proches au sens d'une distance quelconque (ici euclidienne) et donnée dans le poids des arcs.
La technique utilisée correspond à l'algorithme de Prim. Cet algorithme est basé sur le grossissement d'un sous-graphe jusqu'à recouvrement en choissisant d'ajouter à chaque fois l'arête de plus faible coût qui ne crée pas un cycle. On prend comme racine de l'arbre le dernier sommet du graphe (pure convention).
Les liens entre les sommets sont modifiés de manière physique; les relations de voisinage initiales sont perdues et les poids des arcs restants sont mis à 1.
Retourne SUCCESS ou FAILURE.
pmst g1.pan g2.pan
Auteur: François Angot