From Wikipedia, the free encyclopedia Jump to: navigation,
search  In combinatorics, a branch of mathematics, a matroid
/ˈmtrɔɪd/ is a structure that captures and generalizes the
notion of linear independence in vector spaces. There are many
equivalent ways to define a matroid, the most significant being
in terms of independent sets, bases, circuits, closed sets or
flats, closure operators, and rank functions.  Matroid theory
borrows extensively from the terminology of linear algebra and
graph theory, largely because it is the abstraction of various
notions of central importance in these fields. Matroids have
found applications in geometry, topology, combinatorial
optimization, network theory and coding theory.[1][2]   There
are many equivalent (cryptomorphic) ways to define a (finite)
matroid.[3]  Independent sets[edit]  In terms of independence, a
finite matroid M is a pair (E,\mathcal{I}), where E is a finite
set (called the ground set) and \mathcal{I} is a family of
subsets of E (called the independent se