What is minimum generating tree?
I have an exercise to solve and the teacher told me it was enough to use this method to solve. What is minimum generating tree and how can I use it in practice?
1 answers
A generating tree in a graph you already know, even without knowing!
Think of that graph here (which got ugly, but for something automated until it's ok: P)
A generating tree is simply a set of edges of the graph that generates a tree.
Every tree is an acyclic connected graph. But it is easier to imagine the same graph with at least one edge entering and at most one (i.e. there is not necessarily one) edge coming out of each vertex.
For example, a generating tree in the graph above can be this:
The two classical graph algorithms, the depth search and the width search , induce generating trees in the graph. That's why you already knew them!
The Weight of this tree is 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 that exist on the graph, the sum of the weights at the edges of it is as small as possible.
In this graph, an MST (from English, minimum spanning tree ) can be:
The weight of this is:
1 + 3 + 3 + 4 + 8 == 19
Two famous algorithms for finding an MST are Prim it's the one of Kruskal .
Just like almost everything legal in graphs, MSTs has several applications. You can take a look 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 connected by roads (a classic, right?). If we want to build the minimum number of roads that connect all cities and that, too, have the lowest cost. The solution is an MST! Or you can play with Obi problem : P.