Graph Theory
Q21.
Let G be an undirected complete graph on n vertices, where n\gt2. Then, the number of different Hamiltonian cycles in G is equal toQ22.
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is .Q23.
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (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?Q24.
G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4 ,v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7 }. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?Q25.
Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?MSQQ26.
Breadth First Search(BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is______ .Q27.
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is ___________.Q28.
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?Q30.
The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?