UTpaper

Free mock tests & test series

Question 13Asked in UGC NET Computer Science, June 2015 (Paper II & III, Selected Questions)

Consider the given graph (edge : weight) : 1–6 : 10, 1–2 : 28, 2–7 : 14, 2–3 : 16, 6–5 : 25, 5–7 : 24, 7–4 : 18, 5–4 : 22, 4–3 : 12

Consider the given graph (edge : weight) : 1–6 : 10, 1–2 : 28, 2–7 : 14, 2–3 : 16, 6–5 : 25, 5–7 : 24, 7–4 : 18, 5–4 : 22, 4–3 : 12 Its Minimum cost spanning tree is ..........
  1. AEdges 1–2 (28), 2–3 (16), 3–4 (12), 4–5 (22), 5–6 (25), 6–7
  2. BEdges 1–6 (10), 6–5 (25), 5–4 (22), 4–3 (12), 3–2 (16), 2–7 (14)
  3. CEdges 1–2 (28), 2–3 (16), 3–4 (12), 4–5 (22), 5–6 (25), 5–7 (24)
  4. DEdges 1–6 (10), 1–2 (28), 2–3 (16), 3–4 (12), 4–7 (18), 4–5 (22)
Show answerHide answer

Correct answer: (B) Edges 1–6 (10), 6–5 (25), 5–4 (22), 4–3 (12), 3–2 (16), 2–7 (14)

Explanation

Using Kruskal's algorithm: take 10 (1–6), 12 (3–4), 14 (2–7), 16 (2–3); skip 18 (4–7, cycle); take 22 (4–5); skip 24 (5–7, cycle); take 25 (5–6). Total = 10 + 12 + 14 + 16 + 22 + 25 = 99, which is option (b).

From UGC NET Computer Science PYQ, June 2015 (Paper II & III, Selected Questions)

This is question 13 of UGC NET Computer Science PYQ, June 2015 (Paper II & III, Selected Questions). See all questions of this paper with answers, or attempt the paper as a timed online test to get your score and all-India rank.