GraphTheory[RandomGraphs] - Maple Programming Help

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

GraphTheory[RandomGraphs]

 RandomRegularGraph
 generate a random regular graph

 Calling Sequence RandomRegularGraph(n,d,options)

Parameters

 n - positive integer or list of vertices d - nonnegative integer options - (optional) equation(s) of the form option=value where option is one of connected or seed

Options

 • connected : truefalse
 If specified, indicates that the generated graph should be connected.
 • seed : integer or none
 Seed for the random number generator. When an integer is specified, this is equivalent to calling randomize(seed).

Description

 • RandomRegularGraph(n,d) creates a d-regular undirected unweighted graph on n vertices. n and d cannot both be odd and d must satisfy $d.
 • If the option connected is specified, the graph created will be connected. n and d must then satisfy n = 1 and d = 0, or n = 2 and d = 1, or $n>2$ and $d>1$ as well as the above.
 • For RandomRegularGraph(n,d,connected), a random tree with maximum $\mathrm{degree}\le d$ is first created.
 • For generating weighted graphs use weights = f and see AssignEdgeWeights for details about f.
 • 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):$
 > $R≔\mathrm{RandomRegularGraph}\left(100,80,\mathrm{connected}\right)$
 ${R}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 100 vertices and 4000 edge\left(s\right)}}$ (1)
 > $\mathrm{IsRegular}\left(R\right)$
 ${\mathrm{true}}$ (2)
 > $\mathrm{IsConnected}\left(R\right)$
 ${\mathrm{true}}$ (3)
 > $R≔\mathrm{RandomRegularGraph}\left(\left[\mathrm{seq}\left("a".."j"\right)\right],3,\mathrm{weights}=-10..10\right)$
 ${R}{≔}{\mathrm{Graph 2: an undirected weighted graph with 10 vertices and 15 edge\left(s\right)}}$ (4)
 > $\mathrm{WeightMatrix}\left(R\right)$
 $\left[\begin{array}{cccccccccc}{0}& {-1}& {0}& {0}& {0}& {3}& {0}& {9}& {0}& {0}\\ {-1}& {0}& {0}& {9}& {0}& {0}& {0}& {0}& {-7}& {0}\\ {0}& {0}& {0}& {0}& {0}& {0}& {7}& {-10}& {0}& {6}\\ {0}& {9}& {0}& {0}& {8}& {0}& {0}& {0}& {-7}& {0}\\ {0}& {0}& {0}& {8}& {0}& {-10}& {-6}& {0}& {0}& {0}\\ {3}& {0}& {0}& {0}& {-10}& {0}& {0}& {0}& {-2}& {0}\\ {0}& {0}& {7}& {0}& {-6}& {0}& {0}& {0}& {0}& {-7}\\ {9}& {0}& {-10}& {0}& {0}& {0}& {0}& {0}& {0}& {-6}\\ {0}& {-7}& {0}& {-7}& {0}& {-2}& {0}& {0}& {0}& {0}\\ {0}& {0}& {6}& {0}& {0}& {0}& {-7}& {-6}& {0}& {0}\end{array}\right]$ (5)
 > $f≔\mathrm{RandomTools}:-\mathrm{Generate}\left(\mathrm{float}\left(\mathrm{range}=0.1..1,\mathrm{digits}=2\right),\mathrm{makeproc}=\mathrm{true}\right):$
 > $R≔\mathrm{RandomRegularGraph}\left(10,3,\mathrm{weights}=f\right)$
 ${R}{≔}{\mathrm{Graph 3: an undirected weighted graph with 10 vertices and 15 edge\left(s\right)}}$ (6)
 > $\mathrm{WeightMatrix}\left(R\right)$
 $\left[\begin{array}{cccccccccc}{0}& {0}& {0.33}& {0}& {0}& {0}& {0.42}& {0}& {0}& {0.95}\\ {0}& {0}& {0.33}& {0}& {0}& {0}& {0}& {0}& {0.27}& {0.25}\\ {0.33}& {0.33}& {0}& {0}& {0}& {0}& {0.64}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}& {0}& {0}& {0}& {0.54}& {0.74}& {0.83}\\ {0}& {0}& {0}& {0}& {0}& {0.40}& {0.54}& {0.74}& {0}& {0}\\ {0}& {0}& {0}& {0}& {0.40}& {0}& {0}& {0.70}& {0.47}& {0}\\ {0.42}& {0}& {0.64}& {0}& {0.54}& {0}& {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0.54}& {0.74}& {0.70}& {0}& {0}& {0}& {0}\\ {0}& {0.27}& {0}& {0.74}& {0}& {0.47}& {0}& {0}& {0}& {0}\\ {0.95}& {0.25}& {0}& {0.83}& {0}& {0}& {0}& {0}& {0}& {0}\end{array}\right]$ (7)
 > $U≔\mathrm{rand}\left(1..4\right):$
 > f := proc() local x; x := U(); if x=1 then 1 else 2 end if; end proc:
 > $H≔\mathrm{RandomRegularGraph}\left(10,3,\mathrm{connected},\mathrm{weights}=f\right)$
 ${H}{≔}{\mathrm{Graph 4: an undirected weighted graph with 10 vertices and 15 edge\left(s\right)}}$ (8)
 > $\mathrm{WeightMatrix}\left(H\right)$
 $\left[\begin{array}{cccccccccc}{0}& {0}& {2}& {2}& {1}& {0}& {0}& {0}& {0}& {0}\\ {0}& {0}& {2}& {1}& {0}& {0}& {1}& {0}& {0}& {0}\\ {2}& {2}& {0}& {0}& {0}& {0}& {0}& {0}& {2}& {0}\\ {2}& {1}& {0}& {0}& {0}& {0}& {1}& {0}& {0}& {0}\\ {1}& {0}& {0}& {0}& {0}& {0}& {0}& {2}& {2}& {0}\\ {0}& {0}& {0}& {0}& {0}& {0}& {0}& {2}& {2}& {2}\\ {0}& {1}& {0}& {1}& {0}& {0}& {0}& {0}& {0}& {2}\\ {0}& {0}& {0}& {0}& {2}& {2}& {0}& {0}& {0}& {2}\\ {0}& {0}& {2}& {0}& {2}& {2}& {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {0}& {0}& {2}& {2}& {2}& {0}& {0}\end{array}\right]$ (9)