Matroid (source code)
= Matroid
{wiki}
A <matroid> is an <independence system> in which a smaller admissible selection can always grow using an element of a larger admissible selection. This exchange rule abstracts <linear independence> of <vectors> and the selection of <edges> forming a <forest>. It forces all <matroid bases> to have the same <cardinality> and makes the <matroid greedy algorithm> correct for maximizing their total weight. The useful surprise is that local choices become globally optimal because of a structural rule about admissible <subsets>, rather than a special numerical coincidence.
The <weighted three-vector matroid> below lets us inspect every <subset> and every possible size comparison. Its three <vectors> give three two-element <matroid bases>, yet their total weights differ. The <graphic matroid> of a <graph triangle> has exactly the same admissible labels. A <pregeometry> is a finitary closure-theoretic extension to possibly infinite <sets>.
Back to article page
