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 : true or false

If weighted=true, the result is a weighted graph whose edge weights correspond to the distance between points using the specified norm. 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 norm.

The parameter P must be a Matrix or list of lists representing a set of points.

The parameter norm must be a positive number or one of the symbols Euclidean or infinity. This specifies the norm to be used in computing distances.

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 $\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.

$\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{points}≔\begin{array}{c}\left[\begin{array}{cc}9.85017697341803& 82.9750304386195\\ 86.0670183749663& 83.3188659363996\\ 64.3746795546741& 73.8671607639673\\ 57.3670557294666& 2.34399775883031\\ 23.6234264844933& 52.6873367387328\\ 47.0027547350003& 22.2459488367552\\ 74.9213491558963& 62.0471820220718\\ 92.1513434709073& 96.3107262637080\\ 48.2319624355944& 63.7563267144141\\ 90.9441877431805& 33.8527464913022\\ ⋮& ⋮\end{array}\right]\\ \hfill \text{60 × 2 Matrix}\end{array}$

$\mathrm{EMST}≔\mathrm{EuclideanMinimumSpanningTree}\left(\mathrm{points}\right)$

$\mathrm{EMST}≔\mathrm{Graph\; 1:\; an\; undirected\; weighted\; graph\; with\; 60\; vertices\; and\; 59\; edge(s)}$

$\mathrm{DrawGraph}\left(\mathrm{EMST}\right)$

$\mathrm{DrawGraph}\left(\mathrm{EuclideanMinimumSpanningTree}\left(\mathrm{points}\,\mathrm{method}=\mathrm{Prim}\right)\right)$

$\mathrm{RMST}≔\mathrm{GeometricMinimumSpanningTree}\left(\mathrm{points}\,1\right)$

$\mathrm{RMST}≔\mathrm{Graph\; 2:\; an\; undirected\; weighted\; graph\; with\; 60\; vertices\; and\; 59\; edge(s)}$

$\mathrm{DrawGraph}\left(\mathrm{RMST}\right)$

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.