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

The cost of renting a bike at the local bike is y = 2x + 2, The cost of re...

The cost of renting a bike at the local bike shop can be represented through the equation y = 2x + 2, where y is the total cost and x is the number of hours the bike is rented. Whi

Decision-making under conditions of certainty, Decision-Making Under Condit...

Decision-Making Under Conditions of Certainty Conditions of certainty tend to be rare, especially when significant decisions are involved. Under conditions of certainty, decis

Area of solid figures, the formulas of the area of solid figures

the formulas of the area of solid figures

Find out the mean wait in line - probability, Example of Probability I...

Example of Probability Illustration: It has been determined that the probability density function for the wait in line at a counter is specified by, In which t is the

Binomial expansion, Expand (1- 1/2x -x^2)^9

Expand (1- 1/2x -x^2)^9

Show that x(q-r) + y(r-p) + z(p-q) = 0, If the p th , q th & r th term of...

If the p th , q th & r th term of an AP is x, y and z respectively, show that x(q-r) + y(r-p) + z(p-q) = 0 Ans: p th term ⇒ x = A + (p-1) D q th term ⇒ y = A + (

Derivatives, What are the ingredients of a Mathematical Model? What is a mo...

What are the ingredients of a Mathematical Model? What is a model?

One tailed test, One Tailed Test It is a test where the alternative hy...

One Tailed Test It is a test where the alternative hypothesis (H 1 :) is only concerned along with one of the tails of the distribution for illustration, to test a business co

The sum of two integers is 36 what is the smaller number, The sum of two in...

The sum of two integers is 36, and the difference is 6. What is the smaller of the two numbers? Let x = the ?rst integer and let y = the second integer. The equation for the su

Pendulum, how many pendulum swings will it take to walk across the classroo...

how many pendulum swings will it take to walk across the classroom

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages