Matroide

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 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 demostrar 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.

Una matroide ${displaystyle M}$ es un par ordenado de elementos ${displaystyle (E,I)}$ donde ${displaystyle E}$ es un conjunto finito e ${displaystyle I}$ es un subconjunto del conjunto potencia de ${displaystyle E}$ que cumplen las siguientes propiedades^[1]​:

La propiedad 1 se puede leer como que el vacío siempre es independiente.

La propiedad 2 la podemos interpretar como que cualquier subconjunto de un conjunto independiente es también independiente.

La propiedad 3 Nos dice que si tenemos dos conjuntos independientes de diferente cardinalidad, siempre es posible encontrar un elemento en el conjunto más grande tal que si se lo agregamos al chico el resultado es también un conjunto independiente.

El conjunto ${displaystyle E}$ es llamado el conjunto subyacente de ${displaystyle M}$, Los elementos en ${displaystyle I}$ son llamados conjuntos independientes y los subconjuntos del conjunto potencia de ${displaystyle E}$ que no están en ${displaystyle I}$ son llamados conjuntos dependientes.

Una matroide es un par ordenado de elementos ${displaystyle (E,B)}$ donde ${displaystyle E}$ es un conjunto no vacío de elementos y ${displaystyle B}$ es un subconjunto del conjunto potencia de E, tal que cumple las siguientes propiedades.

Los elementos en ${displaystyle B}$ son llamados Bases.

Una matroide es un par ordenado de elementos ${displaystyle (E,C)}$ donde E es un conjunto no vacío de elementos y C es un subconjunto del conjunto potencia de E que cumple las siguientes propiedades.^[1]​

Nótese que la propiedad 1 de las definiciones 2 y 3 no son para nada la misma propiedad, en el primer caso se pide que el conjunto de las bases no sea vacío, en el segundo se pide que el vacío no sea un circuito.