MATROID

Matroid - This is an abstraction of independence that includes vectors in linear algebra and circuits in graphs . First, we need some preliminary definitions. Let N=(1, ..., n) be a finite set, and let M=(S1, ..., Sm) be a collection of subsets of N. (N,M) is an independence system if Si in M implies every subset of Si is in M. Elements of M are called independent sets, and the remaining subsets of N are called dependent sets. An independent set, say Si, is maximal if Si\/(k) is not in M for any k in N\Si. The max-cardinality independent set of any subset of N, say T, is given by:

A matroid is an independence system (N, M) in which for any subset of N, say T, every independent set in T that is maximal in T has cardinality m(T). 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 .