Homework 14 - Graphs

(submission is not required)

Question 1.
Draw a simple undirected graph G that has 12 vertices, 18 edges and 3 connected components. Why would it be impossible to draw G with 3 connected components if G had 66 edges?

Question 2.
Let G be a graph whose vertices are integers 1 through 8, and let the adjacent vertices of each vertex be given by the table below:

v | Adj[v]
1 | (2,3,4)
2 | (1,3,4)
3 | (1,2,4)
4 | (1,2,3,6)
5 | (6,7,8)
6 | (4,5,7)
7 | (5,6,8)
8 | (5,7)

Assume that, in a traversal of G, the adjacent vertices of a given vertex are returned in the same order they are listed in the table.
(a) Draw G.
(b) Write the adjacency matrix structure of the G.
(c) Give the sequence of vertices of G visited using DFS traversal starting at vertex 1.
(d) Given the sequence of vertices of G visited using BFS traversal starting at vertex 1.

Question 3.
Explain why BFS and DFS traversal runs in O(n2) time on an n-vertex graph that is represented with the adjacency matrix.

Question 4.
Give procedure code to describe the BFS traversal from lecture using a non-recursive algorithm.

Question 5.
Give procedure code to describe DFS traversal from lecture using a non-recursive algorithm.