In combinatorics, a branch of mathematics, a weighted matroid is a matroid endowed with a function that assigns a weight to each element. Formally, let M = ( E , I ) {\displaystyle M=(E,I)} be a matroid, where E is the set of elements and I is the family of independent set. A weighted matroid has a weight function w : E → R + {\displaystyle w:E\rightarrow \mathbb {R} ^{+}} for assigns a strictly positive weight to each element of E {\displaystyle E} . We extend the function to subsets of E {\displaystyle E} by summation; w ( A ) {\displaystyle w(A)} is the sum of w ( x ) {\displaystyle w(x)} over x {\displaystyle x} in A {\displaystyle A} .
Finding a maximum-weight independent set A basic problem regarding weighted matroids is to find an independent set with a maximum total weight. This problem can be solved using the following simple greedy algorithm:
Initialize the set A to an empty set. Note that, by definition of a matroid, A is an independent set. For each element x in E\A, check whether Au{x} is still an independent set. If there are no such elements, then stop, as A cannot be extended anymore. If there is at least one such element, then choose the one with maximum weight, and add it to A. This algorithm does not need to know anything about the matroid structure; it just needs an independence oracle for the matroid - a subroutine for testing whether a set is independent. Jack Edmonds proved that this simple algorithm indeed finds an independent set with maximum weight. Denote the set found by the algorithm by e1,...,ek. By the matroid properties, it is clear that k=rank(M), otherwise the set could be extended. Assume by contradiction that there is another set with a higher weight. Without loss of generality, it is possible to assume that this set has rank(M) elements too; denote it by f1,...,fk. Order these items such that w(f1) ≥ ... ≥ w(fk). Let j be the first index for which w(fj) > w(ej). Apply the augmentation property to the sets {f1,...,fj} and {e1,...,ej-1}; we conclude that there must be some i ≤ j such that fi could be added to {e1,...,ej-1} while keeping it independent. But w(fi) ≥ w(fj) > w(ej), so fi should have been chosen in step j instead of ej - a contradiction.
Example: 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. It can be solved by Kruskal's algorithm, which can be seen as the special case of the above greedy algorithm to a graphical matroid. If we look at the definition of the forest matroid, 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 A {\displaystyle A} be the empty set. For each x {\displaystyle x} in E {\displaystyle E}
if A ∪ { x } {\displaystyle A\cup \{x\}} is independent, then set A {\displaystyle A} to A ∪ { x } {\displaystyle A\cup \{x\}} . The result is clearly an independent set. It is a maximal independent set because if B ∪ { x } {\displaystyle B\cup \{x\}} is not independent for some subset B {\displaystyle B} of A {\displaystyle A} , then A ∪ { x } {\displaystyle A\cup \{x\}} 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:
… excerpt ends here. Continue reading the full article.
