GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

Graph

 

Calling Sequence

Parameters

Options

Description

Examples

Calling Sequence

Graph(V, opts)

Graph(V, E, opts)

Graph(L, opts)

Graph(V, L, opts)

Graph(T, opts)

Graph(A, opts)

Graph(V, E, A, opts)

Graph(N, opts)

Parameters

V

-

(optional) list of vertices (integers, symbols, or strings) or integer specifying the vertices 1,2,...,V

E

-

(optional) set of edges

L

-

(optional) list or Array of neighbors

T

-

(optional) function of the form Trail(a,b,c,,...) or Trail([a,b,c,...])

A

-

(optional) adjacency Matrix (of edge weights)

N

-

(optional) procedure (a networks graph)

opts

-

(optional) zero or more options as specified below

Options

  

The opts parameter is used to specify one or more additional properties of the graph.

  

weighted or weighted=true

  

Specifies that this graph has weighted edges.

  

unweighted or weighted=false

  

Specifies that this graph has no edge weights.

  

directed or directed=true

  

Specifies that this graph has directed edges.

  

undirected or directed=false

  

Specifies that this graph has no directed edges.

  

vertexcolor=c

  

Specifies a color or list of colors to associate with the vertices in vertex order.

  

vertexpositions=p

  

Specifies coordinate positions for the vertices for use with DrawGraph.

Description

• 

The type of each argument determines what it is.  Because of this the arguments can appear in any order.

• 

A symbol can be one of directed, undirected, weighted, or unweighted. This specifies the type of the graph.  If not specified, a default is chosen depending on the type of the other inputs.

• 

An integer n specifies the number of vertices and implicitly the vertex labels 1 through n.

• 

A list V of integers, symbols or strings specifies the vertices. Each vertex must be an integer, symbol or string.

• 

A set E specifies the set of edges. An undirected edge between vertices i and j is input as a set of two vertices i,j.  A directed edge from vertex a to vertex b is input as a list a,b.  A weighted edge is input as either e,w where e is an edge (directed or undirected) and w, the edge weight, is a number (integer or decimal). Note that the vertices at the ends of either a directed or undirected edge must be distinct.

• 

An Array (or list) of lists / sets of vertices L specifies a mapping from vertices to their neighbors. Note that the mapping is an integer mapping that indicates the vertices (if the vertices are labeled as 1,2,3,...) or the location of each vertex in the vertex list V. If the graph is undirected, then the lists / sets of neighbors must be symmetric.

• 

A function T of the form Trail(a,b,c,...) or Trail([a,b,c,...]) specifies a trail of edges from a to b to c ....  By default the edges are undirected.  If the symbol directed is specified as an option then they are directed.  More than one trail can be specified.  This is often the easiest way to enter a graph interactively.

• 

A matrix A means the adjacency matrix.  A symmetric matrix is interpreted as an undirected graph unless the edge direction is stated otherwise. Likewise, a matrix of 0's and 1's is interpreted as an unweighted graph unless specified otherwise. The diagonal entries of an adjacency matrix must all be equal to 0.

• 

A procedure N means a networks graph.  This option allows conversion from a networks graph representation to the GraphTheory representation. Note, the GraphTheory package does not support multigraphs.

Examples

withGraphTheory:

Build a graph with 5 vertices and no edges.

GGraph5

GGraph 1: an undirected unweighted graph with 5 vertices and 0 edge(s)

(1)

VerticesG

1,2,3,4,5

(2)

EdgesG

(3)

Build an undirected graph with 3 vertices, all of which are connected.

GGrapha,b,b,c,c,a

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

(4)

VerticesG

a,b,c

(5)

EdgesG

a,b,a,c,b,c

(6)

DrawGraphG

Build a directed graph with 3 vertices which form a directed cycle.

GGraph1,2,2,3,3,1

GGraph 3: a directed unweighted graph with 3 vertices and 3 arc(s)

(7)

EdgesG

1,2,2,3,3,1

(8)

Va,b,c,d:

Ea,b,2,b,c,2.3,c,a,32:

GGraphV,E

GGraph 4: a directed weighted graph with 4 vertices and 3 arc(s)

(9)

WeightMatrixG

0200002.30320000000

(10)

Build a directed graph with 4 vertices which form a directed cycle.

GGrapha,b,c,d,2,3,4,1

GGraph 5: a directed unweighted graph with 4 vertices and 4 arc(s)

(11)

EdgesG

a,b,b,c,c,d,d,a

(12)

Build a undirected graph with 4 vertices by specifying a trail.

GGraphTrail1,2,3,4,1,3

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

(13)

EdgesG

1,2,1,3,1,4,2,3,3,4

(14)

GGraphdirected,Trail1,2,3,1,Trail4,5,6,4

GGraph 7: a directed unweighted graph with 6 vertices and 6 arc(s)

(15)

EdgesG

1,2,2,3,3,1,4,5,5,6,6,4

(16)

Build a undirected graph with 4 vertices by specifying an adjacency matrix.

A1Matrix0,1,1,0,1,0,0,1,1,0,0,0,0,1,0,0:

GGraphA1

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

(17)

EdgesG

1,2,1,3,2,4

(18)

GGraphdirected,A1,weighted

GGraph 9: a directed weighted graph with 4 vertices and 6 arc(s)

(19)

EdgesG,weights

1,2,1,1,3,1,2,1,1,2,4,1,3,1,1,4,2,1

(20)

A2Matrix0,1.0,2.3,0,4,0,0,3.1,0,0,0,0,0,0,0,0:

GGraphA2

GGraph 10: a directed weighted graph with 4 vertices and 4 arc(s)

(21)

EdgesG,weights

1,2,1.0,1,3,2.3,2,1,4,2,4,3.1

(22)

Convert a graph built using the legacy networks package to a GraphTheory graph.

withnetworks

acycpoly,addedge,addvertex,adjacency,allpairs,ancestor,arrivals,bicomponents,charpoly,chrompoly,complement,complete,components,connect,connectivity,contract,countcuts,counttrees,cube,cycle,cyclebase,daughter,degreeseq,delete,departures,diameter,dinic,djspantree,dodecahedron,draw,draw3d,duplicate,edges,ends,eweight,flow,flowpoly,fundcyc,getlabel,girth,graph,graphical,gsimp,gunion,head,icosahedron,incidence,incident,indegree,induce,isplanar,maxdegree,mincut,mindegree,neighbors,new,octahedron,outdegree,path,petersen,random,rank,rankpoly,shortpathtree,show,shrink,span,spanpoly,spantree,tail,tetrahedron,tuttepoly,vdegree,vertices,void,vweight

(23)

newN:

addvertex1,2,a,b,N

1,2,a,b

(24)

addedge1,2,N

e1

(25)

addedgea,b,N

e2

(26)

addedgeb,a,N

e3

(27)

GGraphN

GGraph 11: a directed unweighted graph with 4 vertices and 4 arc(s)

(28)

EdgesG

1,2,2,1,a,b,b,a

(29)

addedge1,a,weights=2,N

e4

(30)

addedge2,b,weights=3,N

e5

(31)

GGraphN

GGraph 12: a directed weighted graph with 4 vertices and 5 arc(s)

(32)

EdgesG,weights

1,2,1,1,a,2,2,b,3,a,b,1,b,a,1

(33)

See Also

Details

Digraph

DrawGraph

Edges

networks

RandomGraphs

SpecialGraphs

Trail

Vertices