You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 

270 lines
8.6 KiB

\documentclass[10pt]{article}
\usepackage[activeacute,spanish]{babel}
\usepackage[left=1.5cm,top=1.5cm,right=1.5cm, bottom=1.5cm,letterpaper, includeheadfoot]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{amssymb, amsmath, amsthm}
\usepackage{graphicx}
\usepackage{lmodern,url}
\usepackage{fourier-orns}
\usepackage{colonequals}
\setlength{\parindent}{0em}
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancypagestyle{plain}{%
\fancyhf{}
\lhead{\footnotesize\itshape\bfseries\rightmark}
\rhead{\footnotesize\itshape\bfseries\leftmark}
}
% macros
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\C}{\mathbb C}
%Teoremas, Lemas, etc.
\theoremstyle{plain}
\newtheorem{teo}{Teorema}
\newtheorem{lem}{Lema}
\newtheorem{prop}{Proposición}
\newtheorem{cor}{Corolario}
\newtheorem*{obs}{Observación}
\theoremstyle{definition}
\newtheorem*{defi}{Definición}
\newtheorem*{ejem}{Ejemplo}
\newtheorem*{warning}{\raisebox{0.2em}{\danger} Advertencia}
% fin macros
%%%%% NOMBRE ESCRIBAS Y FECHA
\newcommand{\sca}{Felipe Contreras}
\newcommand{\scb}{Patricio Foncea}
\newcommand{\catnum}{6}
\newcommand{\fecha}{6 de Septiembre de 2013}
%%%%%%%%%%%%%%%%%%
%Macros para este documento
\newcommand{\cin}{\operatorname{cint}}
\newcommand{\I}{\mathcal{I}}
\begin{document}
%Encabezado
\fancyhead[L]{Facultad de Ciencias Físicas y Matemáticas}
\fancyhead[R]{Universidad de Chile}
\vspace*{-1.2 cm}
\begin{minipage}{0.6\textwidth}
\begin{flushleft}
\hspace*{-0.5cm}\textbf{MA4701. Optimización Combinatorial. 2013.}\\
\hspace*{-0.5cm}\textbf{Profesor:} José Soto\\
\hspace*{-0.5cm}\textbf{Escriba(s):} \sca~y~\scb\\
\hspace*{-0.5cm}\textbf{Fecha:} \fecha.
\end{flushleft}
\end{minipage}
\begin{minipage}{0.36\textwidth}
\begin{flushright}
\includegraphics[scale=0.15]{fcfm}
\end{flushright}
\end{minipage}
\bigskip
%Fin encabezado
\begin{center}
\LARGE\textbf{Cátedra \catnum}
\end{center}
Comenzaremos recordando la definición de rango en un matroide, dada la clase
anterior:
\begin{defi}
Sea $M=(E,\I)$ matroide. Definimos rango $r\colon 2^E\to\N$ como
$r(X)=\max\{|I|: I\in\I, I\subseteq X\}$.
\end{defi}
\section{Operaciones en matroides}
\subsection{Suma directa de matroides}
Sean $M_1 = (E_1,\I_1), M_2=(E_2,\I_2)$ matroides con $E_1\cap
E_2=\varnothing$.
\begin{defi}
$M_1\oplus M_2 = (E_1\cup E_2, \{I_1\cup I_2: I_i\in\I_i\})$.
\end{defi}
\begin{teo}
$M_1\oplus M_2$ es matroide.
\end{teo}
\begin{proof}
Sean $X,Y\in\I=\{I_1\cup I_2: I_i\in\I_i\}$, $Y=Y_1\cup Y_2$ y $X=X_1\cup
X_2$, con $|Y|>|X|$. Ya que $E_1$ y $E_2$ son disjuntos, necesariamente se
tiene que $|Y_1|>|X_1|$ ó $|Y_2|>|X_2|$. Sin pérdida de generalidad,
asumamos se cumple lo primero. Como $\I_1$ es matroide, $\exists z\in
Y_1\setminus X_1$ tal que $X+z\in\I_1$. De esta forma, $z\in Y\setminus X$ y
$X+z=(X_1+z)\cup X_2 \in\I$.
\end{proof}
\begin{ejem}
Sean $M_i = U(E_i,k)$, donde $U(E_i,k_i)$ es la matroide uniforme con conjunto
de referencia $E_i$ y $I\subseteq E_i$ es independiente ssi $|I|\leq k$, con
los $E_i$ disjuntos.
Definimos la \textit{matroide de partición} $M=\bigoplus M_i$ asociada a
$\left(\bigcup E_i,\{k_1\dots, k_n\}\right)$, donde $I\in \I(M) \iff
|I\cap E_i|\leq k_i, \forall i$.
\end{ejem}
\subsection{Truncación}
Sean $M=(E,\I)$ matroide, $k\in\N$.
\begin{defi}
$M^k\colonequals (E, \{I\in\I: |I|\leq k\})$.
\end{defi}
\begin{teo}
$M^k$ es matroide.
\end{teo}
\begin{proof}
Sean $X,Y\in\I(M^k)$ con $|Y|>|X|$. Dado que $X,Y\in\I$, $\exists z\in
Y\setminus X$ tal que $X+z\in\I$. Como $|X|<|Y|\leq k$, entonces
$|X+z|=|X|+1\leq k$ y se tiene que $X+z\in\I(M^k)$.
\end{proof}
\begin{ejem}[Laminar de dos niveles]
Sean $\{E_i\}_{i=1}^n$ disjuntos. La \textit{matroide laminar de dos
niveles} es $M = (\bigoplus M_i)^k$, con $M_i = U(E_i, k_i)$.
El ejemplo anterior se puede aplicar al caso de una oficina con $n$
departamentos, en donde se debe contratar a un máximo de $k$ empleados,
repartidos entre los distintos departamentos, cada uno de los cuales tiene
una restricción $k_i$ sobre la cantidad de empleados que pueden agregar a su
planta. Así, la matroide que tiene como conjunto de referencia los posibles
empleados y como conjuntos independientes a los conjuntos de empleados que
se pueden contratar simultaneamente es la matroide laminar descrita.
\begin{center}
\includegraphics[width=0.55\textwidth]{oficina.pdf}
\end{center}
\end{ejem}
\subsection{Borrado}
Sean $M = (E, \I)$ y $F\subseteq E$.
\begin{defi}
$M\setminus F \colonequals (E\setminus F, \{I\in\I: I\cap F =
\varnothing\})$.
\end{defi}
\begin{teo}
$M\setminus F$ es matroide.
\end{teo}
\begin{proof}
Sean $X,Y\in\I_F =\{I\in\I: I\cap F = \varnothing\}$ con $|Y|>|X|$. Como
$X,Y\in\I$, entonces existe $z\in Y\setminus X$ tal que $X+z\in\I$. Además,
ya que $Y\cap F=\varnothing$, $z$ no está en $F$ y, por lo tanto, $(X+z)\cap
F=\varnothing$, lo que concluye la demostración.
\end{proof}
\begin{ejem}
Sean $G = (V.E)$ grafo, $M = (E.\I)$ matroide gráfica asociada a $G$ y
$F\subseteq E$. Entonces $M\setminus F$ es la matroide de $G\setminus F =
(V,E\setminus F)$.
\end{ejem}
\begin{warning}
Existen grafos distintos con la misma matroide gráfica.
\begin{center}
\includegraphics[width=0.55\textwidth]{matgraf.pdf}
\end{center}
\end{warning}
\subsection{Dual}
\begin{defi}
Dada $M=(E,\I)$ matroide. Un conjunto $F$ se dice generador de $M$ si $F$
continene una base de $M$.
\end{defi}
\begin{defi}
Definimos el dual de $M = (E,\I)$ como $M^* = (E, \{F\subseteq E: \text{$E\setminus
F$ es generador de $M$}\})$.
\end{defi}
\begin{ejem}
Si $M$ es gráfica de un grafo conexo $G = V,E$, tenemos que
\begin{align*}
F\in\I(M^*) &\iff \text{$E\setminus F$ es generador de $M$}\\
& \iff \text{$G\setminus F$ contiene un árbol generador de $G$}\\
& \iff \text{$(V,E\setminus F)$ es conexo.}
\end{align*}
En general, si $G$ no es conexo, $F\in\I(M^*)\iff\text{$(V,E\setminus F)$
tiene las mismas componentes conexas que $G$}$.
\end{ejem}
\begin{teo}
Si $M=(E,\I)$ es matroide, entonces $M^*=(E,\I^*)$ es matroide.
\end{teo}
\begin{proof}
Sean $X,Y\in\I^*$ con $|Y|>|X|$. Como $Y\in\I^*$, entonces existe
$B\subseteq E\setminus Y$ base de $M$. Luego, $B\setminus X$ es
independiente en $M$.
Como $E\setminus X$ contiene una base, entonces podemos ``aumentar''
$B\setminus X$ a una base de $M$ en $E\setminus X$, que llamaremos $B'$.
Tenemos que $B\setminus X\subseteq B' \subseteq E\setminus X$. Además, como
$B$ y $B'$ tienen el mismo tamaño
\[|B'| = |B| = |B\setminus X| + |B\cap X| = |B\setminus X| +
\underbrace{\text{elementos agregados}}_{B'\setminus(B\setminus X)}\]
\begin{center}
\includegraphics[width=0.4\textwidth]{base.pdf}
\end{center}
Es decir, agregamos $|B\cap X|$ elementos. Como en $Y\setminus X$ hay más
elementos que en $X\setminus Y\supseteq B\cap X$, entonces existe $z\in
Y\setminus X$ tal que $z\not\in B'$. Luego, $X+z$ y $B'$ son disjuntos, por
lo que $X+z\in\I^*$.
\end{proof}
\subsubsection*{Propiedades}
\begin{enumerate}
\item Las bases de $M^*$ son exactamente los complementos de las bases de
$M$.
\item $(M^*)^* = M$.
\end{enumerate}
\begin{proof}
Notemos que las bases de $M$ definen a $M$ (ver Def. 4 del complemento 2).
\begin{enumerate}
\item Sea $B$ base de $M$. Luego, $E\setminus B\in\I^*$ y $\forall z\in
E\setminus(E\setminus B)=B$, $E\setminus B +z\not\in\I^*$, ya que
$E\setminus(E\setminus B +z)=B-z$ no contiene ninguna base. Por la
maximalidad de $E\setminus B$, se concluye que es base.
Por otro lado, si $B^*$ es base de $M^*$, entonces $E\setminus B^*$ es
generador de $M$, pero $B^*$ es maximal en $\I^*$, por lo tanto,
$\forall z\in E\setminus B^*$, $B^*+z\not\in\I^*$. Es decir,
$(E\setminus B^*)-z = E\setminus(B^*+z)$ no contiene ninguna base, pero
$E\setminus B^*$ sí, con lo que se concluye que $E\setminus B^*$ es base
de $M$.
\item Basta notar que por la propiedad anterior, las bases de $M$ y
$M^{**}$ son las mismas.
\end{enumerate}
\end{proof}
\subsection{Contracción}
\begin{defi}
Dados $M = (E,\I)$ matroide y $F\subseteq E$, definimos
\[M/F \colonequals (M^*\setminus F)^* = (E\setminus F,\{X\subseteq
E\setminus F: X\cup B_F\in\I\})\]
Donde $B_F$ es cualquier base de $F$.
\end{defi}
\begin{obs}
$(M^*\setminus F)^*$ está bien definida. La segunda definición es válida
para cualquier $B_F$ que elija.
\end{obs}
\subsubsection*{Propiedades}
\begin{enumerate}
\item $(M\setminus F_1)/F_2 = (M/F_2)\setminus F_1$.
\item $r_{M^*}(U) = |U| + r_M(E\setminus U) - r_M(E)$.
\item $r_{M^k}(U) = \min(r_M(U),k)$.
\item $r_{M\setminus F}(U) = r_M(U)$.
\item $r_{M/F}(U) = r_M(U\cup F) - r_M(F)$.
\end{enumerate}
\end{document}