Time Left - 10:00 mins

Graph Algorithms

Attempt now to get your rank among 65 students!

Question 1

Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is ___________.

Question 2

Consider a complete graph G with 4 vertices. The number of spanning trees possible for graph G.

Question 3

In a simple undirected graph with ‘n’ vertices maximum degree for each vertex is

Question 4

The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ___________.

Question 5

Consider a weighted complete graph G on the vertex set {v₁, v₂, .… v_n} such that the weight of the edge (v_i, v_j) is 3|i – j|. The weight of the minimum spanning tree of G is:

65 attempts
0 upvotes
0 comments

Tags :

GATE & PSU CS Algorithms

Jul 5GATE & PSU CS