Matroid

A matroid is a finite set equipped with a family of subsets called independent sets, satisfying axioms that generalize linear independence and graph acyclicity.

Independence system: A set system is a ground set together with a collection of its subsets. Matroids are set systems whose independent subsets obey additional exchange rules.
Linear matroid: A matroid whose independent sets are linearly independent subsets of a vector configuration. It realizes matroid independence as ordinary linear independence.
Matroid greedy algorithm: An algorithm that processes weighted elements in order and accepts each when independence is preserved. The matroid exchange property is exactly what makes this greedy procedure optimal for every weight ordering.
Hassler Whitney: An American mathematician who introduced matroids in a 1935 paper on abstract properties of linear dependence. Whitney gave the structure its foundational formulation and name.
Exchange axiom: An axiom requiring that one of two unequal independent sets can be enlarged using an element of the larger set. This augmentation rule distinguishes matroid independence from arbitrary hereditary set systems.
Graphic matroid: A matroid whose independent edge sets are forests in a graph. A graph's cycles are precisely the dependent sets in this standard example.
Kruskal's algorithm: A greedy algorithm that builds a minimum spanning forest by accepting edges that join distinct components. It is the graphic-matroid instance of greedy optimization.
N. L. White: A mathematician known for work on matroid theory and for editing major collections on the subject. White's editorial work documents the development and breadth of matroid theory.
Basis (matroid theory): A maximal independent set of a matroid; all bases have the same size. Bases are the maximal independent sets governed by the basis-exchange property.
Cographic matroid: The dual of a graph's cycle matroid, with bonds as its circuits. It shows how matroid duality translates graph structure into a second matroid.

Linked from 9 pages