a. Graph G is an undirected graph, represented using the following adjacency list. Draw G. Vertex...

 

Transcribed Image Text:

a. Graph G is an undirected graph, represented using the following adjacency list. Draw G. Vertex Neighbors 1 2,3,4 1,3,4 23456 1,2,4 1,2,3,6 6,7,8 4,5,7 7 8 5,6,8 5,7 b. Which graph representation would you use to represent a graph with V vertices and E edges if E is O(V) for minimum space requirement? What if E is O(V)? What if we also care about adjacency time? c. A universal sink is a vertex with in-degree |V|-1 and out-degree 0. Given a graph G(V,E), represented as an adjacency matrix, describe an algorithm that determines whether G(V,E) contains a universal sink. a. Graph G is an undirected graph, represented using the following adjacency list. Draw G. Vertex Neighbors 1 2,3,4 1,3,4 23456 1,2,4 1,2,3,6 6,7,8 4,5,7 7 8 5,6,8 5,7 b. Which graph representation would you use to represent a graph with V vertices and E edges if E is O(V) for minimum space requirement? What if E is O(V)? What if we also care about adjacency time? c. A universal sink is a vertex with in-degree |V|-1 and out-degree 0. Given a graph G(V,E), represented as an adjacency matrix, describe an algorithm that determines whether G(V,E) contains a universal sink.