Spanning Forest Algorithms
As a simple example, say we wish to find the maximum spanning forest of a graph. That is, given a graph and a weight for each edge, find a forest containing every vertex and maximizing the total weight of the edges in the tree. This problem arises in some clustering applications. If we look at the definition of the forest matroid above, we see that the maximum spanning forest is simply the independent set with largest total weight — such a set must span the graph, for otherwise we can add edges without creating cycles. But how do we find it?
Read more about this topic: Weighted Matroid
Famous quotes containing the word forest:
“Our democracy, our culture, our whole way of life is a spectacular triumph of the blah. Why not have a political convention without politics to nominate a leader who’s out in front of nobody?... Maybe our national mindlessness is the very thing that keeps us from turning into one of those smelly European countries full of pseudo-reds and crypto-fascists and greens who dress like forest elves.”
—P.J. (Patrick Jake)