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.
 

190 lines
6.8 KiB

\documentclass{article}
\usepackage{bstr}
\fancyhead[L]{MA4701 - Optimización Combinatorial}
\fancyhead[R]{Primavera 2013}
\fancyfoot[C]{}
\title{Auxiliar 7}
\date{}
\author{}
\begin{document}
\maketitle
\thispagestyle{fancy}
\subsection*{P1}
\begin{itemize}
\item[$\Rightarrow$] Supongamos que $G$ es bipartito y $C$ un ciclo de
largo $2k+1$.Sea $V(G)=U_0\dotcup U_1$ la bipartición. Spg, $c=u_0u_1\dots
u_{2k}$ con $u_0\in U_0$. Entonces, tenemos
\begin{align*}
u_1\in& U_1\\
u_2\in& U_0\\
& \vdots\\
u_k\in U_{k\mod 2}
& \vdots\\
u_{2k}\in U_0
\end{align*}
Pero, $u_0u_{2k}\in E(G)$ $\contra$.
\item[$\Leftarrow$] Spg $G$ es conexo. Sean $r\in V(G)$ y $T$ un árbol
generador partiendo desde $r$ (por ejemplo, haciendo un BFS).
Tenemos que todo $v\in V(G)$ está conectado a $r$ por un único camino en
$T$, al que llamaremos $vTr$. Definimos
\begin{align*}
U_0 &\{v\in V(G): \text{$|vTr|$ es par}\}\\
U_1 &\{v\in V(G): \text{$|vTr|$ es impar}\}\\
\end{align*}
Claramente es partición. Falta ver que no hay aristas entre ellos. Sea
$e=xy \in E(G)$
\begin{enumerate}
\item $e\in E(T)$
Spg, $|xTr| < |yTr|$. Entonces, $yTr = yxTr$. Luego, $x,y$ están en
clases distintas.
\item $e\not\in E(T)$
$xTr + yTr + e$ es un ciclo \footnote{NdE: En realidad no es
necesariamente un ciclo, pero el argumento es análogo} de tamaño par.
es decir,
\[|C| = |xTr| + |yTr| + 1\]
Luego, $|xTr|$ y $|yTr|$ no pueden tener la misma paridad.
\end{enumerate}
\end{itemize}
\subsection*{P2}
Sea $M\in\{0,1\}^{n\times m}$. Definiremos $G_M$ como
\begin{align*}
V(G_M) =& \{a_1\dots, a_m\}\dotcup \{b_1,\dots,b_n\}\\
E(G_M) =& \{a_ib_j: M_{ij} = 1\}
\end{align*}
Tenemos que $\{(i1,j1),\dots,(i_k,j_k)\}$ son coordenadas de unos en distintas
filas y columnas $\iff$ $\{a_{i_1}b_{j_1},\dots,a_{i_k}b{j_k}\}$ es un
emparejamiento. Además, eliminar las filas $f_{i_1},\dots,f_{i_k}$ y las
columnas $c_{j_1},\dots,c_{j_k}$ tal que no queden unos, equivale a que
$\{a_{i_1},\dots,a_{i_k},b_{j_1},\dots,b_{j_k}\}$ sea cubrimiento de vértices.
Del teorema de Kőnig se concluye.
\subsection*{P3}
Spg, el primer jugador se llama Priscila y el segundo, Segundo. Veamos que si
$G$ tiene emparejamiento perfecto, Segundo tiene estrategia ganadora, y que
Priscila tiene estrategia ganadora en caso contrario.
\begin{itemize}
\item Sea $M$ emparejamiento perfecto. Probemos que en cada paso, Segundo
puede escoger $v_{i+1}$ tal que $v_{i+1}\in M$.
Si Priscila escoge $v_1\in V(G)$ cualquiera, entonces existe $e=v_1v_2\in
M$, pues $v_1$ está $M$-cubierto. Luego, Segundo puede escoger $v_2$.
Si ya se han escogido $v_1,\dots,v_{2_k},v_{2k+1}$, tenemos que
$v_1,v_2,\dots,v_{2k-1}v_{2k}\in M$. Luego, $v_{2k}v_{2k+1}\not\in M$.
Entonces, existe $v_{2k+1}v_{2k+2}\in M$, por lo que Segundo puede elegir
$v_{2k+2}$ $\Rightarrow$ WIN.
\item Sea $M$ un emparejamiento máximo. Luego, existe $v_1$ no cubierto por
$M$. La estrategia de Priscila es:
\begin{itemize}
\item en el primer paso, escoge $v_1$ no cubierto,
\item escoger $v_i$ tal que $v_{i-1}v_i\in M$.
\end{itemize}
Esto equivale a que Segundo se ve siempre obligado a
\begin{itemize}
\item perder,
\item escoger $v_{i+1}$ cubierto por $v_{i+1}v_{i+2}\in M$ tal que
$v_{i+2}$ no ha sido tomado todavía.
\end{itemize}
En el primer caso, toda elección posible se Segundo tiene que ser un
vértico cubierto, si no, podría agregar $v_1v_2$ a $M$ y aumentarlo
$\contra$.
Supongamos que $v_1,\dots, v_{2k-1}$ ha sido escogidos de acuerdo a la
estrategia. Entonces, $v_1$ no está cubierto y
$v_2v_3,\dots,v_{2k-2}v_{2k-1}\in M$. Si existe $v_{2k}$ no cubierto
adyacente a $v_{2k-1}$, entonces tenemos un camino aumentante. Por lo
tanto, Priscila siempre puede seguir su estrategia $\Rightarrow$ WIN.
\end{itemize}
\subsection*{P4}
Notemos que si $A$ es anticadena y $C$ es cadena, entonces $|A\cap C|\leq 1$.
Luego, para toda familia $\mathcal{C}$ de cadenas disjuntas y toda anticadena
$A$, $|A|\leq |\mathcal{C}|$. Entonces,
\[\max |A| \leq \min \mathcal{C}\]
Luego, nos basta encontrar $A$ anticadena y $\mathcal{C}$ partición en cadenas
que sean del mismo tamaño.
En la construcción de la indicación, por Kőnig, existen $M$ emparejamiento y
$S$ cubrimiento tales que $|M|=|S|=m$.
Sea $A=\{x\in P:x\not\in S\}$ (ninguna de las copias de $x$ debe estar en $S$).
Tenemos que $A$ es anticadena, pues si $x<y\Rightarrow xy\in E\Rightarrow x\in
S\lor y\in S\Rightarrow x\not\in A\lor y\not \in A$. Además, $|A|\geq n-m$
(pues $|S|=m$ y en el peor de los casos, todos los elementos están en uno de
los lados de $G_P$).
Sea $M$ el emparejamiento máximo en $G_P$, Consideremos $G'_P$ dado por
$V(G'_P) = P, E(G'_P) = \{uv: uv\in M\}$. Tenemos que cada component conexa
de $G'_P$, pues $\Delta(G'_P)\leq 2$ y no pueden haber ciclos (si hubiera,
tendríamos elementos en $G'_P$ tales que $u_1<u_2<\dots<u_k<u_1$). Sean
$D=\{D_1,\dots,D_l\}$ las componentes conexas de $G'_P$ y $C_i=\{u_\in P:u\in
D_i\}$. Veamos que $\mathcal{C}=\{C_i\}_{i=1}^l$ es familia de cadenas
que particionan:
\begin{itemize}
\item Son disjuntos $\checkmark$
\item Cubren todo $P$ $\checkmark$
\item
\begin{align*}
x\neq y\in C_i &\Rightarrow x,y\in D_i\\
&\Rightarrow \exists\ xp_1\dots p_ky \text{ camino en $G'_P$}\\
&\Rightarrow xp_1,p_1p_2,\dots,p_ky\in M\\
&\Rightarrow x<p_1<\dots<p_k<y\\
&\Rightarrow x<y
\end{align*}
\end{itemize}
Además, como cada $D_i$ es un camino, entonces tiene $|D_i|-1$ aristas. Luego,
\[|M|=|E(G'_P)| = \sum_{i=1}^{l}|E(D_i)| = \sum_{i=1}^{l}(|D_i|-1) = n-l\]
Por lo tanto, $|\mathcal{C}|=l=n-m$.
\subsection*{P5}
\subsubsection*{a)}
Sea $F$ un cubrimiento de tamaño mínimo. De cada vértice $v\in V(G)$ quitamos
$d_F(V)-1\geq 0$ aristas. Así, cada vértices queda con $0$ o $1$ arista en $F$.
Entonces, lo que queda es un emparejamiento en $M$. Tenemos
\[|M| \geq |F| - \left(\sum_{v\in V}(d_F(v)-1)\right) = |F| + n -\sum_{v\in
V}d_F(V) = |F|+n-2|F| = n - |F|\]
Luego, $\mu(G)\leq |M| \leq n-|F| = n-\nu(G)$. Ahora, basta encontrar un
cubrimiento de aristas tal que $|F| = n-\mu(G)$. Sea $M$ de cardinal $\mu(G)$.
Para cada vértice $v$ no $M$-cubierto, escogemos $e_v$ incidente a él,
cualquiera. El otro extremos de $e_v$ debe estar cubierto, por lo que para
$u\neq v$ no cubiertos, $e_u\neq e_v$. Tomemos $F=M\cup\{e_v: \text{$v$ no
cubierto}\}$. Por construcción, $F$ es cubrimiento de aristas. Además,
\[|F| = |M| + |\{v:\text{$v$ no cubierto}\}| = |M| + (n-2|M|) = n-\mu(G)\]
\subsubsection*{b)}
$\textsc{CubAristas}(G)$
\begin{algorithm}
$F\gets\varnothing$\;
Encontrar $M$ emp. máximo \tcp*{$O(nm)$}
$F\gets M$\;
\ForEach{$v\in V(G)$ no cubierto}{
Escoger $e_v$ incidente a él \tcp*{entre todas las iteraciones}
$F\gets F\cup\{e_v\}$\tcp*{es $O(n+m)$}
}
\Return $F$
\end{algorithm}
En total, el algoritmo corre en $O(nm)$.
\end{document}