MATROID THEORY

The abstract structure of independence

7
0.45
5
A matroid (Whitney 1935) abstracts the notion of linear independence from vector spaces and forests from graph theory into a single axiom system. A matroid M = (E, I) consists of a ground set E and independent sets I satisfying: ∅ ∈ I, hereditary closure, and the augmentation axiom (if |A| < |B|, A can be extended by an element of B). The graphic matroid of a graph G has edges as ground set, with forests as independent sets — bases are spanning trees. The visualization shows a random graph with its spanning tree (in gold) highlighted via greedy/Kruskal algorithm. Matroids unify greedy algorithms: the greedy algorithm optimally finds a max-weight basis in any matroid, and conversely, greedy-solvability implies matroid structure (Rado-Edmonds theorem).