Matroid

Summary

A matroid is a finite set together with a notion of independence for its subsets that behaves like linear independence of vectors. Matroids abstract both linear independence in vector spaces and acyclic sets of edges (forests) in graphs. They have many equivalent descriptions, by independent sets, bases, rank functions, circuits or closure, and every matroid has a dual. Matroids explain why the greedy algorithm works and carry invariants such as the Tutte polynomial.