EuclideanMinimumSpanningTree - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

GraphTheory[GeometricGraphs]

 EuclideanMinimumSpanningTree
 construct a Euclidean minimum spanning tree
 GeometricMinimumSpanningTree
 construct a minimum spanning tree for specified metric

 Calling Sequence EuclideanMinimumSpanningTree( P, opts ) GeometricMinimumSpanningTree( P, metric, opts )

Parameters

 P - Matrix or list of lists representing set of points metric - positive number or one of the symbols Euclidean, Manhattan, discrete, geographical, or infinity. opts - (optional) one or more options as specified below

Options

 • method = one of Kruskal or Prim.
 Specifies the algorithm to use in constructing the minimum spanning tree. The default is Kruskal's algorithm.
 • triangulation = list of three-element lists.
 Supply a previously computed Delaunay triangulation of P. The input must be a valid Delaunay triangulation in the format returned by ComputationalGeometry[DelaunayTriangulation]: a list of three-element lists of integers, representing triangles in a triangulation of P.
 • vertices = list of integers, strings or symbols
 Specifies the vertices to be used in the generated graph.
 • weighted = truefalse
 If weighted=true, the result is a weighted graph whose edge weights correspond to the distance between points using the specified metric. Default is false.

Description

 • The EuclideanMinimumSpanningTree(P, opts) command returns a minimum spanning tree for the graph generated from the point set P.
 • The GeometricMinimumSpanningTree(P, norm, opts) command returns a minimum spanning tree for the graph generated from the point set P using the norm metric.
 • The parameter P must be a Matrix or list of lists representing a set of points.
 • The parameter metric must be a positive number or one of the symbols Euclidean, Manhattan, or infinity. A positive number p corresponds to the p-norm of the difference x-y of two points x and y.
 For more information on norms, see LinearAlgebra[Norm].

Definitions

 • Let $P$ be a set of points in $n$ dimensions, let $p$ and $q$ be arbitrary points from $P$, and let $\mathrm{dist}\left(p,q\right)$ be the Euclidean distance between $p$ and $q$.
 • The Euclidean minimum spanning tree is simply a minimum-weight spanning tree for the complete weighted graph on $P$ with the weight of the edge between points $p$ and $q$ defined to be $\mathrm{dist}\left(p,q\right)$.
 • For any norm $\mathrm{\rho }$ on $P$, the minimum spanning tree for norm $\mathrm{\rho }$ is a minimum-weight spanning tree for the complete weighted graph on $P$ with the weight of the edge between points $p$ and $q$ defined to be $\mathrm{\rho }\left(p-q\right)$.
 • The Euclidean minimum spanning tree has the following relationships with other graphs:
 The Euclidean minimum spanning tree on P is a subgraph of the relative neighborhood graph on P.
 The Euclidean minimum spanning tree on P is a subgraph of the Urquhart graph on P.

Examples

Generate a set of random two-dimensional points and draw the Euclidean minimum spanning tree.

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{GeometricGraphs}\right):$
 > $\mathrm{points}≔\mathrm{LinearAlgebra}:-\mathrm{RandomMatrix}\left(60,2,\mathrm{generator}=0..100.,\mathrm{datatype}=\mathrm{float}\left[8\right]\right)$
 > $\mathrm{EMST}≔\mathrm{EuclideanMinimumSpanningTree}\left(\mathrm{points}\right)$
 ${\mathrm{EMST}}{≔}{\mathrm{Graph 1: an undirected weighted graph with 60 vertices and 59 edge\left(s\right)}}$ (1)
 > $\mathrm{DrawGraph}\left(\mathrm{EMST}\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{EuclideanMinimumSpanningTree}\left(\mathrm{points},\mathrm{method}=\mathrm{Prim}\right)\right)$

Now draw the rectilinear minimum spanning tree (corresponding to the 1-norm or Manhattan norm) on the same data.

 > $\mathrm{RMST}≔\mathrm{GeometricMinimumSpanningTree}\left(\mathrm{points},1\right)$
 ${\mathrm{RMST}}{≔}{\mathrm{Graph 2: an undirected weighted graph with 60 vertices and 59 edge\left(s\right)}}$ (2)
 > $\mathrm{DrawGraph}\left(\mathrm{RMST}\right)$

Compatibility

 • The GraphTheory[GeometricGraphs][EuclideanMinimumSpanningTree] and GraphTheory[GeometricGraphs][GeometricMinimumSpanningTree] commands were introduced in Maple 2020.
 • For more information on Maple 2020 changes, see Updates in Maple 2020.