Matroide

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

La combinatoria, una rama de las matemáticas, llama matroide a una estructura que toma y generaliza el concepto de independencia lineal en los espacios vectoriales.

Hay muchas maneras equivalentes de definir a una matroide y muchos conceptos dentro de la teoría de matroides tienen una serie de formulaciones diferentes. Dependiendo de cuán sofisticado sea el concepto, puede resultar no trivial el mostrar que las diversas formulaciones son equivalentes, un fenómeno conocido como criptomorfismo. Entre las definiciones importantes de matroides se incluyen aquellas en forma de conjuntos independientes, bases, circuitos, conjuntos cerrados o flats, operadores de oclusión y funciones de rango.

La teoría de matroides se basa en gran parte en la terminología del álgebra lineal y de la teoría de grafos, sobre todo porque es la abstracción de varias nociones muy importantes en estos campos.