Graph Theory
Q41.
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.Q42.
What is the cyclomatic complexity of a module which has seventeen edges and thirteen nodes?Q43.
Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even.Q44.
Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?Q45.
The line graph L(G) of a simple graph G is defined as follows: There is exactly one vertex v(e) in L(G) for each edge e in G. For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.