Discrete Mathematics
Q61.
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______ .Q62.
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 ___________.Q63.
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?Q65.
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?Q67.
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x \in V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)-d(v)?Q68.
The minimum number of colours that is sufficient to vertex-colour any planar graph is _________.Q69.
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, n isQ70.
A given connected graph G is a Euler Graph if and only if all vertices of G are of