What is a minimal generating tree?

Question

I have an exercise to solve and the teacher told me that I would just use this method to solve. What is a minimal generating tree and how can I use it in practice?

Answer 1

One generating tree in a graph you already know, even without knowing!

Think of this graph here (which turned 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 coming in and at most one (ie not necessarily one) edge coming out of each vertex.

For example, a generating tree in the above graph may be this:

The two classical algorithms in graphs, the deep-sea search and the search in width, induce generating trees in the graph. So you already knew them!

The heaviness 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 minimal if, among all the generating trees that exist in the graph, the sum of the weights on its edges is the smallest 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 the Prim and that 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 also have the lowest cost. The solution is an MST! Or you can play at doing OBI’s little problem :P.