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.
Definiciones.
[editar]Definición 1. (Por conjuntos independientes)
[editar]Una matroide es un par ordenado de elementos donde es un conjunto no vacío llamado subyacente de e es un subconjunto del conjunto potencia de que cumplen las siguientes propiedades.[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 que es independiente y el vacío será subconjunto de este, y por ende 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.
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 vacío de elementos y es un subconjunto del conjunto potencia de , tal que cumple las siguientes propiedades.
Los elementos en son llamados bases.
La propiedad 1 nos asegura la existencia de bases.
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.
Definición 3. (Por circuitos)
[editar]Una matroide es un par ordenado de elementos donde es un conjunto no vacío de elementos y es un subconjunto del conjunto potencia de que cumple las siguientes propiedades.[1]
- .
La propiedad 1 nos indica que el vacío no puede ser un circuito.
La propiedad 2 nos asegura que el subconjunto propio de un circuito (subconjunto de distinto de ) no puede ser otro 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.
Definición 4. (Por aplicación rango)
[editar]Una matroide es un par ordenado de elementos donde es un conjunto no vacío de elementos y es una aplicación de dominio el conjunto potencia de 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 o el de más 1.
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.
Definición 5. (Por operador cierre)
[editar]Una matroide es un par ordenado de elementos donde es un conjunto no vacío de elementos y es una aplicación , donde es el conjunto potencia de y se verifican las siguientes propiedades:
Sea , el conjunto es llamado cierre, clausura u oclusión de , y dicha aplicación es llamada operacior clausura, operador cierre u operador de oclusión de la matroide, donde en general un operador de oclusión de un conjunto cualquiera es aquella aplicación que verifica las tres primeras propiedades.
La propiedad 1 nos dice que todo conjunto está contenido en su clausura.
La propiedad 2 nos asegura que si un conjunto está contenido en otro, su clausura estará contenida en la del otro.
La propiedad 3 nos indica que la clausura de la clausura de un conjunto es ella misma.
La cuarta propiedad, a menudo llamada propiedad de intercambio de Mac Lane–Steinitz, es propia del operador clausura de una matroide, que respecto de la definición de dicho matroide mediante la aplicación rango es definida como . 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.
Adicionalmente, a un conjunto se le denomina sistema generador cuando verifica que , es decir, su clausura es todo .
Equivalencia entre definiciones
[editar]Dada una matroide definido mediante sus independientes podemos ver que:
- El conjunto de bases de la matroide es
- El conjunto de circuitos de la matroide es
- La aplicación rango de la matroide queda definida por
Dada una matroide definido mediante sus bases podemos ver que:
- El conjunto de independientes de la matroide es
- El conjunto de circuitos de la matroide es
- La aplicación rango de la matroide queda definida por
Dada una matroide definido mediante sus circuitos podemos ver que:
- El conjunto de independientes de la matroide es
- El conjunto de bases de la matroide es
- La aplicación rango de la matroide queda definida por
Dada una matroide definido mediante su aplicación rango podemos ver que:
- El conjunto de independientes de la matroide es
- El conjunto de bases de la matroide es
- El conjunto de circuitos de la matroide es
- El operador clausura de la matroide queda definido por
Referencias
[editar]- ↑ a b Oxley, James G. (1992). «1». Matroid Theory (en inglés). Oxford University Press. p. 8. ISBN 0-19-853563-5. (requiere registro).
- ↑ Welsh, D. J. A. (2010). Matroid theory (Dover ed edición). Dover Publications. ISBN 978-0-486-47439-7. OCLC 319491697. Consultado el 13 de junio de 2021.
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.