Question 8 (9 marks)
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.