For a matroid M on ground set E, a weight function on M is a function w : E -> ℝ, extended to all subsets of E by setting w(X) := ∑x∈X w(x). The greedy algorithm for finding a maximum-weight independent subset of E starts with the empty set, and proceeds by successively adding elements of E of maximum weight, which together with the elements already added, form an independent set.
In this method, a weight function is specified by its list of values on E. Thus if E = {e1, ..., en}, then w is represented as the list {w(e1), ..., w(en)}.
Matroids can be characterized via the greedy algorithm as follows: a set I of subsets of E is the set of independent sets of a matroid on E iff I is nonempty, downward closed, and for every weight function w : E -> ℝ, the greedy algorithm returns a maximal member of I of maximum weight.
i1 : M = matroid completeGraph 4 o1 = a matroid of rank 3 on 6 elements o1 : Matroid |
i2 : bases M o2 = {set {2, 4, 5}, set {1, 4, 5}, set {0, 4, 5}, set {2, 3, 5}, set {1, 3, ------------------------------------------------------------------------ 5}, set {0, 3, 5}, set {0, 2, 5}, set {0, 1, 5}, set {2, 3, 4}, set {1, ------------------------------------------------------------------------ 3, 4}, set {0, 3, 4}, set {1, 2, 4}, set {0, 1, 4}, set {1, 2, 3}, set ------------------------------------------------------------------------ {0, 2, 3}, set {0, 1, 2}} o2 : List |
i3 : w1 = apply(M_*, e -> (toList e)#1) o3 = {1, 2, 3, 2, 3, 3} o3 : List |
i4 : maxWeightBasis(M, w1) o4 = set {2, 4, 5} o4 : Set |
i5 : w2 = rsort w1 o5 = {3, 3, 3, 2, 2, 1} o5 : List |
i6 : maxWeightBasis(M, w2) o6 = set {0, 1, 2} o6 : Set |