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
What kind of issue would you like to report? (Optional)