ROUGH DRAFT authorea.com/109895
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • Matroid theory

    Abstract

    A matroid is a structure that generalizes the properties of independence. Interesting applications are found in graph theory. This paper will focus on the definitions of a matroid in terms of bases, the rank function, independent sets and cycles.

    Introducción

    Matroides

    \label{matroides}
    \label{M2}

    Un matroide \(M\), es un par \((E,I)\) donde \(E\) se llama conjunto base y \(I\) es una familia de subconjuntos de \(E\), donde los elementos de \(I\) serán referidos como independientes tal que

    1. 1.

      \label{M11}\(\emptyset\in I\)

    2. 2.

      Si \(X\in I\) entonces todo \(A\subset X\) cumple \(A\in I\).

    3. 3.

      Si \(X,Y\in I\) y \(|X|<|Y|\), entonces existe \(y\in Y\) tal que \(X\cup\{y\}\in I\).

    Una definición alternativa a matroide es la siguiente:

    \label{M1}

    Un matroide \(M\) consiste de un conjunto base \(E\neq\emptyset\), y una familia \(B\) de subconjuntos de \(E\), llamada base, de tal manera que satisface las siguientes propiedades:

    1. 1.

      Ninguna base contiene de manera propia otra base.

    2. 2.

      Si \(B_{1}\), \(B_{2}\) son bases y si \(\{e\}\) es cualquier elemento de \(B_{1}\) entonces existe un \(\{f\}\) de \(B_{2}\) tal que \((B_{1}-\{e\})\cup\{f\}\) es también base.

    \ref{M1} es equivalente a \ref{M2}

    Proof.

    Para demostrar la equivalencia entre \ref{M1} y \ref{M2} se procede de la siguiente forma.

    1. (i)

      \ref{M1} implica \ref{M2}. Sea \(B\) una familia de subconjuntos base de acuerdo a \ref{M1} entonces \(B\) cumple (1), (2) y (3) de \ref{M1}. (1). Usando el hecho de que \(E\neq\emptyset\) implica que \(B\neq\emptyset\), luego \(\emptyset\in B\), puesto que \(\emptyset\) es siempre subconjunto de cualquier conjunto. (2). Sea \(B_{1},B_{2}\) cualquier dos bases \(\in B\), \(B_{1}\not\subset B_{2}\). Por contradicción \(B_{1}\subset B_{2}\), Sea \(B_{2}\subset B\), \(B_{1}={a_{1},a_{2},a_{3},...,a_{n}}\) un posible \(B_{2}\) sería \(A=\{a_{1},a_{2},a_{3}\}\), ya que \(B_{1}\subset B_{2}\) la contradicción es verdadera haciendo falsa la \ref{M1} por lo que no cumple la equivalencia. (3). Sea \(B_{1},B_{2}\) equivalentes a \(X,Y\) respectivamente, se toma cualquier elemento \(x\in X\), y se resta de \(X\), ya que \(|X|=|Y|\) por definición, al realizar ésta resta es decir \(X-\{x\}\) daría como resultado que \(|X|<|Y|\), por lo que la primera condición se cumple. Posteriormente la \ref{M1} dice que existe un elemento de \(y\in Y\) de tal manera que \((X-\{x\})\cup\{y\}\) también es base, es decir que pertenece al conjunto \(I\), por lo que la equivalencia entre éstas dos definiciones se cumple.

    Las dos definiciones anteriores no son equivalentes, ya que para la defincion \ref{M2} permite conjuntos en \(I\) que no son maximales. Por definición un conjunto maximal inclusion-wise de una familia de conjuntos es un conjunto el cual no está contenido en otro de la familia, esto implica que todo conjunto maximal independiente (inclusion-wise) es máximo, en otras palabras todos los conjuntos maximales independientes tienen la misma cardinalidad. Por lo que la definición \ref{M2} permite todos los conjuntos incluyendo los maximales independientes y la definición \ref{M1} sólo incluye los maximales independientes. ∎