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.

Definiciones.[editar]

Definición 1. (Por conjuntos independientes)[editar]

Una matroide es un par ordenado de elementos donde es un conjunto finito e es un subconjunto del conjunto potencia de que cumplen las siguientes propiedades[1]​:

  1. Si y entonces
  2. Si y entonces existe tal que:

La propiedad 1 se puede leer como que el vació 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. [2]

El conjunto es llamado el conjunto subyacente de , Los elementos en son llamados conjuntos independientes y los subconjuntos del conjunto potencia de que no están en son llamados conjuntos dependientes.

Definición 2. (Por bases)[editar]

Una matroide es un par ordenado de elementos donde es un conjunto no vacio de elementos y es un subconjunto del conjunto potencia de E, tal que cumple las siguientes propiedades.[2][3]

  1. ( es no vacio).
  2. si y entonces existe un elemento tal que (propiedad de intercambio)

Los elementos en son llamados Bases.

Definición 3. (Por circuitos)[editar]

Una matroide es un par ordenado de elementos donde E es un conjunto no vacio de elementos y C es un subconjunto del conjunto potencia de E que cumple las siguientes propiedades.[2][1]

  1. Si tales que entonces
  2. Si y entonces existe tal que .

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 vacio, en el segundo se pide que el vacio no sea un circuito.

  1. a b Oxley, James G. (1992). «1». Matroid Theory (en ingles). Oxford University Press. p. 8. ISBN 0-19-853563-5. 
  2. a b c Pico Sánchez, Wilson. «Temas de representabilidad de matroides sobre campos finitos e infinitos». Tesis de maestría, universidad de Colombia. Consultado el 18/04/2018. 
  3. Aigner, Martin (1979). «4». Combinatorial Theory (en inglés). Springer. p. 256. ISBN 3-540-61787-6.