Scilab function

min_weight_tree - arbre couvrant de poids minimum

Sequence d'appel

t = min_weight_tree([i],g)

Parametres

Description

min_weight_tree essaye de trouver un arbre couvrant de poids minimum pour l'arbre graphe g. L'argument optionnel i est le numéro du sommet racine de l'arbre; sa valeur par défaut est le sommet 1. Ce sommet n'est pas significatif pour un graphe non-orienté.

Les poids sont données par les éléments edge_weight du graphe. Si ces valeurs ne sont pas données (vecteur vide []), elles sont supposées nulles. Les poids peuvent être positifs, nuls ou négatifs. Pour calculer un arbre recouvrant sans tenir compte des poids, leur donner une valeur nulle ou vide [].

min_weight_tree renvoie l'arbre t sous forme d'un vecteur ligne des numéros d'arcs (cas orienté) ou d'arêtes (cas non-orienté), si il existe, ou le vecteur vide [] sinon. Si l'arbre existe, la dimension de t est le nombre de sommets moins 1. Si t(i) est la racine de l'arbre, - pour j < i, t(j) est le numéro de l'arc dans l'arbre après le sommet t(j) - pour j > i, t(j) est le numéro de l'arc dans l'arbre avant le sommet t(j)

Exemples