[scilab-Users] min_weight_tree for non oriented graph

[Yuta SAWA]

Do you know what "minimum spaning tree" is?

The difinition of tree is written in Wikipedia.
http://en.wikipedia.org/wiki/Tree_structure

This case, you have already had a tree.
In tree structure, any node can be root (head) of tree.

>

>
>
>   thanks for any help to a newbie, in a learning phase on a simple   
> example...  ;o-)
>
> using the min_weight_tree function with a non oriented graph, i do not
> understand the result, and for my understanding, the result is not a
> tree...
>
> before creating a request or bug, i imagine someone can explain more...
>
> Example:
>
> ta=[ 1, 1, 1, 2, 2, 2, 3, 4, 5, 8, 7, 6, 6, 6, 6, 6, 9, 9,10,11,12,13,14];
> he=[ 2,10,11, 3, 7, 8, 4, 5, 8, 7, 6,11,12,13,14,15,11,10,11,12,13,14,15];
> g=make_graph('name',0,15,ta,he);
> t=min_weight_tree(1,g);
> for i=1:(node_number(g)-1)
>         arbre(i,1)=g.tail(t(i));
>         arbre(i,2)=g.head(t(i));
> end
>
> -->arbre
> arbre  =
>
>     1.     2.
>     2.     3.
>     4.     5.
>     5.     8.
>     6.     11.
>     2.     7.
>     2.     8.
>     9.     10.
>     1.     10.
>     1.     11.
>     11.    12.
>     6.     13.
>     6.     14.
>     6.     15.
>
> For me, in a tree, the root is the only node with no head ...
> in this example: 1,4,6,9... that is a forest !
>
> so the result of min_weight_tree is not a tree ?
>
> i read and read again the help with this strange sentence
>
> If  T(I)  is the root of the tree:
> - for j < i,  T(J)  is the number of the arc in the tree after node  T(J)
> - for j > i,  T(J)  is the number of the arc in the tree before node  T(J)
>
>   t(j) is not a node... so what means "after node  T(J)" and
> before node  T(J) ??
>
>   so i suppose there is an error in this documentation...
>
>   again, thanks for any help
>
>   pam
>
>   pam



-- 
Yuta SAWA <yuta.sawa at inria.fr>
Scilab Team Member

----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.