Matroide

La combinatòria, una branca de les matemàtiques, flama matroide a una estructura que pren i generalisa el concepte d'independència llineal en els espais vectorials.

Hi ha moltes maneres equivalents de definir una matroide i molts conceptes dins de la teoria de matroides tenen una série de formulació diferents. Depenent de cuán sofisticat siga el concepte, pot resultar no trivial el demostrar que les diverses formulació són equivalents, un fenomen conegut com criptomorfismo. Entre les definicions importants de matroides s'inclouen aquelles en forma de conjunts independents, bases, circuits, conjunts tancats o flats, operadors d'oclusió i funcions de ranc.

La teoria de matroides es basa en gran part en la terminologia del àlgebra llineal i de la teoria de grafos, sobretot perque és l'abstracció de vàries nocions molt importants en estos camps.

Definicions.

Definició per conjunts independents

Una matroide $M$ és un parell ordenat d'elements $(E, I)$ a on $E$ és un conjunt no buit, cridat conjunt subjacent de $M$ , i $I$ és una colecció de subconjunts de $E$ , cridats conjunts independents, que complixen les següents propietats.^[1]

El conjunt buit pertany a $I$ .
Si un conjunt pertany a $I$ , tot subconjunt seu pertany també a $I$ .
Donats dos conjunts $I_{1}, I_{2} \in I$ tals que $| I_{2} | < | I_{1} |$ , existix un element $e \in I_{1} ∖ I_{2}$ tal que el conjunt $I_{2} \cup {e}$ pertany a $I$ .

La propietat 1 es pot llegir com que el buit sempre és independent. És equivalent, per la propietat 2, enunciar aixina la propietat 1 que assegurar que el conjunt d'independents és no buit, $I \neq \emptyset$ , puix en el moment en que el buit és independent el conjunt d'independents és no buit, i en el moment en que el conjunt d'independents és no buit existix algun subconjunt de $E$ que és independent i el buit serà subconjunt d'est, i per això independent.

La propietat 2 la podem interpretar com que qualsevol subconjunt d'un conjunt independent és també independent.

La propietat 3 nos diu que si tenim dos conjunts independents de diferent cardinalidad, sempre és possible trobar un element en el conjunt més gran tal que si li l'agreguem al chic el resultat és també un conjunt independent.

Els elements en $I$ són cridats conjunts independents i els subconjunts del conjunt potencia de $E$ que no estan en $I$ són cridats conjunts depenents.

Definició per bases

Una matroide $M$ és un parell ordenat d'elements $(E, B)$ a on $E$ és un conjunt no buit d'elements i $B$ és una colecció de subconjunts de $E$ , denominats bases, tal que complix les següents propietats.

El conjunt $B$ és no buit.
Donades dos bases $B_{1}, B_{2} \in B$ i un element $e \in B_{1}$ , existix un element $f \in B_{2}$ que no pertany a $B_{1}$ i tal que el conjunt unió $(B_{1} ∖ {e}) \cup {f}$ és una base en $B$ .

La propietat 1 nos assegura l'existència de bases.

La propietat 2, cridada propietat de l'intercanvi, nos diu que si tenim dos bases d'I i un element en una d'elles llavors existix un segon element en l'atra de manera que podem intercanviar-los de manera que seguim tenint dos bases.

Les bases seran aquells independents que no són subconjunt de cap atre independent llevat elles mateixos.

Definició 3. (Per circuits)

Una matroide $M$ és un parell ordenat d'elements $(E, C)$ a on $E$ és un conjunt no buit d'elements i $C$ és un subconjunt del conjunt potencia de $E$ que complix les següents propietats.^[1]

$\emptyset \notin C$
$C_{1}, C_{2} \in C : C_{1} \subseteq C_{2} ⟹ C_{1} = C_{2}$
$C_{1}, C_{2} \in C \land e \in C_{1} \cap C_{2} ⟹ \exists C_{3} \in C : C_{3} \subseteq C_{1} \cup C_{2} ∖ {e}$ .

La propietat 1 nos indica que el buit no pot ser un circuit.

La propietat 2 nos assegura que el subconjunt propi d'un circuit (subconjunt de $C_{x} \in C$ distint de $C_{x}$ ) no pot ser un atre circuit.

La propietat 3 nos diu que daus dos circuits i un element en la seua intersecció, llavors existix un tercer circuit contingut en l'unió dels dos primers que no té a dit element.

Els circuits seran aquells dependents mínims, és dir, tals que llevar-los qualsevol dels seus elements faça al conjunt un independent.

Definició 4. (Per aplicació ranc)

Una matroide $M$ és un parell ordenat d'elements $(E, r)$ a on $E$ és un conjunt no buit d'elements i $r$ és una aplicació de domini el conjunt potencia de $E$ i codominio els sancers positius en el zero que verifica les següents propietats.^[2]

$r (\emptyset) = 0$
$r (X) \leq r (X \cup {y}) \leq r (X) + 1, \forall X \subseteq E, \forall y \in E$
$r (X \cup Y) + r (X \cap Y) \leq r (X) + r (Y), \forall X, Y \subseteq E$

La propietat 1 nos indica que el buit sempre té ranc 0.

La propietat 2 nos diu que en afegir un element a un subconjunt $X$ el ranc serà sempre o el mateix que el de $X$ o el de $X$ més 1.

La propietat 3 nos assegura que daus dos conjunts la suma dels seus rancs és sempre major o igual que la suma dels rancs de la seua unió i la seua intersecció.

Definició 5. (Per operador tanque)

Una matroide $M$ és un parell ordenat d'elements $(E, cl)$ a on $E$ és un conjunt no buit d'elements i $cl$ és una aplicació $cl : 𝒫 (E) \to 𝒫 (E)$ , a on $𝒫 (E)$ és el conjunt potencia de $E$ i es verifiquen les següents propietats:

$X \subseteq cl (X), \forall X \in 𝒫 (E)$
$X \subseteq Y ⟹ cl (X) \subseteq cl (Y), \forall X, Y \in 𝒫 (E)$
$cl (cl (X)) = cl (X), \forall X \in 𝒫 (E)$
$\forall a, b \in E, \forall X \subseteq E, a \in cl (X \cup {b}) ∖ cl (X) ⟹ b \in cl (X \cup {a}) ∖ cl (X)$

Siga $X \subseteq E$ , el conjunt $cl (X)$ és cridat tancament, clausura o oclusió de $X$ , i dita aplicació $cl$ és cridada operacior clausura, operador tanque o operador d'oclusió de la matroide, a on en general un operador d'oclusió d'un conjunt qualsevol $S$ és aquella aplicació $cl : 𝒫 (S) \to 𝒫 (S)$ que verifica les tres primeres propietats.

La propietat 1 nos diu que tot conjunt està contingut en la seua clausura.

La propietat 2 nos assegura que si un conjunt està contingut en un atre, la seua clausura estarà continguda en la de l'atre.

La propietat 3 nos indica que la clausura de la clausura d'un conjunt és ella mateixa.

La quarta propietat, a sovint cridada propietat d'intercanvi de Mac Lane–Steinitz, és pròpia de l'operador clausura d'una matroide, que respecte de la definició de dit matroide per mig de l'aplicació ranc és definida com $cl (A) = {e \in E : r (A) = r (A \cup {e})}$ . Dita propietat nos assegura que per a qualssevol dos elements, si un primer element està en la clausura d'un conjunt al que li afegim el segon element i no està en la clausura de dit conjunt, llavors el segon element està en la clausura del conjunt afegint-li el primer element i no està en la clausura de dit conjunt.

Adicionalment, a un conjunt $X \subseteq E$ se li denomina sistema generador quan verifica que $cl (X) = E$ , és dir, la seua clausura és tot $E$ .

Equivalència entre definicions

Donada una matroide $(E, I)$ definit per mig dels seus independents podem vore que:

El conjunt de bases de la matroide és $B = {B_{x} \in I : \forall I_{x} \in I, B_{x} \subseteq I_{x} ⟹ B_{x} = I_{x}}$
El conjunt de circuits de la matroide és $C = {C_{x} \in 𝒫 (E) ∖ I : \forall I_{x} ⊊ C_{x}, I_{x} \in I}$

L'aplicació ranc de la matroide queda definida per $r (X) = \max {| A | : A \subseteq X \land A \in I}, \forall X \in 𝒫 (E)$

Donada una matroide $(E, B)$ definit per mig de les seues bases podem vore que:

El conjunt d'independents de la matroide és $I = {I_{x} \subseteq E : \exists B_{x} \in B (I_{x} \subseteq B_{x})}$
El conjunt de circuits de la matroide és $C = {C_{x} \subseteq E : ∄ B_{x} \in B (C_{x} \subseteq B_{x}) \land \forall A \subseteq E (∄ B_{x} \in B : A \subseteq B_{x}), A \subseteq C_{x} ⟹ C_{x} = A}$
L'aplicació ranc de la matroide queda definida per $r (X) = \max {| A | : A \subseteq X \land \exists B_{x} \in B (A \subseteq B_{x})}, \forall X \in 𝒫 (E)$

Donada una matroide $(E, C)$ definit per mig dels seus circuits podem vore que:

El conjunt d'independents de la matroide és $I = {I_{x} \subseteq E : ∄ C_{x} \in C (C_{x} \subseteq I_{x})}$
El conjunt de bases de la matroide és $B = {B_{x} \subseteq E : ∄ C_{x} \in C (C_{x} \subseteq B_{x}) \land \forall I_{x} \subseteq E (∄ C_{x} \in C : C_{x} \subseteq I_{x}), B_{x} \subseteq I_{x} ⟹ B_{x} = I_{x}}$
L'aplicació ranc de la matroide queda definida per $r (X) = \max {| A | : A \subseteq X \land ∄ C_{x} \in C (C_{x} \subseteq A)}, \forall X \in 𝒫 (E)$

Donada una matroide $(E, r)$ definit per mig de la seua aplicació ranc podem vore que:

El conjunt d'independents de la matroide és $I = {I_{x} \subseteq E : r (I_{x}) = | I_{x} |}$
El conjunt de bases de la matroide és $B = {B_{x} \subseteq E : \forall e \in E, r (B_{x} \cup {e}) = r (B_{x}) = | B_{x} |}$
El conjunt de circuits de la matroide és $C = {C_{x} \subseteq E : \forall e \in E, r (C_{x} ∖ {e}) = r (C_{x}) = | C_{x} | - 1}$
L'operador clausura de la matroide queda definit per $cl (A) = {e \in E : r (A) = r (A \cup {e})}, \forall A \in 𝒫 (E)$

Referències

↑ ^1,0 ^1,1 Oxley, James G. (1992). «1», Matroid Theory (en Anglés), Oxford University Press, p. 8. ISBN 0-19-853563-5.
↑ Welsh, D. J. A. (2010). Matroid theory, Dover ed edició, Dover Publications. OCLC 319491697. ISBN 978-0-486-47439-7.

Este artícul conté una traducció derivada de «Matroide» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

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

[2] Welsh, D. J. A. (2010). Matroid theory, Dover ed edició, Dover Publications. OCLC 319491697. ISBN 978-0-486-47439-7.

[1]

[2]