Introduction to Maple’s Networks Package

(Back to MM322 homepage)

(Back to MM322 software page)

Maple has a built-in graph theory package, called ‘networks’. This needs to be loaded at the beginning of any Maple graph theory session using the command

with(networks):

 

Sets and Lists

In order to be able correctly to define graphs, simple graphs, digraphs and simple digraphs in Maple, it is necessary to understand the difference between sets and lists in Maple. A set in Maple is the same as it is in mathematics; that is, an unordered collection of elements where any repeats are ignored. Also as in mathematics, the elements of a set in Maple are enclosed between braces (‘curly brackets’). Thus, in Maple, the input

A:={1,3,4,3,2,3,2};

returns the set A = {1, 2, 3, 4}.

A list by contrast is an ordered collection of elements where any repeats are considered as distinct elements. The elements of a list are enclosed between square brackets. Thus the Maple input

B:=[1,3,4,3,2,3,2];

returns the list B = [1, 3, 4, 3, 2, 3, 2].

 

Defining graphs and digraphs

To define a graph in Maple, use the command

graph(vertexset,edge-set-or-list):

where   vertexset is a set of vertex names

and     edge-set-or-list is either a set or a list whose elements are either sets of vertex pairs or lists of vertex pairs.

If edge-set-or-list is a list then repeated edges are allowed but if edge-set-or-list is a set then any repeats are ignored.

A set of vertex pairs {v1, v2} defines an undirected edge joining the two vertices v1 and v2. A list of vertex pairs [v1, v2] defines a directed edge from the vertex v1 to v2.

Maple allows graphs which contain a mixture of undirected and directed edges.

 

Examples

Let G1, G2, G3 and G4, be the graphs and digraphs whose diagrams are given below.

                 

         G1                          G2                         G3                         G4

 

These graphs and digraphs can be defined in Maple as follows.

G1:=graph({v1,v2,v3,v4},{{v1,v2},{v2,v3},{v3,v4},{v1,v4},{v1,v3}}):

G2:=graph({v1,v2,v3,v4},[{v1,v2},{v2,v3},{v3,v3},{v1,v4},{v1,v4}]):

G3:=graph({v1,v2,v3,v4},{[v2,v1],{v2,v3},[v4,v3],[v4,v1],{v1,v3}}):

G4:=graph({v1,v2,v3,v4},[{v1,v2},[v3,v2],[v4,v3],{v1,v4},{v1,v4}]):

 

Maple has several pre-defined graphs (see the handout ‘Examples of graphs’):

G:=petersen(): defines G to be Petersen’s graph

G:=tetrahedron(): defines G to be the tetrahedron graph

G:=octahedron(): defines G to be the octahedron graph

G:=icosahedron(): defines G to be the icosahedron graph

G:=dodecahedron(): defines G to be the dodecahedron graph.

 

Various families of graphs are also definable within Maple.

G:=void(n): defines G to be the null graph with n vertices.

G:=void(vertexset): defines G to be the null graph with vertex set equal to the specified vertexset.

G:=complete(n): defines G to be the complete graph with n vertices, Kn.

G:=complete(vertexset): defines G to be the complete graph with vertex set equal to the specified vertexset.

G:=complete(m,n): defines G to be the complete bipartite graph Km,n.

G:=cube(n): defines G to be the hypercube graph with 2n vertices.

G:=cycle(n): defines G to be the cycle graph with n vertices, Cn.

 

Maple can also create ‘random graphs’ in a variety of ways.

G:=random(n): defines a simple graph G with n vertices and where the probability that any two vertices are joined by an edge is 1/2.

G:=random(n,m): defines a simple graph G with n vertices, m edges and where all pairs of vertices are equally likely to joined by an edge.

G:=random(n,prob=x): defines a simple graph G with n vertices and where the probability that any two vertices are joined by an edge is x (where 0 £ x £ 1).

 

Vertices and edges

Let G be a graph or digraph defined in Maple. Then

vertices(G); returns the vertex set of G

edges(G); returns the set of edges of G (even if the edges have been defined as a list in order to include multiple edges).

ends(ej,G); returns the ‘ends’ of an edge ej as a pair of vertices (in a set or list as appropriate).

 

Vertices and/or edges may be added to or deleted from a graph G previously defined in Maple as follows.

addvertex(v1,v2,...vn,G): adds the vertices v1, v2, ..., vn to the graph G.

addedge({vi,vj},G): adds the edge {vi, vj} to the graph G.

addedge(edge-set-or-list,G): adds the edges in edge-set-or-list to the graph G. Here edge-set-or-list is a set or a list of vertex pairs.

delete(vertex-set,G): deletes the vertices in vertex-set from the graph G.

delete(edge-set,G): deletes the edges in edge-set from the graph G.

 

Example

Suppose we wish to define a graph G whose diagram is shown below.

Instead of defining all 9 vertices and 12 edges, we could begin by defining the cycle graph C8 and then add vertex 9 and finally add the remaining edges as follows.

G:=cycle(8):

addvertex(9,G):

addedge({{2,9},{4,9},{8,9},{5,7}},G):

 

Drawing graphs

If G is a Maple graph the command draw(G); draws G by placing the vertices at equal intervals around a circle. However, this may not give the best diagram of G so Maple has some options which can be used to give alternative diagrams.

draw(Concentric(vertex-list),G);

places the vertices in the list vertex-list around one circle and the remaining vertices around a concentric circle outside the first.

draw(Concentric(vertex-list1,vertex-list2),G);

places the vertices of G in three concentric circles with the vertices in vertex-list1 around the inner circle, those in vertex-list2 around the middle circle and any remaining vertices around the outer circle.

draw(Linear(vertex-list),G);

places the vertices in the list vertex-list in a vertical line and the remaining vertices in a second line to the right of the first.

draw(Linear(vertex-list1,vertex-list2),G);

places the vertices in the list vertex-list1 in a vertical line, the vertices in vertex-list2 in a second line to the right and the remaining vertices in a third line to the right of the first two.

 

Example

If we define G:=complete(6): then

draw(G); and draw(Concentric([1,3,5]),G);

will produce the following diagrams of K6.

           

      draw(G);     draw(Concentric([1,3,5]),G);

 

Summary of some other Maple commands in the Networks package

adjacency(G);

returns the adjacency matrix of a graph G.

incidence(G);

returns the incidence matrix of G.

incident(vertex-set,G);

finds those edges in G incident with a vertex in vertex-set1.

connect(vertex-set1,vertex-set2,G);

joins each vertex in vertex-set1 to each vertex in vertex-set2 with an edge.

degreeseq(G);

returns the degree sequence of G.

girth(G);

finds the girth of G; that is, the length of the shortest cycle in G.

girth(G,anyname);

finds the girth of G and assigns the name anyname to the edges of a shortest cycle.
Then the command anyname; will return the list of edges in a shortest cycle.

counttrees(G);

returns the number of spanning trees in a connected graph G.

components(G);

returns the components of G as a set of subsets of the vertex set of G; that is as a partition of the vertex set of G.

(Back to MM322 homepage)

(Back to MM322 software page)