Matroid theory

AbstractA 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}