Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is TRUE?

LohaHridoy
  1. T' = T with total weight t' = t2
  2. T' = T with total weight t' < t 2
  3. T' ≠ T but total weight t' = t2
  4. None of the above

0 like 0 dislike
1 views
Share with your friends

1 Answers

AhmedNazir

Call

Option 4 : None of the above

The correct answer is “option 4”.

CONCEPT:

A spanning tree of graph G is a subset of G which has all vertices covered with the minimum possible number of edges.

Some properties of spanning tree are:

1. Spanning tree doesn’t contain any cycle.

2. Spanning tree cannot be disconnected.

Every connected and undirected graph G has at least one spanning tree.

EXPLANATION:

Consider graph G with edge weights > 1,

[ alt="F1 Raju S 19.5.21 Pallavi D1" src="//storage.googleapis.com/tb-img/production/21/05/F1_Raju%20S_19.5.21_Pallavi_D1.png" style="width: 182px; height: 134px;">

Consider graph G’ with squared edge weights of graph G,

[ alt="F1 Raju S 19.5.21 Pallavi D2" src="//storage.googleapis.com/tb-img/production/21/05/F1_Raju%20S_19.5.21_Pallavi_D2.png" style="width: 200px; height: 132px;">

The minimum spanning tree (T) of graph G is:

[ alt="F1 Raju S 19.5.21 Pallavi D3" src="//storage.googleapis.com/tb-img/production/21/05/F1_Raju%20S_19.5.21_Pallavi_D3.png" style="width: 171px; height: 137px;">

Minimum Spanning Tree (T’) of graph G’ is:

[ alt="F1 Raju S 19.5.21 Pallavi D4" src="//storage.googleapis.com/tb-img/production/21/05/F1_Raju%20S_19.5.21_Pallavi_D4.png" style="width: 182px; height: 137px;">

So, T is not equal to T'and t' < t2.

Hence, the correct answer is "option 4".

0 like 0 dislike
1 views
Talk Doctor Online in Bissoy App
24 mango trees, 56 apple trees and 72 orange trees have to be planted in rows such that each row contains the same number of trees of one variety only. Find the minimum number of rows in which the above mentioned trees may be planted.?

Option 3 : 19Given: 24 mango trees, 56 apple trees and 72 orange trees have to be planted in rows such that each row contains the same number of trees of...

1 Answers 1 views
The logic problems in this set present you with three true statements: Fact 1, Fact 2 and Fact 3. Then you are given three more statements (labelled I, II, III), and you must determine which of these, if any, is also a fact. One or two of the statements could be true; or none of the statements could be true. Fact 1: Pictures can tell a story. Fact 2: All storybooks have pictures. Fact 3: Some storybooks have both words and pictures. If the first three statements are facts, which of the following statement/(s) must also be a fact I. Pictures can tell a story better than words can. II. The stories in storybooks are very simple. III. Some storybooks have both words and pictures. Choose the correct answer from the options given below:?

Option 3 : Only IIIIn the given question, Statement Correctness Reason Pictures can tell a story better than words can. Incorrect This statement is incorrect as it has no base to justify its say from the...

1 Answers 1 views
The logic problems in this set present you with three true statements: Fact 1, Fact 2 and Fact 3. Then you are given three more statements (labelled I, II, III), and you must determine which of these, if any, is also a fact. One or two of the statements could be true; or none of the statements could be true. Fact 1: Jessica has four children. Fact 2: Two of the children have blue eyes and two of the children have brown eyes. Fact 3: Half of the children are girls. If the fist three statements are facts, which of the following statement/(s) must also be a fact I. At least one girl has blue eyes. II. Two of the children are boys. III. The boys have brown eyes. Choose the correct answer from the options given below:?

Option 1 : Only IIIn the given question, Statement Correctness Reason At least one girl has blue eyes Incorrect This could be a probable situation but not sure as maybe both boys have blue eyes and...

1 Answers 1 views
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.?

Option 1 : P onlyThe correct answer is “option 1”. EXPLANATION: Statement P: True Every edge in a given cycle graph will become a vertex in the new defined graph L(G) and every vertex...

1 Answers 1 views
If A is greater than or equal to 50 but less than 70 and B is less than or equal to 70 but greater than 50, then which of the following is the correct choice.?

Option 4 : B - A is always less than or equal to 20Given : A &gt; 50 and B &lt; 70  Calculations : Check for every option For option 1  A is greater than...

1 Answers 1 views
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?

Option 3 : (a, b), (b, c), (c, i), (c, f), (f, g), (g, h), (c, d), (d, e) The correct answer is option 1 and option 3. Concept: A minimum spanning tree...

1 Answers 4 views
User level threads are threads that are visible to the programmer and are unknown to the kernel. The operating system kernel supports and manages kernel level threads. Three different types of models relate user and kernel level threads. Which of the following statements is/are true (a) (i) The Many - to - one model maps many user threads to one kernel thread (ii) The one - to - one model maps one user thread to one kernel thread (iii) The many - to - many model maps many user threads to smaller or equal kernel threads (b) (i) Many - to - one model maps many kernel threads to one user thread (ii) One - to - one model maps one kernel thread to one user thread (iii) Many - to- many model maps many kernel threads to smaller or equal user threads?

Option 1 : (a) is true; (b) is falseThe correct answer is option 1. CONCEPT: Threads are lightweight processes because they have their own stack but can access shared data. Because threads...

1 Answers 1 views
Consider the graph given below:   Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are chosen is?

Option 3 : GC, AD, GB, GA, BF, AEConcept: Krushkal Algorithm 1. First Sort All Edges in non Decreasing order. ( Generally Uses Min Heap )  2. Delete Minimum Edge from Min heap. 3....

1 Answers 1 views
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following option is/are correct?

Option :Answer: Option 2 Explanation: Option 1: If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in...

1 Answers 1 views
Let G be a connected undirected weighted graph. Consider the following two statements. S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G. S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree. Which one of the following options is correct?

Option 1 : S1 is false and S2 is true.Concept: A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected,...

1 Answers 1 views
X