CS502 Quiz No.4 File 3

There is relationship between number of back edges and number of cycles in DFS Select correct option:

Both are equal.

Cycles are half of back edges.

 Cycles are one fourth of back edges.

There is no relationship between back edges and number of cycles.         (Correct)

In strong components algorithm, the form of graph is used in which all the vertices of original graph G have been reversed in direction. Select correct option:

True                (Correct)

 False

In Kruskal's algorithm, the next edge is added to viable set A, if its adding does not induce a/an __________ . Select correct option:

Vertex

Edge

 Cycle              (Correct)

 Tree

For undirected graph, there is no distinction between forward and back edges. Select correct option:

True                (Correct)

 False

You have an adjacency list for G, what is the time complexity to compute Graph transpose G^T ? Select correct option:

(V+E)             (Correct)

V.E

 V

E

There exist a unique path between any ________ vertices of a free tree. Select correct option:

One

 Two                (Correct)

Three

 All

A digraph is strongly connected under what condition? Select correct option:

A digraph is strongly connected if for every pair of vertices u, v e V, u can reach v .

A digraph is strongly connected if for every pair of vertices u, v e V, u can reach v and vice versa.                   (Correct)

A digraph is strongly connected if for at least one pair of vertex u, v e V, u can reach v and vice versa.

A digraph is strongly connected if at least one third pair of vertices u, v e V, u can reach v and vice versa.

If u and v are mutually reachable in G, then in the graph formed by reversing all the edges, these vertices are not reachable. Select correct option:

True

 False              (Correct)

In Prim's algorithm, at any time, the subset of edges A forms a single forest. Select correct option:

True

 False              (Correct)

In digraph G=(V,E) ;G has cycle if and only if

The DFS forest has forward edge.

The DFS forest has back edge

The DFS forest has both back and forward edge

BFS forest has forward edge