Aspire Faculty ID #18988 · Topic: UGC NET Computer Science Nov 2020 (Paper II) · Just now
UGC NET Computer Science Nov 2020 (Paper II)

Consider the undirected graph below.



Using Prim's algorithm to construct a minimum spanning tree starting with node $a$, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?

Solution

Using Prim's algorithm, we always select the minimum weight edge that connects the current tree with a new vertex.

Start from vertex $a$.

From $a$, possible edges are:

$(a,b)=4$

$(a,h)=8$

Minimum edge is:

$(a,b)=4$

So, first edge is $(a,b)$.

Now current tree is:

$\{a,b\}$

Possible crossing edges are:

$(a,h)=8$

$(b,c)=8$

$(b,h)=11$

Here, $(a,h)$ and $(b,c)$ both have the same minimum weight $8$.

So, there is a tie.

If we choose $(a,h)$, then the sequence can be:

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

This matches option (A).

Now check option (A):

After adding $(a,h)$, minimum edge from tree to outside is:

$(h,g)=1$

Then,

$(g,f)=2$

Then,

$(f,c)=4$

Then,

$(c,i)=2$

Then,

$(c,d)=7$

Then,

$(d,e)=9$

So, option (A) is a valid possible order.

But because of the tie at weight $8$, we may also choose $(b,c)$ instead of $(a,h)$.

If we choose $(b,c)$, then the sequence can be:

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

This matches option (C).

So, option (C) is also a valid possible order.

Option (B) is not correct because after $(a,b)$, edge $(b,h)=11$ cannot be selected since edges of weight $8$ are available.

Option (D) is not correct because $(g,h)$ cannot be selected immediately after $(a,b)$ as it does not connect the current tree to a new vertex.

Therefore, both options (A) and (C) are possible due to tie in Prim's algorithm.

Correct Answer: (A) and (C) both are possible

Note: If the question expects only one answer, then it is ambiguous because Prim's algorithm can give different valid edge orders when equal weight edges are present.
← Previous Next →

Previous 10 Questions — UGC NET Computer Science Nov 2020 (Paper II)

Nearest first
1
Arrange the following types of Cohesion from best to worst type.(A) Logical Cohesion(B) Sequential Cohesion(C) Communic…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 2
Given below are different properties of $3D$ projections from A-D. Identify the correct order on the basis of property …
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 3
Arrange the following types of machine in descending order of complexity.(A) SISD(B) MIMD(C) SIMDChoose the correct ans…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 4
In lexicographic ordering, comparison is done from left to right.Given order is:$0<1$Now compare the given strings:$…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 5
Match List I with List II. List I List II (A) Gree…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 6
Match List I with List II. List I List II (A) Seri…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 7
Match List I with List II.$L_R$ : Regular language, $L_{CF}$ : Context free language$L_{REC}$ : Recursive language, $L_…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 8
Match List I with List II. List I List II (A) Topo…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 9
Match List I with List II. List I List II (A) Bran…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 10
Match List I with List II.With reference to CMM developed by Software Engineering Institute (SEI) …
Topic: UGC NET Computer Science Nov 2020 (Paper II)

Next 10 Questions — UGC NET Computer Science Nov 2020 (Paper II)

Ascending by ID
1
Consider the following regular expressions:(a) $r=a(b+a)^*$(b) $s=a(a+b)^+$(c) $t=aa^*b$Choose the correct answer from …
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 2
Given below are two statements:Statement I: $5$ divides $n^5-n$ whenever $n$ is a nonnegative integer.Statement II: $6$…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 3
Given below are two statements:Statement I: Hardwired control unit can be optimized to produce fast mode of operation.S…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 4
Given below are two statements:Statement I: Bezier curves are curves that interpolate all of their control points.State…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 5
Given below are two statements:If two variables $V_1$ and $V_2$ are used for clustering, then consider the following st…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 6
Assuming that the system call $fork()$ never fails, consider the following C programs $P1$ and $P2$ executed on a UNIX …
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 7
Given below are two statements:Statement I: Quality control involves the series of inspections, reviews and tests used …
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 8
Let $G$ be a simple undirected graph, $T_D$ be a DFS tree on $G$, and $T_B$ be the BFS tree on $G$.Consider the followi…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 9
Given below are two statements:Statement I: The problem "Is $L_1\cap L_2=\phi$?" is undecidable for context sensitive l…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
 10
Given below are two statements:Statement I: The laws of nature put two fundamental limits on the data rate of a channel…
Topic: UGC NET Computer Science Nov 2020 (Paper II)
Ask Your Question or Put Your Review.

loading...