What is minimum spanning tree, Mathematics

Assignment Help:

What is minimum spanning tree?  Determine a railway network of minimal cost for the cities in the following graph using Kruskal's algorithm.

Ans: Minimum spanning tree in a connected weighted graph is spanning tree which has the smallest possible sum of weights of its edges.

2247_What is minimum spanning tree.png

We collect the edges in sorted order like this:

1121_What is minimum spanning tree 1.png

Select the edges (B,C),(D,F),(A,G),(C,D),(C,E).

After that we have option we may choose only one of (A,B) and (A,D), as selection of both makes a circuit. Assume we choose (A,B).  

Similarly we may choose just only one of (G,H) and (F,H).Assume we select (F,H).  

We Comprise a spanning tree as:

1500_What is minimum spanning tree 2.png


Related Discussions:- What is minimum spanning tree

Evaluate the area of the shaded region, Using the example provided, Evaluat...

Using the example provided, Evaluate the area of the shaded region in terms of π. a. 264 - 18π b. 264 - 36π c. 264 - 12π d. 18π- 264 b. The area of the shaded r

Need answer urgently, using a pair of compasses a ruler and a pencil. const...

using a pair of compasses a ruler and a pencil. construct a triangle CDE in which DE=10cm, DC+8cm and CDE= 45 degrees. construct CF perpendicular to DE such that F lies on DE using

Vectors, A 10 m ladder of 150N is placed at an angle 30degrees to a smooth ...

A 10 m ladder of 150N is placed at an angle 30degrees to a smooth wall at point A and the other end (point B) on the ground. Assume that the weight of the ladder acts at its mid po

Mensuration, if area of a rectangle is 27 sqmtr and it perimeter is 24 m fi...

if area of a rectangle is 27 sqmtr and it perimeter is 24 m find the length and breath#

Evaluate algebraic word problems, Evaluate algebraic word problems: A ...

Evaluate algebraic word problems: A utility has three nuclear facilities which supply a total of 600 megawatts (Mw) of electricity to a particular area.  The largest facility

Find the total volume of the hay stack, The lower portion of a hay stack is...

The lower portion of a hay stack is an inverted cone frustum and the upper part is a cone find the total volume of the hay stack.

How many handles must be molded weekly to break even, Northwest Molded mold...

Northwest Molded molds plastic handles which cost $0.70 per handle to mold. The fixed cost to run the molding machine is $5799 per week. If the company sells the handles for $ 3.70

Application of statistics-quality control, Quality Control Normally th...

Quality Control Normally there is a quality control departments in every industry which is charged along with the responsibility of ensuring about the products made do meet th

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd