RandomGraph - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

GraphTheory[RandomGraphs]

 RandomGraph
 generate random graph

 Calling Sequence RandomGraph(V,p,options) RandomGraph(V,m,options) RandomGraph(n,p,options) RandomGraph(n,m,options)

Parameters

 V - list of vertex labels n - positive integer p - numeric value between 0.0 and 1.0 m - non-negative integer options - sequence of options (see below)

Options

 • connected = truefalse
 If the option connected is specified, the graph created is connected, and hence has at least n-1 edges.
 For RandomGraph(n,m,connected), m must be at least n-1. A random tree is first created, then the remaining m-n+1 edges are
 For RandomGraph(n,p,connected), a random tree is first created then each remaining edge is present with probability p.
 • degree = nonnegint
 If the option degree=d is specified, and d-regular n vertex graph is possible, then a random d-regular graph having n vertices will be returned. Note that this option cannot be present with the directed option. This is equivalent to using the RandomRegularGraph command.
 • directed = truefalse
 If the option directed is specified, a random directed graph is chosen. This is equivalent to using the RandomDigraph command. Default value is false.
 • seed = integer or none
 Seed for the random number generator. When an integer is specified, this is equivalent to calling randomize(seed).
 • weights = range
 If the option weights=m..n is specified, where $m\le n$ are integers, the graph is a weighted graph with integer 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 graph 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 graph has datatype=anything, and if the edge from vertex i to j is not in the graph then W[i,j] = 0.

Description

 • RandomGraph(n,p) creates an undirected unweighted graph on n vertices where each possible edge is present with probability p where $0.0\le p\le 1.0$.
 • RandomGraph(n,m) creates an undirected unweighted graph on n vertices and m edges where the m edges are chosen uniformly at random. The value of m must satisfy $0\le m\le \mathrm{binomial}\left(n,2\right)=n\frac{n-1}{2}$.
 • If the first input is a positive integer n, then the vertices are labeled 1,2,...,n.  Alternatively, you may specify the vertex labels in a list.
 • This model of random graph generation, in which edges are selected with uniform probability from all possible edges in a graph on the specified vertices, is known as the Erdős–Rényi model.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{RandomGraphs}\right):$
 > $G≔\mathrm{RandomGraph}\left(8,0.5\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected graph with 8 vertices and 10 edge\left(s\right)}}$ (1)
 > $G≔\mathrm{RandomGraph}\left(8,10\right)$
 ${G}{≔}{\mathrm{Graph 2: an undirected graph with 8 vertices and 10 edge\left(s\right)}}$ (2)
 > $G≔\mathrm{RandomGraph}\left(8,10,\mathrm{connected}\right)$
 ${G}{≔}{\mathrm{Graph 3: an undirected graph with 8 vertices and 10 edge\left(s\right)}}$ (3)
 > $\mathrm{IsConnected}\left(G\right)$
 ${\mathrm{true}}$ (4)
 > $G≔\mathrm{RandomGraph}\left(6,\mathrm{degree}=3\right)$
 ${G}{≔}{\mathrm{Graph 4: an undirected graph with 6 vertices and 9 edge\left(s\right)}}$ (5)
 > $\mathrm{IsRegular}\left(G\right)$
 ${\mathrm{true}}$ (6)
 > $H≔\mathrm{RandomGraph}\left(4,1.0,\mathrm{weights}=0.0..1.0\right)$
 ${H}{≔}{\mathrm{Graph 5: an undirected weighted graph with 4 vertices and 6 edge\left(s\right)}}$ (7)
 > $\mathrm{WeightMatrix}\left(H\right)$
 $\left[\begin{array}{cccc}{0.}& {0.809734551911930}& {0.230156065952094}& {0.761731208483085}\\ {0.809734551911930}& {0.}& {0.158057578940872}& {0.580956679189321}\\ {0.230156065952094}& {0.158057578940872}& {0.}& {0.423165119881119}\\ {0.761731208483085}& {0.580956679189321}& {0.423165119881119}& {0.}\end{array}\right]$ (8)
 > $H≔\mathrm{RandomGraph}\left(8,10,\mathrm{connected},\mathrm{weights}=1..4\right)$
 ${H}{≔}{\mathrm{Graph 6: an undirected weighted graph with 8 vertices and 10 edge\left(s\right)}}$ (9)
 > $\mathrm{WeightMatrix}\left(H\right)$
 $\left[\begin{array}{cccccccc}{0}& {4}& {1}& {0}& {0}& {2}& {0}& {0}\\ {4}& {0}& {0}& {1}& {0}& {0}& {2}& {0}\\ {1}& {0}& {0}& {3}& {2}& {0}& {3}& {0}\\ {0}& {1}& {3}& {0}& {0}& {0}& {4}& {4}\\ {0}& {0}& {2}& {0}& {0}& {0}& {0}& {0}\\ {2}& {0}& {0}& {0}& {0}& {0}& {0}& {0}\\ {0}& {2}& {3}& {4}& {0}& {0}& {0}& {0}\\ {0}& {0}& {0}& {4}& {0}& {0}& {0}& {0}\end{array}\right]$ (10)
 > $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{RandomGraph}\left(6,1.0,\mathrm{weights}=f\right)$
 ${H}{≔}{\mathrm{Graph 7: an undirected weighted graph with 6 vertices and 15 edge\left(s\right)}}$ (11)
 > $\mathrm{WeightMatrix}\left(H\right)$
 $\left[\begin{array}{cccccc}{0}& {2}& {1}& {1}& {2}& {2}\\ {2}& {0}& {1}& {1}& {2}& {1}\\ {1}& {1}& {0}& {2}& {1}& {2}\\ {1}& {1}& {2}& {0}& {2}& {2}\\ {2}& {2}& {1}& {2}& {0}& {2}\\ {2}& {1}& {2}& {2}& {2}& {0}\end{array}\right]$ (12)