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\le 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\le 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[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.

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.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{with}\left(\mathrm{RandomGraphs}\right)\:$

$T≔\mathrm{RandomArborescence}\left(10\right)$

$T≔\mathrm{Graph\; 1:\; a\; directed\; graph\; with\; 10\; vertices\; and\; 9\; arcs}$

$T≔\mathrm{RandomArborescence}\left(10\,\mathrm{weights}=1..9\right)$

$T≔\mathrm{Graph\; 2:\; a\; directed\; weighted\; graph\; with\; 10\; vertices\; and\; 9\; arcs}$

$\mathrm{IsArborescence}\left(T\right)$

$\mathrm{true}$

$\mathrm{WeightMatrix}\left(T\right)$

$\left[\begin{array}{cccccccccc}0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 8& 0& 0& 0\\ 0& 0& 8& 0& 0& 0& 0& 0& 0& 0\\ 7& 0& 0& 0& 0& 0& 0& 5& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 2& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 5& 0& 0& 0& 0\\ 0& 0& 0& 3& 3& 0& 0& 0& 5& 0\end{array}\right]$

$T≔\mathrm{RandomArborescence}\left(100\right)$

$T≔\mathrm{Graph\; 3:\; a\; directed\; graph\; with\; 100\; vertices\; and\; 99\; arcs}$

$\mathrm{DegreeSequence}\left(T\right)$

$\left[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\right]$

$T≔\mathrm{RandomArborescence}\left(100\,\mathrm{maxoutdegree}=4\right)$

$T≔\mathrm{Graph\; 4:\; a\; directed\; graph\; with\; 100\; vertices\; and\; 99\; arcs}$

$\max \left(\mathrm{OutDegree}\left(T\right)\right)$

$4$

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

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