# Matroid

### From Glossary

This is an abstraction of independence that
includes vectors in linear algebra and circuits in graphs. First, we need some
preliminary definitions. Let be a finite set, and let
be a collection of subsets of . is an
*independence system* if in implies every subset of is
in . Elements of are called *independent sets*, and the
remaining subsets of are called *dependent sets*. An
independent set, say , is *maximal* if is not in
for any . The *max-cardinality independent set* of
any subset of , say is given by:

A *matroid* is an independence system in which for
any subset of , say , every independent set in that is maximal
in has cardinality . The definition essentially means that
*maximal* and *maximum* are the same. In other words, a
system is a matroid if, and only if, a greedy algorithm
yields a globally optimal solution to the associated max weight problem. An
example is the spanning tree.