[GRASS-dev] spanning tree and steiner tree problems?

[Moritz Lennert]

On 08/10/12 18:29, Michael Barton wrote:
> Then perhaps this spanning tree and Steiner net is different from
> what it used to do and what I've seen for a definition.
>
> By my understanding (and my recollection of previous behavior in
> 6.3), a Steiner tree and spanning net should produce similar, if not
> identical graphs (Steiner net is a type of spanning tree). They
> should be connecting all nodes via a set of shortest paths. That is,
> for 4 nodes, there should be a total of 4+3+2+1 = 10 total paths, not
> the complex set of paths in your graphic (same as mine BTW).
>
> If these are not connecting all nodes via a set of minimal paths,
> what ARE they doing?

The way I understand it:

- Spanning tree does not take into account specific nodes you add, but 
uses all vertices of the network. This is why you cannot specify 
specific nodes.

- Steiner network uses only the specific nodes you provide. This is why 
you have the tcats options which allows you specify which nodes you want 
to use.

And here's what wikipedia has to say:

"The Steiner tree problem is superficially similar to the minimum 
spanning tree problem: given a set V of points (vertices), interconnect 
them by a network (graph) of shortest length, where the length is the 
sum of the lengths of all edges. The difference between the Steiner tree 
problem and the minimum spanning tree problem is that, in the Steiner 
tree problem, extra intermediate vertices and edges may be added to the 
graph in order to reduce the length of the spanning tree. These new 
vertices introduced to decrease the total length of connection are known 
as Steiner points or Steiner vertices. It has been proved that the 
resulting connection is a tree, known as the Steiner tree. There may be 
several Steiner trees for a given set of initial vertices."
(http://en.wikipedia.org/wiki/Steiner_tree_problem)

Moritz