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 has from the first expanded the minute blossoms of the forest only toward the heavens, above men’s heads and unobserved by them. We see only the flowers that are under our feet in the meadows.”
—Henry David Thoreau (1817–1862)