Thursday, October 13, 2011

What is the real world scenario where Minimum Spanning Tree Solutions are used?


One real world application of a Minimum Spanning Tree would be in the design of a computer network. In order to connect a group of individual computers over a wired network which are separated by varying distances a MST can be applied. Although MST cannot do anything about the distance from one connection to another, it can be used to determine the least costly paths with no cycles in this network, thereby connecting all the computers at a minimum cost.

Another useful application of MST would be finding airline routes. The vertices of the graph would represent cities, and the edges would represent routes between the cities. Obviously, the further one has to travel, the more it will cost, so MST can be applied to optimize airline routes by finding the least costly paths with no cycles.

No comments:

Post a Comment