J. A. Hernandez edited sectionClique_width_.tex  almost 8 years ago

Commit id: 071546840965dded42bbc63b1f41ab6b1a5e329f

deletions | additions      

       

\section{Matroides}  \label{matroides}  \begin{definition}\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:  \begin{enumerate}  \item Ninguna base contiene de manera propia otra base.   \item 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\'en base.  \end{enumerate}  \end{definition}  Una definici\'on alternativa a matroide es la siguiente:  \begin{definition}\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 

\item Si $X,Y\in I$ y $|X|<|Y|$, entonces existe $y\in Y$ tal que $X\cup\{y\}\in I$.  \end{enumerate}  \end{definition}  Una definici\'on alternativa a matroide es la siguiente:  \begin{definition}\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:  \begin{enumerate}  \item Ninguna base contiene de manera propia otra base.   \item 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\'en base.  \end{enumerate}  \end{definition}  \begin{proposition} \ref{M1} es equivalente a \ref{M2}  \end{proposition}  \begin{proof} Para demostrar la equivalencia entre \ref{M1} y \ref{M2} se procede de la siguiente forma.