Directed Graphs quiz



How many different digraphs are there on V vertices? Allow self-loops but do now allow self-edges.

V
2V
2(V2)
2(2V)

Suppose that a digraph G is represented using the adjacency-lists representation. What is the order of growth of the running time to find all vertices that point to a given vertex v?

indegree(v)
outdegree(v)
V
V + E

Suppose that during an execution of depth-first search in a digraph G, dfs(v) is called after dfs(w) is called, but before dfs(w) returns. Which of the following must be true of the graph G?

There exists a directed path from v to w.
There exists a directed path from w to v.
There does not exist a directed path from v to w.
There exists a directed cycle containing both v and w.

How many strong components does a DAG on V vertices and E edges have?

0
1
V
E