A city (this is not a typo) is evaluating the cost of constructing bridges to co

Question

A city (this is not a typo) is evaluating the cost of constructing bridges to connect the n islands scattered in lake R. A company, Smart Computing, claims that the following method can be used to compute the minimum number of bridges that are needed:

Initially, all the islands are separated and each forms its own group.

Construct the first bridge between two arbitrarily-chosen islands (and therefore these two islands become a connected group).

As long as there are separated island groups, arbitrarily pick two groups and construct a bridge between two arbitrarily-chosen islands (one from each group). As a consequence, the two selected groups are merged into one single connected group.

Prove, using the principle of strong induction on the number of islands n, that no matter how the groups and islands are selected in each step, the total number of bridges obtained by the above procedure is always n1.

( In the inductive step, consider the last bridge constructed. This last bridge shall connect two islands groups, say A and B. By the inductive hypothesis, it takes ... bridges to connect the islands within group A, and ... bridges to connect the islands within group B. Therefore ...)

Explanation / Answer

Let took two islands then we have to construct 1 bridges now this two forms one connected group.

Then this connected group and a separate island require one bridge to get connected. Now this three forms a connected Group.

Now three islands form a connected group by construction of 2 bridges.

So like this for n islands we need to construct n-1 bridges

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.