Graph theory in MAPLE

This worksheet will explore some of the things MAPLE can do in graph theory. The purpose is just to get accustomed to some graph-theoretical computations and constructions which MAPLE can do.

Each command has at least one example/ Question and a Problem associated to it. Solve each problem using maple.

sm342_2.mws, 1-2000

>

> with(networks);

[acycpoly, addedge, addvertex, adjacency, allpairs,...
[acycpoly, addedge, addvertex, adjacency, allpairs,...
[acycpoly, addedge, addvertex, adjacency, allpairs,...
[acycpoly, addedge, addvertex, adjacency, allpairs,...
[acycpoly, addedge, addvertex, adjacency, allpairs,...

>

An acyclic graph is a graph with no cycles. A tree is a connected acyclic graph.

Question : How many acyclic graphs does the complete graph on 4 vertices (pictured below) have?
Answer: 38. (See MAPLE computation below.)

acycpoly returns the acyclicity polynomial in variable p, which gives the probability that G is acyclic when each edge operates with probability p

Problem : How many acyclic graphs does the complete graph on 3 vertices have?

Here's how to solve the first question in MAPLE:

> G:=complete(4):
acycpoly(G,p);
ans:=acycpoly(G,1/2) * 2^nops(edges(G)); # number of acyclic subgraphs

-(-1+p)^3*(3*p+6*p^2+6*p^3+1)

ans := 38

>

Two vertices of a graph are said to be adjacent if one or more edges connect them. The adjacency matrix for a graph is matrix whose rows and columns are indexed by the vertices (in address order) and whose i-j th entry is the number of edges from vertex i to vertex j.

Question : What is the adjacency matrix for the complete graph on 4 vertices (pictured below)?
Answer: (See MAPLE computation below.)

adjacency(G) constructs an ajacency matrix for the graph G.

Problem : What is the adjacency matrix for the complete graph on 3 vertices?

Here's how to solve the first question in MAPLE:

> G:=complete(4):
draw(G);
ans:=adjacency(G);

[Maple Plot]

ans := matrix([[0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 0...

>

Question : Can you draw the graph obtained by adding 2 vertices onto the complete graph on 4 vertices, and an edge from

one vertex of the original complete graph to one of the 2 new vertices?

Answer: (See below).

addvertex : adds one or more vertices to a graph. The vertex names used are returned as an expression sequence.

addedge : add one or more edges to a graph by creating new edges for the specified sets or lists of vertices. An expression sequence of the names used for the new edges is returned.

Problem : Draw the graph obtained by adding 1 vertix onto the complete graph on 3 vertices, and an edge from one vertex of the original complete graph to the new vertex.

Here's how to solve the first question in MAPLE:

> G:=complete(4):
draw(G);
addvertex({a,b},G):
addedge([1,a],G);
vertices(G);
draw(G);

[Maple Plot]

e7

{1, 2, 3, 4, a, b}

[Maple Plot]

>

Question : What is the distance between vertex 6 and vertex 8 (in the picture below) in the Pedersen graph?

Answer: 2 (see below).

allpairs is is an implementation of Floyd's allpairs shortest path algorithm.
The result, T, is a table of distances between any two vertices. Thus T[u,v] is the shortest distance from u to v.
The optional extra parameter (eg. parents) is used to supply a name for a table of ancestors. Thus parents[u,v] is the ancestor of v in the shortest path tree rooted at u.
Edge weights are assumed to be lengths or distances. Undirected edges are assumed to be bidirectional. Edge weights must be non-negative.

Problem : What is the largest distance between two vertices in a cyclic graph on 10 vertices? (Hint: Use the command G:=cyclic(10); in place of G:=pedersen(); below.)

Here's how to solve the first question in MAPLE:

> G := petersen():
draw(G);
T := allpairs(G,p):
T[1,3]; # distance between outer vertices
ans:=T[6,8];
#distance between 2 inner vertices

[Maple Plot]

2

ans := 2

> G := cycle(5):
draw(G);
T := allpairs(G,p):
T[1,3]; # the distance
p[1,3]; # the parent of 3 in the tree rooted at 1.
addedge([1,3],G);
draw(G);
T := allpairs(G,p):
T[1,3]; # the distance

[Maple Plot]

2

2

e6

[Maple Plot]

1

>

Question : What is the characteristic polynomial for the adjacency matrix for the complete graph on 4 vertices (pictured below)?
Answer: (See MAPLE computation below.)

charpoly computes the characteristic polynomial of the adjacency matrix of G expressed as a polynomial in x.

Problem : What is the characteristic polynomial for the adjacency matrix for the complete graph on 3 vertices?

Here's how to solve the first question in MAPLE:

> G:=complete(4):
ans:=charpoly(G,x);

ans := x^4-6*x^2-8*x-3

>

>

Question : What is the chromatic polynomial of the complete graph on 4 vertices?
Answer: (See MAPLE computation below.)

chrompoly returns the chromatic polynomial of the graph G as a polynomial in lambda. The value of this polynomial gives the number of proper vertex-colorings of G using lambda colors.

Problem : What is the chromatic polynomial of the complete graph on 3 vertices?

Here's how to solve the first question in MAPLE:

> G:=complete(4):
draw(G);
ans:=chrompoly(G,x);

[Maple Plot]

ans := x*(x-1)*(x-2)*(x-3)

> G:=petersen(4):
draw(G);
chrompoly(G,x);

[Maple Plot]

x*(x-1)*(x-2)*(x^7-12*x^6+67*x^5-230*x^4+529*x^3-81...

>

Question : What is the complement of the cyclic graph on 5 vertices in the complete graph on 5 vertices?

Answer: the Star of David. (See below.)

complement returns the complement of a graph. If one argument is used, then the complement is relative to the complete graph on the same number of vertices. If a second argument is given then the complement is relative to the given graph.

Problem : What is the complement of one vertex (no edges) in the complete graph on 5 vertices?

Here's how to solve the first question in MAPLE:

> draw(complete(5));
G := cycle(5):
draw(G);
H := complement(G):
draw(H);

[Maple Plot]

[Maple Plot]

[Maple Plot]

>

Question: Can you draw the complete graph on 10 vertices?

Answer: See MAPLE graph below.

complete generates various types of complete graphs. The number of arguments indicates the number of parts. Each part is specified by an integer indicating the number of vertices in that part. For example a complete bipartite graph is specified as complete(m,n) .

Problem : Can you draw the complete bipartite graph on 6 vertices, 3 in one part and 3 in the other?

Here's how to solve the first question in MAPLE:

> G := complete(10):
draw(G);

[Maple Plot]

> H := complete(2,3):
draw(H);

[Maple Plot]

> H := complete(2,3,3):
draw(H);

[Maple Plot]

>

Question : Draw a random graph having 12 vertices and 6 edges. How many connected components does it have?

Answer: See MAPLE computation below.

components : components of the graph G are returned as a set of sets. The number of sets indicates the number of components while the elements of the sets indicate the vertices belonging to each component. If a second argument of the formroot=v is given, then only the single component containing the vertex v is constructed. A set of subgraphs corresponding to each component can be constructed by mapping induce() onto the set of components.

Problem : Draw a random graph having 6 vertices and 6 edges. How many connected components does it have?

Here's how to solve the first question in MAPLE:

> G := random(12,6):
draw(G);
components(G);
ans:=nops(components(G));

[Maple Plot]

{{4, 10}, {1}, {12}, {2, 6, 11}, {3, 5, 9}, {7, 8}}...

ans := 6

> components(G,root=5);

{3, 5, 9}

>

>

>


Last updated 5-1-2003 by wdj