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:
“Nature herself has not provided the most graceful end for her creatures. What becomes of all these birds that people the air and forest for our solacement? The sparrow seems always chipper, never infirm. We do not see their bodies lie about. Yet there is a tragedy at the end of each one of their lives. They must perish miserably; not one of them is translated. True, “not a sparrow falleth to the ground without our Heavenly Father’s knowledge,” but they do fall, nevertheless.”
—Henry David Thoreau (1817–1862)