[scilab-Users] min_weight_tree for non oriented graph

[Pierre-Alain Millet]

many thanks, Yuta,

i was confusing tree and rooted tree..  In my experience (software  
data structures like bill of material)... a tree was supposed to have  
a root...

pam

Quoting Yuta SAWA <yuta.sawa at inria.fr>:

> 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.