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.

Una matroide M {\displaystyle M} es un par ordenado de elementos ( E , I ) {\displaystyle (E,I)} donde E {\displaystyle E} es un conjunto no vacío, llamado conjunto subyacente de M {\displaystyle M} , e I {\displaystyle I} es una colección de subconjuntos de E {\displaystyle E} , llamados conjuntos independientes, que cumplen las siguientes propiedades.^[1]​

1. El conjunto vacío pertenece a I {\displaystyle I} .
2. Si un conjunto pertenece a I {\displaystyle I} , todo subconjunto suyo pertenece también a I {\displaystyle I} .
3. Dados dos conjuntos I 1 , I 2 ∈ I {\displaystyle I_{1},I_{2}\in I} tales que | I 2 | < | I 1 | {\displaystyle |I_{2}|<|I_{1}|} , existe un elemento e ∈ I 1 ∖ I 2 {\displaystyle e\in I_{1}\setminus I_{2}} tal que el conjunto I 2 ∪ { e } {\displaystyle I_{2}\cup \{e\}} pertenece a I {\displaystyle I} .

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

Una matroide M {\displaystyle M} es un par ordenado de elementos ( E , B ) {\displaystyle (E,B)} donde E {\displaystyle E} es un conjunto no vacío de elementos y B {\displaystyle B} es una colección de subconjuntos de E {\displaystyle E} , denominados bases, tal que cumple las siguientes propiedades.

1. El conjunto B {\displaystyle B} es no vacío.
2. Dadas dos bases B 1 , B 2 ∈ B {\displaystyle B_{1},B_{2}\in B} y un elemento e ∈ B 1 {\displaystyle e\in B_{1}} , existe un elemento f ∈ B 2 {\displaystyle f\in B_{2}} que no pertenece a B 1 {\displaystyle B_{1}} y tal que el conjunto unión ( B 1 ∖ { e } ) ∪ { f } {\displaystyle (B_{1}\setminus \{e\})\cup \{f\}} es una base en B {\displaystyle B} .

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.

Una matroide M {\displaystyle M} es un par ordenado de elementos ( E , C ) {\displaystyle (E,C)} donde E {\displaystyle E} es un conjunto no vacío de elementos y C {\displaystyle C} es un subconjunto del conjunto potencia de E {\displaystyle E} que cumple las siguientes propiedades.^[1]​

1. ∅ ∉ C {\displaystyle \emptyset \notin C}
2. C 1 , C 2 ∈ C : C 1 ⊆ C 2 ⟹ C 1 = C 2 {\displaystyle C_{1},C_{2}\in C:C_{1}\subseteq C_{2}\implies C_{1}=C_{2}}
3. C 1 , C 2 ∈ C ∧ e ∈ C 1 ∩ C 2 ⟹ ∃ C 3 ∈ C : C 3 ⊆ C 1 ∪ C 2 ∖ { e } {\displaystyle 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\}} .

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 C x ∈ C {\displaystyle C_{x}\in C} distinto de C x {\displaystyle C_{x}} ) 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.

Una matroide M {\displaystyle M} es un par ordenado de elementos ( E , r ) {\displaystyle (E,r)} donde E {\displaystyle E} es un conjunto no vacío de elementos y r {\displaystyle r} es una aplicación de dominio el conjunto potencia de E {\displaystyle E} y codominio los enteros positivos con el cero que verifica las siguientes propiedades.^[2]​

1. r ( ∅ ) = 0 {\displaystyle r(\emptyset )=0}
2. r ( X ) ≤ r ( X ∪ { y } ) ≤ r ( X ) + 1 , ∀ X ⊆ E , ∀ y ∈ E {\displaystyle r(X)\leq r(X\cup \{y\})\leq r(X)+1,\forall X\subseteq E,\forall y\in E}
3. r ( X ∪ Y ) + r ( X ∩ Y ) ≤ r ( X ) + r ( Y ) , ∀ X , Y ⊆ E {\displaystyle r(X\cup Y)+r(X\cap Y)\leq r(X)+r(Y),\forall X,Y\subseteq E}

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 X {\displaystyle X} el rango será siempre o el mismo que el de X {\displaystyle X} o el de X {\displaystyle X} 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.

Una matroide M {\displaystyle M} es un par ordenado de elementos ( E , cl ) {\displaystyle (E,\operatorname {cl} )} donde E {\displaystyle E} es un conjunto no vacío de elementos y cl {\displaystyle \operatorname {cl} } es una aplicación cl : P ( E ) → P ( E ) {\displaystyle \operatorname {cl} :{\mathcal {P}}(E)\rightarrow {\mathcal {P}}(E)} , donde P ( E ) {\displaystyle {\mathcal {P}}(E)} es el conjunto potencia de E {\displaystyle E} y se verifican las siguientes propiedades:

1. X ⊆ cl ⁡ ( X ) , ∀ X ∈ P ( E ) {\displaystyle X\subseteq \operatorname {cl} (X),\forall X\in {\mathcal {P}}(E)}
2. X ⊆ Y ⟹ cl ⁡ ( X ) ⊆ cl ⁡ ( Y ) , ∀ X , Y ∈ P ( E ) {\displaystyle X\subseteq Y\implies \operatorname {cl} (X)\subseteq \operatorname {cl} (Y),\forall X,Y\in {\mathcal {P}}(E)}
3. cl ⁡ ( cl ⁡ ( X ) ) = cl ⁡ ( X ) , ∀ X ∈ P ( E ) {\displaystyle \operatorname {cl} (\operatorname {cl} (X))=\operatorname {cl} (X),\forall X\in {\mathcal {P}}(E)}
4. ∀ a , b ∈ E , ∀ X ⊆ E , a ∈ cl ⁡ ( X ∪ { b } ) ∖ cl ⁡ ( X ) ⟹ b ∈ cl ⁡ ( X ∪ { a } ) ∖ cl ⁡ ( X ) {\displaystyle \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)}

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

Dada una matroide ( E , I ) {\displaystyle (E,I)} definido mediante sus independientes podemos ver que:

1. El conjunto de bases de la matroide es B = { B x ∈ I : ∀ I x ∈ I , B x ⊆ I x ⟹ B x = I x } {\displaystyle B=\{B_{x}\in I:\forall I_{x}\in I,B_{x}\subseteq I_{x}\implies B_{x}=I_{x}\}}
2. El conjunto de circuitos de la matroide es C = { C x ∈ P ( E ) ∖ I : ∀ I x ⊊ C x , I x ∈ I } {\displaystyle C=\{C_{x}\in {\mathcal {P}}(E)\setminus I:\forall I_{x}\subsetneq C_{x},I_{x}\in I\}}
3. La aplicación rango de la matroide queda definida por r ( X ) = max { | A | : A ⊆ X ∧ A ∈ I } , ∀ X ∈ P ( E ) {\displaystyle r(X)=\max\{|A|:A\subseteq X\land A\in I\},\forall X\in {\mathcal {P}}(E)}

Dada una matroide ( E , B ) {\displaystyle (E,B)} definido mediante sus bases podemos ver que:

1. El conjunto de independientes de la matroide es I = { I x ⊆ E : ∃ B x ∈ B ( I x ⊆ B x ) } {\displaystyle I=\{I_{x}\subseteq E:\exists B_{x}\in B(I_{x}\subseteq B_{x})\}}
2. El conjunto de circuitos de la matroide es C = { C x ⊆ E : ∄ B x ∈ B ( C x ⊆ B x ) ∧ ∀ A ⊆ E ( ∄ B x ∈ B : A ⊆ B x ) , A ⊆ C x ⟹ C x = A } {\displaystyle 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\}}
3. La aplicación rango de la matroide queda definida por r ( X ) = max { | A | : A ⊆ X ∧ ∃ B x ∈ B ( A ⊆ B x ) } , ∀ X ∈ P ( E ) {\displaystyle r(X)=\max\{|A|:A\subseteq X\land \exists B_{x}\in B(A\subseteq B_{x})\},\forall X\in {\mathcal {P}}(E)}

Dada una matroide ( E , C ) {\displaystyle (E,C)} definido mediante sus circuitos podemos ver que:

1. El conjunto de independientes de la matroide es I = { I x ⊆ E : ∄ C x ∈ C ( C x ⊆ I x ) } {\displaystyle I=\{I_{x}\subseteq E:\nexists C_{x}\in C(C_{x}\subseteq I_{x})\}}
2. El conjunto de bases de la matroide es B = { B x ⊆ E : ∄ C x ∈ C ( C x ⊆ B x ) ∧ ∀ I x ⊆ E ( ∄ C x ∈ C : C x ⊆ I x ) , B x ⊆ I x ⟹ B x = I x } {\displaystyle 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}\}}
3. La aplicación rango de la matroide queda definida por r ( X ) = max { | A | : A ⊆ X ∧ ∄ C x ∈ C ( C x ⊆ A ) } , ∀ X ∈ P ( E ) {\displaystyle r(X)=\max\{|A|:A\subseteq X\land \nexists C_{x}\in C(C_{x}\subseteq A)\},\forall X\in {\mathcal {P}}(E)}

Dada una matroide ( E , r ) {\displaystyle (E,r)} definido mediante su aplicación rango podemos ver que:

1. El conjunto de independientes de la matroide es I = { I x ⊆ E : r ( I x ) = | I x | } {\displaystyle I=\{I_{x}\subseteq E:r(I_{x})=|I_{x}|\}}
2. El conjunto de bases de la matroide es B = { B x ⊆ E : ∀ e ∈ E , r ( B x ∪ { e } ) = r ( B x ) = | B x | } {\displaystyle B=\{B_{x}\subseteq E:\forall e\in E,r(B_{x}\cup \{e\})=r(B_{x})=|B_{x}|\}}
3. El conjunto de circuitos de la matroide es C = { C x ⊆ E : ∀ e ∈ E , r ( C x ∖ { e } ) = r ( C x ) = | C x | − 1 } {\displaystyle C=\{C_{x}\subseteq E:\forall e\in E,r(C_{x}\setminus \{e\})=r(C_{x})=|C_{x}|-1\}}
4. El operador clausura de la matroide queda definido por cl ⁡ ( A ) = { e ∈ E : r ( A ) = r ( A ∪ { e } ) } , ∀ A ∈ P ( E ) {\displaystyle \operatorname {cl} (A)=\{e\in E:r(A)=r(A\cup \{e\})\},\forall A\in {\mathcal {P}}(E)}