1. Execute breadth-first search and depth-first search on the following graph.  Start at vertex a and handle neighbours in alphabetical order.

(a) Provide the ordering of the vertices as they are visited by a BFS. Your answer

should be a string σ − 1 (1)σ − 1 (2) . . . σ − 1 (16) without separators.

[0:15h expected time]  [6 marks]

(b) List the neighbours of f in the BFS-tree in alphabetic order.

[0:01h expected time]  [1 mark] (c) List the neighbours of g in the BFS-tree in alphabetic order.

[0:01h expected time]  [1 mark] (d) List the neighbours of j in the BFS-tree in alphabetic order.

[0:01h expected time]  [1 mark] (e) List the neighbours of k in the BFS-tree in alphabetic order.

[0:01h expected time]  [1 mark]

(f) Provide the ordering of the vertices as they are visited by a DFS.

[0:15h expected time]  [6 marks]

(g) List the neighbours of f in the DFS-tree in alphabetic order.

[0:01h expected time]  [1 mark]

(h) List the neighbours of g in the DFS-tree in alphabetic order.

[0:01h expected time]  [1 mark] (i) List the neighbours of j in the DFS-tree in alphabetic order.

[0:01h expected time]  [1 mark] (j) List the neighbours of k in the DFS-tree in alphabetic order.

[0:01h expected time]  [1 mark]

2.  Consider the function Magic, whose pseudocode is illustrated in Algorithm 1.  The algorithm takes a graph as an input and outputs either true or false. The algorithm also uses a global array p that holds a Boolean value for every v - V and a global integer variable c.

input  : graph G = (V, E).

output: either true or false

function Magic (G)

for v - V do p[v] ·false;

for v - V do

if ! p[v] then

c · 0;

subMagic (G, v);

if c == 1 then

    return false

return true

procedure subMagic (G, w)

p[w] ·true;

c · c + 1;

if c == 2 then c · 0;

for ew, u} - E do

   if ! p[u] then subMagic (G, u);

Algorithm 1: What am I computing?

Given a graph G, then the function Magic returns true if:

● the graph G is connected,

● the graph G has an even number of vertices,

● the graph G has an even number of edges,

● all components of G have exactly two vertices,

● all components of G have an even number of edges,

● all components of G have an even number of vertices.

[0:20h expected time]  [10 marks]

3. Execute the DFS-based topological sort on the following directed graph.  If there is a choice handle vertices in alphabetic order.

(a)  Give the first three vertices of the topological ordering as a string

σ − 1 (1)σ − 1 (2)σ − 1 (3) without separators.           [0:05h expected time]  [2 marks]

(b)  Give the next three vertices of the topological ordering as a string

σ − 1 (4)σ − 1 (5)σ − 1 (6) without separators.           [0:05h expected time]  [2 marks]

(c)  Give the next five vertices of the topological ordering.

[0:05h expected time]  [2 marks]

(d)  Give the next four vertices of the topological ordering.

[0:05h expected time]  [2 marks]

(e)  Give the final five vertices of the topological ordering.

[0:05h expected time]  [2 marks]

4. In the graph below the weight are indicated by numbers on the edges. Find a mini- mum spanning tree in this graph.

4

(a) What is the total weight of your spanning tree?

[0:30h expected time]  [3 marks]

(b) What are the neighbours of vertex a in the spanning tree? Give them in alpha-

betic order without separating blank space, commas etc .

[0:01h expected time]  [1 mark]

(c) What are the neighbours of vertex c in the spanning tree?

[0:01h expected time]  [1 mark] (d) What are the neighbours of vertex h in the spanning tree?

[0:01h expected time]  [1 mark] (e) What are the neighbours of vertex i in the spanning tree?

[0:01h expected time]  [1 mark] (f) What are the neighbours of vertex j in the spanning tree?

[0:01h expected time]  [1 mark] (g) What are the neighbours of vertex k in the spanning tree?

[0:01h expected time]  [1 mark] (h) What are the neighbours of vertex l in the spanning tree?

[0:01h expected time]  [1 mark]

(i) What are the neighbours of vertex m in the spanning tree?

[0:01h expected time]  [1 mark] (j) What are the neighbours of vertex n in the spanning tree?

[0:01h expected time]  [1 mark]