Graphs Exercises

   < Previous  Next >
  1. Identify as many of the graph terms as you can that apply to the following graph:
    Graph of A pointing to B, C & F; B pointing to C, D & F; C pointing to F; D pointing to C; E pointing to D; F pointing to D & E; All edges have weights
  2. Given the above graph, draw the resulting:
    • Adjacency list
    • Adjacency matrix
  3. Discuss with your neighbor the advantages and disadvantages of storing the above graph with each of the following:
    • Adjacency list
    • Adjacency matrix
    For each implementation, how could you store the vertex labels? How could you store weights?
  4. Discuss with your neighbor the advantages and disadvantages of performing the following common operations on graphs for each implementation:
    1. Determine whether there is an edge from vertex i to vertex j
    2. Find all vertices adjacent to a given vertex i
  5. Given digraph G = (V, E) with an adjacency list representation how long does it take to determine the outdegree for v ∈ V?
  6. Given digraph G = (V, E) with an adjacency list representation how long does it take to determine the indegree for v ∈ V?
  7. When an adjacency matrix representation is used, most graph algorithms require time Ω( |V|2 ), but there are some exceptions. Show that determining whether a directed graph G contains a universal sink - a vertex with indegree |V| - 1 and outdegree 0-can be determined in time O( |V| ), given an adjacency matrix for G.
    Trace the execution of such an algorithm on the following graphs: 
    • 		To					
		A	B	C	D	E	F
From	A	1	0	1	1	0	0
	B	0	1	0	1	1	1
	C	1	1	0	1	1	0
	D	0	0	0	0	0	0
	E	0	1	0	1	0	0
	F	0	1	1	1	1	0
    • 		To					
		A	B	C	D	E	F
From	A	1	0	1	1	0	0
	B	0	1	0	1	1	1
	C	1	1	0	1	1	0
	D	0	0	0	0	0	1
	E	0	1	0	1	0	0
	F	0	1	1	1	1	0
(Only the edge from D to F is changed from the previous graph)
  8. List the vertices in the order that the respective search will visit them (starting with vertex A in the graph at the top):
    • Depth-first search
    • Breadth-first search
  9. Discuss with your neighbor what is the run time for Breadth-First Search, in terms of E and V.
  10. Given the list of directed edges below, draw the directed graph: 
    Dress & groom            -> Buy flowers
Buy flowers              -> Pick-up date
Select activity          -> Pick-up date
Make dinner reservations -> Select activity
Pick-up date             -> Activity
Activity                 -> Dinner
  11. For the graph in the preceeding question, determine the topological order. Use the algorithm that finds a vertex that does not have a successor and the one that finds a vertex that does not have a predecessor.

Last Modified: