Matroid

From Glossary

Jump to: navigation, search

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

LaTeX: m(T) = \max \{ |S_i|: S_i \in M, \, S_i \subseteq T\}.

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


Views
Personal tools