GraphTheory[RandomGraphs] - Maple Programming Help

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

GraphTheory[RandomGraphs]

 RandomArborescence
 generate random arborescence

 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 $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.

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

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{RandomGraphs}\right):$
 > $T≔\mathrm{RandomArborescence}\left(10\right)$
 ${T}{≔}{\mathrm{Graph 1: a directed unweighted graph with 10 vertices and 9 arc\left(s\right)}}$ (1)
 > $T≔\mathrm{RandomArborescence}\left(10,\mathrm{weights}=1..9\right)$
 ${T}{≔}{\mathrm{Graph 2: a directed weighted graph with 10 vertices and 9 arc\left(s\right)}}$ (2)
 > $\mathrm{IsArborescence}\left(T\right)$
 ${\mathrm{true}}$ (3)
 > $\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]$ (4)
 > $T≔\mathrm{RandomArborescence}\left(100\right)$
 ${T}{≔}{\mathrm{Graph 3: a directed unweighted graph with 100 vertices and 99 arc\left(s\right)}}$ (5)
 > $\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]$ (6)
 > $T≔\mathrm{RandomArborescence}\left(100,\mathrm{maxoutdegree}=4\right)$
 ${T}{≔}{\mathrm{Graph 4: a directed unweighted graph with 100 vertices and 99 arc\left(s\right)}}$ (7)
 > $\mathrm{max}\left(\mathrm{OutDegree}\left(T\right)\right)$
 ${4}$ (8)

Compatibility

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