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:
vertex Adjacent vertices
(2; 3; 4)
(1; 3; 4)
(1; 2; 4)
(1; 2; 3; 6)
(6; 7; 8)
(4; 5; 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 as they are listed in the above table.
Draw G
Order the vertices as they are visited in a DFS traversal starting at vertex 1.
Order the vertices as they are visited in a BFS traversal starting at vertex 1.
For the graph G in Problem 1, draw its adjacency-lists representation and adjacency matrix representation.
Show that every connected graph has a vertex whose removal (including all adjacent edges) will not disconnect the graph and design a DFS-based algorithm that nds such a vertex.
Let F = (V; E) be a forest with n vertices and k connected components. Prove that the number of edges in F = n k.
Design an algorithm to determine whether a digraph has a unique topological ordering.
1
