GraphTheory[RandomGraphs] - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory[RandomGraphs]

  

RandomGraph

  

generate random graph

 

Calling Sequence

Parameters

Options

Description

Examples

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 mn 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 xy 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.0p1.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 0mbinomialn,2=nn12.

• 

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

withGraphTheory:

withRandomGraphs:

GRandomGraph8,0.5

GGraph 1: an undirected unweighted graph with 8 vertices and 15 edge(s)

(1)

GRandomGraph8,10

GGraph 2: an undirected unweighted graph with 8 vertices and 10 edge(s)

(2)

GRandomGraph8,10,connected

GGraph 3: an undirected unweighted graph with 8 vertices and 10 edge(s)

(3)

IsConnectedG

true

(4)

GRandomGraph6,degree=3

GGraph 4: an undirected unweighted graph with 6 vertices and 9 edge(s)

(5)

IsRegularG

true

(6)

HRandomGraph4,1.0,weights=0...1.0

HGraph 5: an undirected weighted graph with 4 vertices and 6 edge(s)

(7)

WeightMatrixH

0.0.7749104647115020.004634224134067440.9618980808550540.7749104647115020.0.1066527701805840.4426782697754460.004634224134067440.1066527701805840.0.07817552875318370.9618980808550540.4426782697754460.07817552875318370.

(8)

HRandomGraph8,10,connected,weights=1..4

HGraph 6: an undirected weighted graph with 8 vertices and 10 edge(s)

(9)

WeightMatrixH

0110030010031020100000000300200101020000300000040200000100010410

(10)

Urand1..4:

f := proc() local x; x := U(); if x=1 then 1 else 2 end if; end proc:

HRandomGraph6,1.0,weights=f

HGraph 7: an undirected weighted graph with 6 vertices and 15 edge(s)

(11)

WeightMatrixH

022222202222220221222021222201221110

(12)

See Also

AssignEdgeWeights

GraphTheory:-IsConnected

GraphTheory:-WeightMatrix

RandomBipartiteGraph

RandomDigraph

RandomNetwork

RandomRegularGraph

RandomTournament

RandomTree