COMPSCI 5004
Answer All 3 Questions
This examination paper is worth a total of 60 marks
There are 3 questions, worth 26, 12 and 22 marks respectively
Summer Diet 1 Continued Overleaf/
1. A graph is an abstract data type (ADT) which consists of a set of labelled points, or
vertices and a set of pairs of vertices, called edges. For any edge (vi, vj), the label of
vertex vi is smaller than the label of vertex vj.
For example, the first graph (i) in the illustration below has vertices which are labelled
using characters ‘a’, ‘b’, ‘c’, ‘d’ and ‘f’. The vertex set is {v1, v2, v3, v4, v5} and the
edge set is {e1, e2, e3, e4} where e1 is (v1, v2), e2 is (v2, v3), e3 is (v2, v4) and e4 is
(v4, v5).. Graph (ii) is the result of adding a new vertex and a new edge. Graph (iii) is
the result of an attempt to add a new vertex with a label identical to that of an existing
vertex, and graph (iv) is the result of deleting a vertex. Note that if a vertex is deleted,
all edges associated with that vertex are deleted.
(i)
Add new vertex
v6 with label g
Add new edge
(v3, v6)
v6
v2
v5
v4
v3
v1
b
a
c
d
f
g
Delete vertex v4
v6
v2
v5
v3
v1
b
a
c
f
g
(ii)
v2
v4
v3
v1
b
a
c
d
v5 f
Add new
vertex
v7 with label b
(no effect)
v6
v2
v5
v4
v3
v1
b
a
c
d
f
g
(iii) (iv)
Summer Diet 2 Continued Overleaf/
Note that it is not possible to:
– add a new vertex to a graph whose label is the same as that for a vertex
already in the graph,
– remove a vertex v that is not in the graph (even if the graph contains a vertex
with the same label as v),
– add an edge between vertices that have not been added to the graph,
– add an edge if it already exists in the graph,
– remove an edge that is not in the graph.
Box 1 contains a Java interface for a simplified graph, Graph (whose vertices can have
labels of any comparable type F). The interface refers to classes Vertex and
Edge which define a vertex of type F and an edge of type F respectively. Note that
if e=(v1,v2) we say that e contains v1 and v2.
public interface Graph>
{ public boolean addEdge (Edge e);
// add edge e to graph g if its vertices are already in g
// and e doesn’t already exist in g
// return true if successful and false otherwise
public boolean addVertex (Vertex v);
// Add vertex v to graph g if g doesn’t already contain v
// or any vertex with the same label as v
// return true if successful and false otherwise
public boolean deleteEdge (Edge e);
// delete edge edge if it is present in graph
// return true if successful and false otherwise
public boolean deleteVertex (Vertex v);
// delete vertex v if it is present in graph, and all edges that contain v
// return true if successful and false otherwise
}
