MINIMUM SPANNING TREE

MINIMUM SPANNING TREE

LET Subcommand

Compute the minimum spanning tree of either a set of vertices or a distance matrix.

A spanning tree of a connected, undirected graph is a subgraph which is a tree that connects all the vertices together. A graph can more than one spanning tree. Distances are defined for each edge in the graph (alternatively, edges could be represented by weights or costs). the edges

The minimum spanning tree is the spanning tree for which the sum of the distances over the edges in the spanning tree is a minimum.

Dataplot supports two forms of the minimum spanning tree.

1. The input is a set of x and y coordinates for the vertices in the graph. In this case, the distance between two vertices is simply the Euclidean distance between the vertices.

2. The input is a distance matrix. In this case, the distance can denote a weight or a cost instead of a distance.

LET <y2> <x2> <tag> = MINIMUM SPANNING TREE <y> <x>
                        <SUBSET/EXPCEPT/FOR qualification>
where <y> is a variable containing the y-coordinates of the full data set;
            <x> is a variable containing the x-coordinates of the full data set;
            <y2> is a variable that will contain the y-coordinats of the returned minimum spanning tree;
            <x2> is a variable that will contain the x-coordinats of the returned minimum spanning tree;
            <tag> is a variable that will contain a trace-id (i.e., points that will be connected) of the returned minimum spanning tree;
and where the <SUBSET/EXCEPT/FOR qualification> is optional.

LET <edge1> <edge2> = MINIMUM SPANNING TREE <dist>
                        <SUBSET/EXPCEPT/FOR qualification>
where <dist> is a matrix containing the distances (or weights or costs);
            <edge1> is a variable that will contain the first vertex of the edges in the mimimum spanning tree;
            <edge2> is a variable that will contain the second vertex of the edges in the mimimum spanning tree;
and where the <SUBSET/EXCEPT/FOR qualification> is optional.

LET Y2 X2 TAG = MINIMUM SPANNING TREE Y X
LET EDGE1 EDGE2 = MINIMUM SPANNING TREE DIST

Dataplot uses the MINSPT algorithm given in Nijenhuis and Wilf (see the Reference section below).

None.

None

MATRIX DISTANCE	= Compute a distance matrix.
2D CONVEX HULL	= Compute the 2D convex hull of a set of vertices.
SPANNING FOREST	= Determine the spanning forest.
NEXT PERMUTATION	= Generate the next permutation of a positive integer.
RANDOM PERMUTATION	= Generate a random permutation of a positive integer.

Nijenhuis and Wilf (1978), "Combinatorial Algorithms", Second Edition, Academic Press, Chapter 30.

Graph Theory

2008/4

 
read matrix d
  0  100  125  120  110
100    0   40   65   60
125   40    0   45   55
120   65   45    0   50
110   60   55   50    0
end of data
.
let y2 x2 = minimum spanning tree d
set write decimals 1
print y2 x2
    

The following output is generated.

          2              1
          3              2
          4              3
          5              4
    

 
skip 1
read convex_hull.dat x y
.
let y2 x2 tag = minimum spanning tree y x
.
title case asis
title offset 2
title Minimum Spanning Tree
y1label Y
x1label X
tic offset units screen
tic offset 3 3
x3label
.
plot y2 x2 tag