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

GraphTheory[RandomGraphs]

  

RandomArborescence

  

generate random arborescence

 

Calling Sequence

Parameters

Options

Description

Examples

Compatibility

Calling Sequence

RandomArborescence(V,options)

RandomArborescence(n,options)

Parameters

V

-

list of vertex labels

n

-

positive integer

options

-

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

Options

• 

maxoutdegree : integer

  

If specified, this option limits the maximum out-degree of every vertex in the arborescence.

• 

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 arborescence 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 arborescence 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 arborescence has datatype=anything, and if the edge from vertex i to j is not in the graph then W[i,j] = 0.

Description

• 

The RandomArborescence(n) command creates a random arborescence on n vertices. This is a connected directed acyclic graph with n-1 edges. If the first input n is a positive integer, the vertices are labeled 1,2,...,n. Alternatively you can specify the vertex labels in a list.

• 

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

• 

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

Examples

withGraphTheory:

withRandomGraphs:

TRandomArborescence10

TGraph 1: a directed unweighted graph with 10 vertices and 9 arc(s)

(1)

TRandomArborescence10,weights=1..9

TGraph 2: a directed weighted graph with 10 vertices and 9 arc(s)

(2)

IsArborescenceT

true

(3)

WeightMatrixT

0000000000000000000000000000000000008000008000000070000005000000000000020000000000000500000003300050

(4)

TRandomArborescence100

TGraph 3: a directed unweighted graph with 100 vertices and 99 arc(s)

(5)

DegreeSequenceT

2,1,2,2,1,2,1,2,1,1,1,2,2,9,3,1,3,1,2,2,1,2,3,1,1,1,2,1,2,2,1,1,1,1,5,1,2,1,2,2,2,1,1,2,2,1,1,3,6,1,2,4,1,4,4,1,4,1,5,1,4,3,2,2,3,1,5,1,3,2,1,1,1,2,2,4,4,1,1,1,1,1,1,3,2,1,3,1,3,1,1,1,2,2,4,1,1,1,1,2

(6)

TRandomArborescence100,maxoutdegree=4

TGraph 4: a directed unweighted graph with 100 vertices and 99 arc(s)

(7)

maxOutDegreeT

4

(8)

Compatibility

• 

The GraphTheory[RandomGraphs][RandomArborescence] command was introduced in Maple 2019.

• 

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

See Also

AssignEdgeWeights

GraphTheory:-IsArborescence

GraphTheory:-WeightMatrix

RandomBipartiteGraph

RandomDigraph

RandomGraph

RandomNetwork

RandomTournament