I have an exercise to solve and the teacher told me I had to use this method to solve it. What is minimum tree generation and how can I use it in practice?
What is a minimum generating tree?
15
asked by anonymous 24.06.2014 / 04:32
1 answer
17
A generating tree in a graph you already know, even without knowing: P
Think of this graph here (which got ugly, but for something automated until it's okay: P)
Ageneratingtreeissimplyasetofedgesofthegraphthatgeneratesatree:PAtreeandanacyclicconnectedgraph.Butitiseasiertoimaginethatthesamegraphwithatleastoneedgeenteringandatmostone(ieneednothaveone)edgecomingoutofeachvertex.
Forexample,ageneratingtreeintheabovegraphmightbethis:
The two classic algorithms in graphs, depth search and search width induce generating trees in the graph. That's why you already knew them!
The weight of this tree and the sum of the values associated with its edges, in this case:
5 + 8 + 4 + 7 + 3 = 27
A generating tree is called minimum if, among all the generating trees in the graph, the sum of the weights on the edges of the graph is as small as possible.
In this graph, an MST (minimum spanning tree) can be:
Theweightofthisis:
1+3+3+4+8==19TwofamousalgorithmsforfindingaMSTare Prim and Kruskal .
Just like almost everything legal in graphs, MSTs have several applications. You can take a look at here (unfortunately, in English, I did not find a good page in Portuguese).
But as an example of some use, imagine that we have cities that need to be linked by roads (a classic, no?). If we want to build the minimum number of roads that connect all cities and, not only, have the lowest cost. The solution is an MST. Or you can play OBI trouble : P
04.09.2014 / 15:04