Let G be an undirected connected graph with distinct edge weights . Let emax be the edge with maximum weight and emin be the edge with minimum weight. Which of the following statements is false.?

Every minimum spanning tree of G must contain e_min
If emax is in a minimum spanning tree, then its removal must be disconnected G.
No minimum spanning tree contains e_max
G has a unique minimum spanning tree.

LohaHridoy

4 views

2025-01-04 04:42

1 Answers

AhmedNazir

Option 3 : No minimum spanning tree contains emax

Concept:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Example:

It cannot always be the case that the edge with e_max should not be present in MST.

[ alt="Gate CS Algorithms Chapter-5 Images-Q7" src="//storage.googleapis.com/tb-img/production/15/12/Gate%20CS_Algorithms_Chapter-5_Images-Q7.PNG" style="height:377px; width:257px">

e_max is present in MST.

4 views Answered 2022-09-04 04:29

Related Questions

The following question has two statements. Study the question and the statements and decide which of the statement(s) is necessary to answer the question. A retailer wants to earn profit by selling sugar to his customer. He analyzed various methods as per follows. Which of the following would maximize his profit I) Sell sugar at 20% profit. II) Use faulty weight which measures 800 gm instead of 1000 gm III) Mix 10% impurities in sugar and selling it at cost price. IV) Increase the price by 20% and reduce weight by 20%?

1 Answers 4 Views

In each of the following questions, two statements numbered I and II are given. There may be cause and effect relationship between the two statements. These two statements may be the effect of the same cause or independent causes. These statements may be independent causes without having any relationship. Read both the statements in each question and mark your answer. Statements: I. Hotel Leela venture, which currently has a debt of over Rs. 3,600 crore, had issued secured redeemable non-convertible debentures on private placement basis aggregating to Rs. 90 crores to LIC in December, 2008. II. Hotel Leela venture’s "operating cash flows are not sufficient to service its term loans and NCDs and the funds of the company are escrowed with its lenders and are also monitored by the lenders".?

1 Answers 6 Views

The following question, there are three statements I, II and III. Read the question carefully and mark your answer according to which statements(s) is/are sufficient to the answer the question. Find the overall profit percent of the shopkeeper Statement I: The profit made while selling 1 kg of sugar was 16%. But he uses false weight. Statement II: Weight used was 31% less than the actual 1 kg weight of the sugar. Statement III: There was no discount on the price of the sugar?

1 Answers 8 Views

Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD .) (II) For every edge (u, v) of if u is at depth i and v is at depth j in TB , then | − | = 1. Which of the statements above must necessarily be true?

1 Answers 5 Views

In the following question, two statements are given each followed by two conclusions I and II. You have to consider the statements to be true even if they seem to be at variance from commonly known facts. You have to decide which of the given conclusions, if any, follows from the given statements. Statement: (I) Wages are determined by minimum wage legislation in each country. (II) Increase in wage rate is the sign of growth in an economy. Conclusions: (I) Average wage rate signifies the wealth of a country. (II) Minimum wage legislation does not account wage imbalances.?

1 Answers 5 Views

Two processes X and Y need to access a critical section. Consider the following synchronization construct used by both the processes Process /* other code for process */ while(true) { varP = true; while(varQ == true) { /* Critical Section */ varP = false; } } /* other code for process */ Process /* other code for process */ while(true) { varQ = true; while(varP == true) { /* Critical Section */ varQ = false; } } /* other code for process */ Here, varP and varQ are shared variables and both are initialized to false. Which one of the following statements is true?

1 Answers 5 Views

A coin is tossed thrice. Let X be the event that head occurs in each of the first two tosses. Let Y be the event that a tail occurs on the third toss. Let Z be the event that two tails occur in three tosses. Based on the above information, which one of the following statements is TRUE?

1 Answers 5 Views

Let G be an undirected connected graph with distinct edge weight. Let emax be the edge maximum weight and emin the edge with minimum weight. Which of the following statements are false?

1 Answers 4 Views

Among five rods, P, Q, R, S and T, the weight of T is 20 kg. The weight of S is half the weight of P. The weight of Q is one-fourth the weight of P. R's weight is twice the weight of Q. The weight of P is twice the weight of T. Which rod is the lightest among all?

1 Answers 4 Views

Let A, B and C represent distinct non-zero digits. Suppose x is the sum of all possible 3-digit numbers formed by A, B and C without repetition. Consider the following statements : 1. The 4-digit least value of x is 1332. 2. The 3-digit greatest value of x is 888. Which of the above statements is/are correct?

1 Answers 4 Views

এক্সাম দিয়ে মেধা যাচাই করুন

Job Preparation (1125)

Admission (754)

এসএসসি (10)

এইচএসসি (5)