GraphTheory[GeometricGraphs] - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GeometricGraphs : GraphTheory/GeometricGraphs/EuclideanMinimumSpanningTree

GraphTheory[GeometricGraphs]

  

EuclideanMinimumSpanningTree

  

construct a Euclidean minimum spanning tree

  

GeometricMinimumSpanningTree

  

construct a minimum spanning tree for specified norm

 

Calling Sequence

Parameters

Options

Description

Definitions

Examples

Compatibility

Calling Sequence

EuclideanMinimumSpanningTree( P, opts )

GeometricMinimumSpanningTree( P, norm, opts )

Parameters

P

-

Matrix or list of lists representing set of points

norm

-

positive number, infinity, or Euclidean

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.

  

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.

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 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].

Definitions

• 

Let P be a set of points in n dimensions, let p and q be arbitrary points from P, and let distp,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 distp,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 ρpq.

• 

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.

withGraphTheory:

withGeometricGraphs:

pointsLinearAlgebra:-RandomMatrix60,2,generator=0..100.,datatype=float8

(1)

EMSTEuclideanMinimumSpanningTreepoints

EMSTGraph 1: an undirected weighted graph with 60 vertices and 59 edge(s)

(2)

DrawGraphEMST

DrawGraphEuclideanMinimumSpanningTreepoints,method=Prim

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

RMSTGeometricMinimumSpanningTreepoints,1

RMSTGraph 2: an undirected weighted graph with 60 vertices and 59 edge(s)

(3)

DrawGraphRMST

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.

See Also

GeometricGraphs

GraphTheory[MinimalSpanningTree]