Register

GATE CSE 2006 | Question: 47

• edited by
9,750 views
21 votes
21 votes

Consider the following graph:

Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm? 

  1. $(a-b),(d-f),(b-f),(d-c),(d-e)$
  2. $(a-b),(d-f),(d-c),(b-f),(d-e)$
  3. $(d-f),(a-b),(d-c),(b-f),(d-e)$
  4. $(d-f),(a-b),(b-f),(d-e),(d-c)$
• edited by
User Avatar

2 Answers

Best answer
26 votes
26 votes

In Kruskal's algo the edges are added in non decreasing order of their weight. But in Option D edge $d-e$ with weight $3$ is added before edge $d-c$ with weight $2$. Hence, option D is wrong option.

Correct Answer: $D$

• edited by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

32 votes
32 votes
7 answers
1
Rucha Shelke asked Sep 16, 2014
15,149 views
GATE CSE 2006 | Question: 11
Consider a weighted complete graph $G$ on the vertex set $\{v_1,v_2,.....v_n\}$ such that the weight of the edge $(v_i, v_j)$ is $2|i-j|$. The weight of a minimum spanning tree of $G$ is: $n-1$ $2n-2$ $\begin{pmatrix} n \\ 2 \end{pmatrix}$ $n^2$
Consider a weighted complete graph $G$ on the vertex set $\{v_1,v_2,.....v_n\}$ such that the weight of the edge $(v_i, v_j)$ is $2|i-j|$. The weight of a minimum spanni...
User Avatar
59 votes
59 votes
7 answers
3
Rucha Shelke asked Sep 16, 2014
31,885 views
GATE CSE 2006 | Question: 12
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is: Queue Stack Heap B-Tree
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:QueueStackHeapB-Tree
User Avatar
35 votes
35 votes
9 answers
4
gatecse asked Feb 14, 2018
18,092 views
GATE CSE 2018 | Question: 47
Consider the following undirected graph $G$: Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $G$ for this value of $x$ is ____.
Consider the following undirected graph $G$:Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $...
User Avatar
Link Copied!