Transform - Spanning Tree

Given a set of points, builds a minimum spanning tree network on that point set by adding lines.

 

A spanning tree is a network that connects all of the points in the point sets without forming any loops. A minimum spanning tree connects points so that if the lengths of all the links are added up there is no way to connect all of the points using links with a lower total length. If we wish to connect all the points using fiber optic cable the minimum spanning tree will use the least total amount of cable.

 

Although points sets will often have one and only one spanning tree arrangement that results in the lowest distance, regularly arranged point sets (such as those in orthogonal grids) can have many different spanning tree networks drawn that will all have the same, lowest, total length of links. The minimum spanning tree transform simply guarantees that no tree can be drawn that uses less material than the spanning tree it finds.

 

images\sc_nets_points.gif

 

Given the point set above, the minimum spanning tree operator would create the network shown below:

 

images\sc_nets_spantree.gif

 

Minimum spanning trees are very important in a very wide range of disciplines. Because they show how to connect points with the least connecting material they are obviously important in any analysis that requires short distances between connected items and minimization of overall connection distances.

 

Select Spanning Tree

 

Given a network, this operator selects those lines in the network that make up a minimum spanning tree.

 

images\sc_nets_spantree_sel01.gif

We can create the network above by inserting points into a drawing and then running the Relative Neighborhood operator.

 

images\sc_nets_spantree_sel02.gif

 

If we then run the Select Spanning Tree operator it will select those lines that participate in a minimum spanning tree.

 

See Also

 

Clusters - The transform operator that in the Clusters (Zahn) form uses minimum spanning trees to find clusters.

 

Relative Neighborhood Network - The transform operator that creates relative neighborhood networks, which are subsets of Gabriel networks. This topic includes a note on characteristics of relative neighborhood networks.

 

Notes

 

In graph theory, networks are called graphs. When searching Internet for information on these topics try searching for words like "relative neighborhood", "graph", "spanning tree", "cluster" and similar. These ideas are applied in an astonishing range of disciplines, from fungal spore distribution patterns to the characterization of finds in archeological sites.

 

The points for the examples above were created by making centroids for provinces in Mexico using the Centroids (Weight) transform operator. The points and results of the transform operators are shown in a map with a drawing of Mexico as a backdrop. We used the centroids as a source set of points because they are dispersed in a geographically interesting way. There is no meaning to the map of Mexico; however, if we were to place one antenna in the geographic center of each province and then we wished to link the antennas in a network we would likely create and study maps such as these.