Ver el código de «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 [[espacio vectorial|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. ===

==== Definición 1. (Por conjuntos independientes) ====
Una '''matroide''' <math>M</math> es un [[par ordenado]] de elementos <math>(E,I)</math> donde <math>E</math> es un conjunto no vacío llamado subyacente de <math>M</math> e <math>I</math> es un subconjunto del [[conjunto potencia]] de <math>E</math> que cumplen las siguientes propiedades.<ref name=":1">{{Cita libro|apellidos=Oxley|nombre=James G.|enlaceautor=|título=Matroid Theory|url=https://archive.org/details/matroidtheory00oxle|url-access=registration|fechaacceso=|año=1992|editorial=Oxford University Press|isbn=0-19-853563-5|editor=|ubicación=|página=[https://archive.org/details/matroidtheory00oxle/page/n8 8]|idioma=Inglés|capítulo=1}}</ref>

# <math>\emptyset \in I</math>
# <math> I_1 \in I \land I_2 \subseteq I_1 \implies I_2 \in I </math>
# <math> I_1,I_2 \in I \land |I_2|<|I_1| \implies \exists e \in I_1 \setminus I_2 : I_2 \cup \{e\} \in I</math>

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, <math>I \neq \emptyset</math>, 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 <math>E</math> 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 <math>I</math> son llamados conjuntos independientes y los subconjuntos del conjunto potencia de <math>E</math> que no están en <math>I</math> son llamados conjuntos dependientes.

==== Definición 2. (Por bases) ====
Una '''matroide''' <math>M</math> es un par ordenado de elementos <math>(E,B)</math> donde <math>E</math> es un conjunto no vacío de elementos y <math>B</math> es un subconjunto del [[conjunto potencia]] de <math>E</math>, tal que cumple las siguientes propiedades.

#<math>B \neq \emptyset</math>
#<math>B_1,B_2 \in B \land e \in B_1 \implies \exists f \in B_2 \setminus B_1 : ((B_1 \setminus \{e\}) \cup \{f\}) \in B</math>

Los elementos en <math>B</math> 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) ====
Una '''matroide''' <math>M</math> es un par ordenado de elementos <math>(E,C)</math> donde <math>E</math> es un conjunto no vacío de elementos y <math>C</math> es un subconjunto del [[conjunto potencia]] de <math>E</math> que cumple las siguientes propiedades.<ref name=":1" />

#<math>\emptyset \notin C</math>
#<math>C_1,C_2 \in C : C_1 \subseteq C_2 \implies C_1 = C_2</math>
#<math>C_1,C_2 \in C \land e\in C_1 \cap C_2 \implies \exists C_3 \in C : C_3 \subseteq C_1\cup C_2 \setminus \{e\}</math>.

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 <math>C_x \in C</math> distinto de <math>C_x</math>) 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) ====
Una '''matroide''' <math>M</math> es un par ordenado de elementos <math>(E,r)</math> donde <math>E</math> es un conjunto no vacío de elementos y <math>r</math> es una aplicación de dominio el [[conjunto potencia]] de <math>E</math> y [[codominio]] los enteros positivos con el cero que verifica las siguientes propiedades.<ref>{{Cita libro|edición=Dover ed|título=Matroid theory|url=https://www.worldcat.org/oclc/319491697|editorial=Dover Publications|fecha=2010|fechaacceso=2021-06-13|isbn=978-0-486-47439-7|oclc=319491697|nombre=D. J. A.|apellidos=Welsh}}</ref>

#<math>r(\empty) = 0</math>
#<math>r(X) \leq r(X\cup\{y\}) \leq r(X)+1, \forall X \subseteq E, \forall y \in E</math> 
#<math>r(X \cup Y)+r(X \cap Y) \leq r(X)+r(Y), \forall X,Y \subseteq E</math>

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 <math>X</math> el rango será siempre o el mismo que el de <math>X</math> o el de <math>X</math> 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) ====
Una '''matroide''' <math>M</math> es un par ordenado de elementos <math>(E,\operatorname{cl})</math> donde <math>E</math> es un conjunto no vacío de elementos y <math>\operatorname{cl}</math> es una aplicación <math>\operatorname{cl}: \mathcal{P}(E) \rightarrow \mathcal{P}(E)</math>, donde <math>\mathcal{P}(E)</math> es el [[conjunto potencia]] de <math>E</math> y se verifican las siguientes propiedades:
#<math>X \subseteq \operatorname{cl}(X), \forall X \in \mathcal{P}(E)</math>
#<math>X \subseteq Y \implies \operatorname{cl}(X) \subseteq \operatorname{cl}(Y), \forall X,Y \in \mathcal{P}(E)</math>
#<math>\operatorname{cl}(\operatorname{cl}(X))=\operatorname{cl}(X), \forall X \in \mathcal{P}(E)</math>
#<math>\forall a,b \in E, \forall X \subseteq E, a \in \operatorname{cl}(X \cup \{b\}) \setminus \operatorname{cl}(X) \implies b \in \operatorname{cl}(X \cup \{a\}) \setminus \operatorname{cl}(X)</math>

Sea <math>X \subseteq E</math>, el conjunto <math>\operatorname{cl}(X)</math> es llamado cierre, clausura u oclusión de <math>X</math>, y dicha aplicación <math>\operatorname{cl}</math> 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 <math>S</math> es aquella aplicación <math>\operatorname{cl}: \mathcal{P}(S) \rightarrow \mathcal{P}(S)</math> 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 <math>\operatorname{cl}(A)=\{e \in E : r(A) = r(A \cup \{e\})\}</math>. 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 <math>X \subseteq E</math> se le denomina [[sistema generador]] cuando verifica que <math>\operatorname{cl}(X)=E</math>, es decir, su clausura es todo <math>E</math>.

=== Equivalencia entre definiciones ===

Dada una matroide <math>(E,I)</math> definido mediante sus independientes podemos ver que:

#El conjunto de bases de la matroide es <math>B = \{B_x \in I : \forall I_x \in I, B_x \subseteq I_x \implies B_x=I_x\}</math>
#El conjunto de circuitos de la matroide es <math>C = \{C_x \in \mathcal{P}(E) \setminus I : \forall I_x \subsetneq C_x, I_x \in I\}</math>
#La aplicación rango de la matroide queda definida por <math>r(X) = \max\{|A| : A \subseteq X \land A\in I\}, \forall X \in \mathcal{P}(E)</math>

Dada una matroide <math>(E,B)</math> definido mediante sus bases podemos ver que:

#El conjunto de independientes de la matroide es <math>I = \{I_x \subseteq E : \exists B_x \in B (I_x \subseteq B_x)\}</math>
#El conjunto de circuitos de la matroide es <math>C = \{C_x \subseteq E : \nexists B_x \in B (C_x \subseteq B_x) \land \forall A \subseteq E (\nexists B_x \in B : A \subseteq B_x), A \subseteq C_x \implies C_x = A\}</math>
#La aplicación rango de la matroide queda definida por <math>r(X) = \max\{|A| : A \subseteq X \land \exists B_x \in B (A \subseteq B_x)\}, \forall X \in \mathcal{P}(E)</math>

Dada una matroide <math>(E,C)</math> definido mediante sus circuitos podemos ver que:

#El conjunto de independientes de la matroide es <math>I = \{I_x \subseteq E : \nexists C_x \in C (C_x \subseteq I_x)\}</math>
#El conjunto de bases de la matroide es <math>B = \{B_x \subseteq E : \nexists C_x \in C (C_x \subseteq B_x) \land \forall I_x \subseteq E (\nexists C_x \in C : C_x \subseteq I_x), B_x \subseteq I_x \implies B_x = I_x\}</math>
#La aplicación rango de la matroide queda definida por <math>r(X) = \max\{|A| : A \subseteq X \land \nexists C_x \in C (C_x \subseteq A)\}, \forall X \in \mathcal{P}(E)</math>

Dada una matroide <math>(E,r)</math> definido mediante su aplicación rango podemos ver que:

#El conjunto de independientes de la matroide es <math>I = \{I_x \subseteq E : r(I_x) = |I_x|\}</math>
#El conjunto de bases de la matroide es <math>B = \{B_x \subseteq E : \forall e \in E, r(B_x \cup \{e\}) = r(B_x) = |B_x|\}</math>
#El conjunto de circuitos de la matroide es <math>C = \{C_x \subseteq E : \forall e \in E, r(C_x \setminus \{e\}) = r(C_x) = |C_x|-1\}</math>
#El operador clausura de la matroide queda definido por <math>\operatorname{cl}(A)=\{e \in E : r(A) = r(A \cup \{e\})\}, \forall A \in \mathcal{P}(E)</math>

== Referencias ==
{{listaref}}

{{Control de autoridades}}
[[Categoría:Combinatoria]]
[[Categoría:Dimensión]]
[[Categoría:Teorías de dualidad]]
[[Categoría:Operadores de cierre]]
[[Categoría:Teoría de matroides| ]]