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.
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.
es un conjunto no vacío llamado subyacente de
[1] La propiedad 1 se puede leer como que el vacío siempre es independiente.
Es equivalente, por la propiedad 2, enunciar así la propiedad 1 que asegurar que el conjunto de independientes es no vacío,
, pues en el momento en que el vacío es independiente el conjunto de independientes es no vacío, y en el momento en que el conjunto de independientes es no vacío existe algún subconjunto de
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.
es un conjunto no vacío de elementos y
La propiedad 2, llamada propiedad del intercambio, nos dice que si tenemos dos bases de E y un elemento en una de ellas entonces existe un segundo elemento en la otra de forma que podemos intercambiarlos de forma que sigamos teniendo dos bases.
Las bases serán aquellos independientes que no son subconjunto de ningún otro independiente salvo ellas mismos.
es un conjunto no vacío de elementos y
[1] La propiedad 1 nos indica que el vacío no puede ser un circuito.
La propiedad 3 nos dice que dados dos circuitos y un elemento en su intersección, entonces existe un tercer circuito contenido en la unión de los dos primeros que no tiene a dicho elemento.
Los circuitos serán aquellos dependientes mínimos, es decir, tales que quitarles cualquiera de sus elementos haga al conjunto un independiente.
es un conjunto no vacío de elementos y
y codominio los enteros positivos con el cero que verifica las siguientes propiedades.
[2] La propiedad 1 nos indica que el vacío siempre tiene rango 0.
La propiedad 2 nos dice que al añadir un elemento a un subconjunto
el rango será siempre o el mismo que el de
La propiedad 3 nos asegura que dados dos conjuntos la suma de sus rangos es siempre mayor o igual que la suma de los rangos de su unión y su intersección.
es un conjunto no vacío de elementos y
y se verifican las siguientes propiedades: Sea
es llamado cierre, clausura u oclusión de
La propiedad 1 nos dice que todo conjunto está contenido en su clausura.
Dicha propiedad nos asegura que para cualesquiera dos elementos, si un primer elemento está en la clausura de un conjunto al que le añadimos el segundo elemento y no está en la clausura de dicho conjunto, entonces el segundo elemento está en la clausura del conjunto añadiéndole el primer elemento y no está en la clausura de dicho conjunto.
se le denomina sistema generador cuando verifica que
definido mediante sus independientes podemos ver que: Dada una matroide
definido mediante sus bases podemos ver que: Dada una matroide
definido mediante sus circuitos podemos ver que: Dada una matroide
definido mediante su aplicación rango podemos ver que: