CS502 Quiz 3 Set 2 by VU Topper RM

Equivalence relation partitions the vertices into _________ classes of mutually reachable vertices and these are the strong components A. Variance B. Non classes

C. Equivalence Page 136

D. Non equivalence

The ancestor and descendent relation can be nicely inferred by the ______________ lemma. A. Node B. Division C. Addition

D. Parenthesis Page 129

Networks are ________ in the sense that it is possible from any location in the network to reach any other location in the digraph. A. Not graphs.

B. Complete Page 135

C. Incomplete D. Transportation

In strong components algorithm, first of all DFS is run for getting _______ times of vertices.

A. Start Page 138

B. Finish C. Middle D. Both start & finish

Timestamp structure of __________ is used in determining the strong components of a digraph.

A. DFS Google

B. BFS C. MST D. Both DFS, BFS In Timestamped DFS-cycles lemma, if edge (u, v) is a tree, forward or cross edge, then _________

A. f[u]>f[v]

B. f[u]<f[v] C. f[u]⩽f[v] D. f[u]⩾f[v]

The component digraph is necessarily _____________. A. Cyclic B. Strong

C. Acyclic Page 136

D. Straight

In computing the ____________ components of a digraph, vertices of the digraph are partitioned into subsets. A. Best B. Worst C. Weakly connected

D. Strongly connected Page 135

There exist a unique path between any ________ vertices of a free tree. A. One

B. Two

C. five D. three

The ________ given by DFS allow us to determine whether the graph contains any cycles. A. Order

B. Time stamps Page 130

C. BFS traversing D. Topological sort

Forward edge is: A. (u, v) where u is a proper descendent of v in the tree. B. (u, v) where v is a proper descendent of u in the tree. C. (u, v) where v is a proper ancesstor of u in the tree. D. (u, v) where u is a proper ancesstor of v in the tree.

Once you enter a strong component, every vertex in thecomponent is

A. Removed

B. Reachable Page 137

C. not reachable D. reachable some times

In Generic approach determining of Greedy MST, we maintain a subset A of __________ . A. Paths

B. Edges Page 143

C. Cycles D. Vertices

If you find yourself in maze the better traversel approach will be : A. DFS

B. BFS

C. Level order D. DFS

Computing the strongly connected components of a digraph is a/an ___________ of the problem to determine whether a digraph is strongly connected or not. A. Size B. Connection C. Optimization

D. Generalization Page 135

A free tree with n _________ have exactly n-1 _________.

A. vertices,edges Page 142

B. vertices,nodes C. nodes,vertices D. vertices,nodes