GraphTheory[RandomGraphs] - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : RandomGraphs : GraphTheory/RandomGraphs/RandomTree

GraphTheory[RandomGraphs]

  

RandomTree

  

generate random tree

 

Calling Sequence

Parameters

Options

Description

Examples

Calling Sequence

RandomTree(V,options)

RandomTree(n,options)

RandomTree(V,degree<d,options)

RandomTree(n,degree<d,options)

Parameters

V

-

list of vertex labels

n

-

positive integer

d

-

positive integer

options

-

(optional) equation(s) of the form option=value where option is one of seed or weights

Options

• 

seed : integer or none

  

Seed for the random number generator. When an integer is specified, this is equivalent to calling randomize(seed).

• 

weights : range or procedure

  

If the option weights=m..n is specified, where mn are integers, the tree is a weighted graph with edge weights chosen from [m,n] uniformly at random.  The weight matrix W in the graph has datatype=integer, and if the edge from vertex i to j is not in the graph then W[i,j] = 0.

  

If the option weights=x..y where xy are decimals is specified, the tree is a weighted graph with numerical edge weights chosen from [x,y] uniformly at random.  The weight matrix W in the graph has datatype=float[8], that is, double precision floats (16 decimal digits), and if the edge from vertex i to j is not in the graph then W[i,j] = 0.0.

  

If the option weights=f where f is a function (a Maple procedure) that returns a number (integer, rational, or decimal number), then f is used to generate the edge weights.  The weight matrix W in the tree has datatype=anything, and if the edge from vertex i to j is not in the graph then W[i,j] = 0.

Description

• 

The RandomTree(n)  command creates a random tree on n vertices. This is an undirected connected graph with n-1 edges. If the first input n is a positive integer, the vertices are labeled 1,2,...,n. Alternatively you may specify the vertex labels in a list.

• 

Starting with the empty undirected graph T on n vertices, edges are chosen uniformly at random and inserted into T if they do do not create a cycle.  This is repeated until T has n-1 edges.

• 

The option degree<d or degreed limits the maximum degree of every vertex in the tree.

• 

The random number generator used can be seeded using the seed option or the randomize function.

Examples

withGraphTheory&colon;

withRandomGraphs&colon;

TRandomTree10

TGraph 1: an undirected unweighted graph with 10 vertices and 9 edge(s)

(1)

TRandomTree10&comma;weights=1..9

TGraph 2: an undirected weighted graph with 10 vertices and 9 edge(s)

(2)

IsTreeT

true

(3)

WeightMatrixT

0300000000300000305000099000000090040070009000000000040004000300000000000004000705070000000000000700

(4)

TRandomTree100

TGraph 3: an undirected unweighted graph with 100 vertices and 99 edge(s)

(5)

MaximumDegreeT

7

(6)

TRandomTree100&comma;degree<4

TGraph 4: an undirected unweighted graph with 100 vertices and 99 edge(s)

(7)

MaximumDegreeT

3

(8)

See Also

AssignEdgeWeights

GraphTheory:-IsTree

GraphTheory:-WeightMatrix

RandomBipartiteGraph

RandomDigraph

RandomGraph

RandomNetwork

RandomTournament