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

GraphTheory[GeometricGraphs]

  

GabrielGraph

  

construct Gabriel graph

 

Calling Sequence

Parameters

Options

Description

Definitions

Examples

References

Compatibility

Calling Sequence

GabrielGraph( 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 GabrielGraph(P, opts) command returns the Gabriel graph for the point set P.

• 

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

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 Gabriel graph the graph whose vertices correspond to points in P and whose edges consist of those pairs p and q from P for which the closed ball centered halfway between p and q with diameter equal to distpq contains no other points from P.

  

Formally, define the ball Bp,q to be those points rP such that distr,p2+q2distp,q2. The Gabriel graph has an edge between p and q if and only if Bp,q=.

• 

The Gabriel graph has the following relationships with other graphs:

  

The Euclidean minimum spanning tree on P is a subgraph of the Gabriel graph on P.

  

The nearest neighbor graph on P is a subgraph of the Gabriel graph on P.

  

The relative neighborhood graph on P is a subgraph of the Gabriel graph on P.

  

The Urquhart graph on P is a subgraph of the Gabriel graph on P.

  

The Gabriel graph on P is a subgraph of the Delaunay graph on P.

Examples

Generate a set of random two-dimensional points and draw a Gabriel graph.

withGraphTheory:

withGeometricGraphs:

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

(1)

GGGabrielGraphpoints

GGGraph 1: an undirected unweighted graph with 60 vertices and 105 edge(s)

(2)

DrawGraphGG

References

  

Gabriel, Kuno Ruben; Sokal, Robert Reuven (1969), "A new statistical approach to geographic variation analysis", Systematic Biology, Society of Systematic Biologists, 18(3): 259–278. doi:10.2307/2412323.

Compatibility

• 

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

• 

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

See Also

DelaunayTriangulation

GeometricGraphs