construct a Euclidean minimum spanning tree
construct a minimum spanning tree for specified metric
EuclideanMinimumSpanningTree( P, opts )
GeometricMinimumSpanningTree( P, metric, opts )
Matrix or list of lists representing set of points
positive number or one of the symbols Euclidean, Manhattan, discrete, geographical, or infinity.
(optional) one or more options as specified below
method = one of Kruskal or Prim.
Specifies the algorithm to use in constructing the minimum spanning tree. The default is Kruskal's algorithm.
For more information, see GraphTheory[MinimalSpanningTree].
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.
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].
Let P be a set of points in n dimensions, let p and q be arbitrary points from P, and let dist⁡p,q 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 dist⁡p,q.
For any norm ρ on P, the minimum spanning tree for norm ρ 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 ρ⁡p−q.
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.
Generate a set of random two-dimensional points and draw the Euclidean minimum spanning tree.
points ≔ LinearAlgebra:-RandomMatrix⁡60,2,generator=0..100.,datatype=float8
EMST ≔ EuclideanMinimumSpanningTree⁡points
EMST≔Graph 1: an undirected weighted graph with 60 vertices and 59 edge(s)
Now draw the rectilinear minimum spanning tree (corresponding to the 1-norm or Manhattan norm) on the same data.
RMST ≔ GeometricMinimumSpanningTree⁡points,1
RMST≔Graph 2: an undirected weighted graph with 60 vertices and 59 edge(s)
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.
Download Help Document