In combinatorics, a branch of mathematics, a weighted matroid is a matroid endowed with function with respect to which one can perform a greedy algorithm. A weight function for a matroid assigns a strictly positive weight to each element of . We extend the function to subsets of by summation; is the sum of over in . A matroid with an associated weight function is called a weighted matroid. 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? Finding a basis There is a simple algorithm for finding a basis: Initially let be the empty set. For each in if is independent, then set to . The result is clearly an independent set. It is a maximal independent set because if is not independent for some subset of , then is not independent either (the contrapositive follows from the hereditary property). Thus if we pass up an element, we'll never have an opportunity to use it later. We will generalize this algorithm to solve a harder problem. Extension to optimal An independent set of largest total weight is called an optimal set. Optimal sets are always bases, because if an edge can be added, it should be; this only increases the total weight. As it turns out, there is a trivial greedy algorithm for computing an optimal set of a weighted matroid. It works as follows: Initially let be the empty set. For each in , taken in (monotonically) decreasing order by weight if is independent, then set to . This algorithm finds a basis, since it is a special case of the above algorithm. It always chooses the element of largest weight that it can while preserving independence (thus the term "greedy"). This always produces an optimal set: suppose that it produces and that . Now for any with , consider open sets and