Diferencia entre revisiones de «Matroide»

← Ir a diferencia anterior Ir a siguiente diferencia →

Contenido eliminado Contenido añadido

En renglón

Revisión del 01:56 19 abr 2018

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.

Definición 1. (Por conjuntos independientes)

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

$\emptyset \in I$
Si $I_{1}\in I$ y $I_{2}\subseteq I_{1}$ entonces $I_{2}\in I$
Si $I_{1},I_{2}\in I$ y $|I_{2}|<|I_{1}|$ entonces existe $e\in I_{1}\setminus I_{2}$ tal que: $I_{2}\cup \{e\}\in I$

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 $E$ es llamado el conjunto subyacente de $M$ , Los elementos en $I$ son llamados conjuntos independientes y los subconjuntos del conjunto potencia de $E$ que no están en $I$ son llamados conjuntos dependientes.

Definición 2. (Por bases)

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

$\emptyset \neq B$ ( $B$ es no vacio).
si $B_{1},B_{2}\in B$ y $e\in B_{1}$ entonces existe un elemento $f\in B_{2}\setminus B_{1}$ tal que $((B_{1}\setminus {e})\cup {f})\in B$ (propiedad de intercambio)

Los elementos en $B$ son llamados Bases.

Definición 3. (Por circuitos)

Una matroide es un par ordenado de elementos $(E,C)$ 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]

$\emptyset \notin C$
Si $C_{1},C_{2}\in C$ tales que $C_{1}\subseteq C_{2}$ entonces $C_{1}=C_{2}$
Si $C_{1},C_{2}\in C$ y $e\in C_{1}\cap C_{2}$ entonces existe $C_{3}\in C$ tal que $C_{3}\subseteq C_{1}\cup C_{2}\setminus {e}$ .

↑ Oxley, James G. (1992). «1». Matroid Theory (en ingles). Oxford University Press. p. 8. ISBN 0-19-853563-5.
↑ ^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 de abril de 2018.
↑ Aigner, Martin (1979). «4». Combinatorial Theory (en inglés). Springer. p. 256. ISBN 3-540-61787-6.

[1] Oxley, James G. (1992). «1». Matroid Theory (en ingles). Oxford University Press. p. 8. ISBN 0-19-853563-5.

[:0-2] Pico Sánchez, Wilson. «Temas de representabilidad de matroides sobre campos finitos e infinitos». Tesis de maestría, universidad de Colombia. Consultado el 18 de abril de 2018.

[3] Aigner, Martin (1979). «4». Combinatorial Theory (en inglés). Springer. p. 256. ISBN 3-540-61787-6.

[1]

[2]

[3]

@@ Línea 24: / Línea 24: @@
 ==== Definición 2. (Por bases) ====
-Una '''matroide''' es un par ordenado de elementos <math>(E,B)</math> donde <math>E</math> es un conjunto no vacio de elementos y <math>B</math> es un subconjunto del conjunto potencia de E, tal que cumple las siguientes propiedades.<ref name=":0" />
+Una '''matroide''' es un par ordenado de elementos <math>(E,B)</math> donde <math>E</math> es un conjunto no vacio de elementos y <math>B</math> es un subconjunto del conjunto potencia de E, tal que cumple las siguientes propiedades.<ref name=":0" /><ref>{{Cita libro|apellidos=Aigner|nombre=Martin|enlaceautor=|título=Combinatorial Theory|url=|fechaacceso=|año=1979|editorial=Springer|isbn=3-540-61787-6|editor=|ubicación=|página=256|idioma=Inglés|capítulo=4}}</ref>
 #<math>\emptyset \neq B</math> (<math>B</math> es no vacio).