generate random arborescence
list of vertex labels
(optional) equation(s) of the form option=value where option is one of maxoutdegree, seed, or weights
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 m≤n 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 x≤y 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, 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.
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.
T ≔ RandomArborescence⁡10
T≔Graph 1: a directed graph with 10 vertices and 9 arc(s)
T ≔ RandomArborescence⁡10,weights=1..9
T≔Graph 2: a directed weighted graph with 10 vertices and 9 arc(s)
T ≔ RandomArborescence⁡100
T≔Graph 3: a directed graph with 100 vertices and 99 arc(s)
T ≔ RandomArborescence⁡100,maxoutdegree=4
T≔Graph 4: a directed graph with 100 vertices and 99 arc(s)
The GraphTheory[RandomGraphs][RandomArborescence] command was introduced in Maple 2019.
For more information on Maple 2019 changes, see Updates in Maple 2019.
Download Help Document