the explaination of minimal spanning tree problem without graph theory. Its practical use , how it is important in day today life and procedure to solve it.
2007-01-09 23:22:46 · 1 answers · asked by Pinky 1 in Science & Mathematics ➔ Mathematics
Well, you can't do it without ANY graph theory, because it's all about graphs. But I can try to give an easier explanation.
I hope you understand what a graph is. It's just a collection of nodes (the circles) and edges (the lines between them). A WEIGHTED graph is a graph where each of the edges has a number, called a cost. A bigger cost is worse, a smaller number is better.
As a real-world example, think about a "graph" of with 3 nodes, where the three nodes represent Dallas, San Antonio, and Houston. If you wanted to go from Dallas to Houston, it would "cost" you 217 miles of travel, and that would be the shortest cost. But you COULD drive to San Antonio (cost 244 miles) and THEN to Houston (cost 179 miles), which would take you 244 + 179 = 423 miles. Obviously, you'd want to take the shortest path.
The purpose of a minimum spanning tree is to find a way to connect every node in the graph so that the sum of all the costs is minimum. This would be like deciding that you want to use electric wires to connect every city in the USA to one big electric network. Obviously, if you don't do it the best possible way, you'll waste a lot of wire and a lot of money. The interesting thing is that sometimes the shortest route between two cities is not the best way...the total is what matters, not the individual edges.
As far as a procedure to solve it, that's impossible to explain without graph theory. I'll just have to refer you to wikipedia for four algorithms to do it.
http://en.wikipedia.org/wiki/Minimal_spanning_tree#Algorithms
2007-01-10 03:21:14 · answer #1 · answered by Jim Burnell 6 · 0⤊ 0⤋