Question 1 |

Let T be a DFS tree obtained by doing DFS in a connected undirected graph G.

Which of the following options is/are correct?

Root of T can never be an articulation point in G. | |

Root of T is an articulation point in G if and only if it has 2 or more children. | |

A leaf of T can be an articulation point in G. | |

If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u. |

Question 2 |

v2v4 | |

v1v4 | |

v4v5 | |

v3v4 |

Question 3 |

Finding diameter of the graph | |

Finding bipartite graph | |

Both (A) and (B) | |

None of the above |

Question 4 |

(I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)

(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |i-j|=1.

Which of the statements above must necessarily be true?

I only | |

II only | |

Both I and II | |

Neither I nor II |

Question 5 |

MNOPQR | |

NQMPOR | |

QMNROP | |

POQNMR |

Question 6 |

16 | |

15 | |

31 | |

32 |

Question 7 |

The number of different topological orderings of the vertices of the graph is

4 | |

5 | |

6 | |

7 |

Question 8 |

-1 | |

0 | |

1 | |

2 |

Question 9 |

16 | |

19 | |

17 | |

20 |

Question 10 |

\Theta (n) | |

\Theta (n+m) | |

\Theta (n^{2}) | |

\Theta (m^{2}) |