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/RelativeNeighborhoodGraph

GraphTheory[GeometricGraphs]

  

RelativeNeighborhoodGraph

  

construct a relative neighbor graph

 

Calling Sequence

Parameters

Options

Description

Definition

Examples

References

Compatibility

Calling Sequence

RelativeNeighborhoodGraph( P, opts )

Parameters

P

-

Matrix or list of lists representing set of points

opts

-

(optional) one or more options as specified below

Options

• 

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 Euclidean distance between points. The default is false.

Description

• 

The RelativeNeighborhoodGraph(P,opts) command returns a relative neighbor graph for the point set P.

• 

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

Definition

• 

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 relative neighborhood graph is the undirected graph whose vertices correspond to the points in P and in which vertices p and q share an edge if there does not exist any rP such that distp&comma;r<distp&comma;q and distq&comma;r<distp&comma;q.

• 

It 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 relative neighborhood graph on P is a subgraph of the Gabriel graph on P.

Examples

Generate a set of random two-dimensional points.

withGraphTheory&colon;

withGeometricGraphs&colon;

pointsLinearAlgebra:-RandomMatrix60&comma;2&comma;generator=0..100.&comma;datatype=float8

(1)

RNGRelativeNeighborhoodGraphpoints

RNGGraph 1: an undirected unweighted graph with 60 vertices and 65 edge(s)

(2)

DrawGraphRNG

References

  

Supowit, K. J. (1983), "The relative neighborhood graph, with an application to minimum spanning trees", J. ACM, 30 (3): 428–448, doi:10.1145/2402.322386.

Compatibility

• 

The GraphTheory[GeometricGraphs][RelativeNeighborhoodGraph] command was introduced in Maple 2020.

• 

For more information on Maple 2020 changes, see Updates in Maple 2020.

See Also

GeometricGraphs