Sample | Sample Final Exam | COMP2521 |

[Q1] [Q2] [Q3] [Q4] [Q5] [Q6] [Q7]

Consider the following graph:

Based on the above, answer the following questions:

Identify any subgraph(s) which form a

*clique*. Identify any clique by giving the set of vertices it contains.Identify the vertex (or vertices) in the graph with the largest degree. Give both the vertex (or vertices)

*and*the degree.Any

*one*of three edges could be removed from this graph to leave a spanning tree. Which edges are they?Consider a non-recursive

*depth-first traversal*of this graph using a stack. Starting from vertex 6, show the current vertex and the stack of to-be-visited vertices at each iteration of the traversal. If a vertex is connected to multiple not-yet-visited vertices, these vertices will be pushed onto the stack in increasing order of vertex number (e.g. vertex 6 is connected to vertices 5 and 7, so during the first iteration vertex 5 will be pushed first onto the stack followed by vertex 7). Make sure that your answer shows clearly which is the top of the stack.Consider a non-recursive

*breadth-first traversal*of this graph using a queue. Starting from vertex 6, show the current vertex and the queue of to-be-visited vertices at each iteration of the traversal. If a vertex is connected to multiple not-yet-visited vertices, these vertices will be added onto the queue in increasing order of vertex number (e.g. vertex 6 is connected to vertices 5 and 7, so during the first iteration vertex 5 will be added first onto the queue followed by vertex 7). Make sure that your answer shows clearly which is the front of the queue.

Type the answer to this question into the file called
`q8.txt` and submit it using the command:

$submit q8

The above command will make a copy of `q8.txt` as your answer
for this question.