Question

Minimum spanning trees were initially design to solve electrical grid problems but now have many more applications such as computer networks, transportation networks, and supply networks. Describe a business problem where minimum spanning trees can be used to find a solution.

Answer 1

ANSWER:

A spanning tree of a graph is just a subgraph that contains all the vertices and is a tree. A graph may have many spanning trees; for instance the complete graph on four vertices

has sixteen spanning trees

The standard application is to a problem like phone network design. You have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. It should be a spanning tree, since if a network isn't a tree you can always remove some edges and save money.

A less obvious application is that the minimum spanning tree can be used to approximately solve the traveling salesman problem. A convenient formal way of defining this problem is to find the shortest path that visits each point at least once.

Note that if you have a path visiting all points exactly once, it's a special kind of tree. For instance in the example above, twelve of sixteen spanning trees are actually paths. If you have a path visiting some vertices more than once, you can always drop some edges to get a tree. So in general the MST weight is less than the TSP weight, because it's a minimization over a strictly larger set.

NOTE:: I HOPE THIS ANSWER IS HELPFULL TO YOU......**PLEASE SUPPORT ME WITH YOUR RATING......

***PLEASE GIVE ME "LIKE"...ITS VERY IMPORTANT FOR ME NOW....PLEASE SUPPORT ME ....THANK YOU