B2_Graphs

For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Span­ning Tree?

• (a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)

• (c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i)

• (d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i)

• (h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)

Consider a directed graph with n vertices and m edges such that all edges have same edge weights. Find the complexity of the best known algorithm to compute the minimum spanning tree of the graph?

• O(m+n)

• O(m logn)

• 
  O(mn)

• 
  O(n logm)

Which of the following data structure is useful in traversing a given graph by breadth first search?

• Stack

• 
  List

• Queue

• None of the above.

In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is _________.

• 10

• 11

• 12

• 6

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?

• 1

• 1/8

• 7

• 6

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.

• Both P and Q

• P is true, Q is false.
• Both P and Q

• Only P

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.

• • P only

• • P and R only

• R only

• • P, Q and S only

Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to

• 6

• 5

• 4

• 3