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.
 

159 lines
5.5 KiB

\documentclass{article}
\usepackage{bstr}
\fancyhead[L]{MA4701 - Optimización Combinatorial}
\fancyhead[R]{Primavera 2013}
\fancyfoot[C]{}
\title{Auxiliar 9}
\author{}
\date{}
\begin{document}
\maketitle
\thispagestyle{fancy}
\subsection*{P1}
\subsubsection*{a)}
Sea $G$ cualquiera. Si $x\in M(G)$, entonces existen $M_1,\dots,M_k$
emparejamientos en $E(G)$ tales que $x =
\lambda_1x_{M_1}+\dots+\lambda_kx_{M_k}$, $\lambda_i\in[0,1], \sum\lambda_i=1$.
Como $\forall M, M\geq 0$, entonces $x\geq 0$.
Además, si $M$ es matching y $v\in V$, entonces
\begin{align*}
|\{e\in M:e\cap v\neq\varnothing\}|\in\{0,1\} & \Rightarrow
\sum_{e\in\Gamma(v)} (x_M)_e \in \{0,1\}\\
&\Rightarrow \sum_{e\in\Gamma(v)} x_e, \forall v\in V\\
&\Rightarrow x\in M_F(G)
\end{align*}
Para $P(G)$ y $P_F{G}$ se procede de manera análoga.
\subsubsection*{b)}
Sea $G$ no bipartito. Basta ver que existe $\bar{x}\in M_F(G),
\bar{x}\not\in M(G)$.
Como $G$ no es bipartito, entonces tiene un ciclo de largo impar $C =
e_1\dots e_{2k+1}$. Definamos
\[\bar{x}_e = \begin{cases} \frac{1}{2} & e \in E(C)\\ 0 & e\not\in E(C)
\end{cases}\]
\begin{itemize}
\item \textbf{Pdq} $\bar{x}\in M_F(G)$
\begin{itemize}
\item Si $v\not\in C$, $\sum_{e\in\Gamma(v)} \bar{x}_e = 0$
\item Si $v\in C$, $\sum_{e\in\Gamma(v)} = \frac{1}{2}+\frac{1}{2} = 1$
\end{itemize}
\item \textbf{Pdq} $\bar{x}\not\in M(G)$
Supongamos que existen $M_1,\dots,M_k$ emparejamientos tales que
\[ \bar{x} = \lambda_1x_{M_1} + \dots + \lambda_kx_{M_k}\]
con $\lambda_i\in[0,1], \sum\lambda_i = 1$. Spg, $\lambda_i > 0$.
Tenemos que $\frac{1}{2} = (\bar{x})_{e_1} =
\sum_{j=1}^k\lambda_j(x_{M_j})_{e_1}$. Sea $S_i=\{j\in[k]:e_i\in M_j\}$.
Tenemos que
\[ \frac{1}{2} = (\bar{x})_{e_1}] = \sum_{j=1}^{j}\lambda_j(x_{M_j})_{e_1} =
\sum_{j\in S_1}\lambda_j \]
Como $\sum_{j=1}^{k}\lambda_j=1$, entonces $\sum_{j\not\in
S_1}\lambda_j=\frac{1}{2}$.
Además, tenemos que
\[\frac{1}{2} = (\bar{x})_{e_2} = \sum_{j\in S_2}\lambda_j \leq
\sum_{j\not\in S_1} ) \frac{1}{2}\]
Como los $M_i$ son matchings, entonces $S_1\cap S_2=\varnothing$. Luego,
$S_2\subseteq S_1^c$. Como $\sum_{j\in S_2}\lambda_j = \sum_{j\not\in S_1}$,
entonces $S_2=S_1^c$. Análogamente, obtenemos que
\[S_i = \begin{cases} S_1 & \text{$i$ impar}\\ S_1^c & \text{$i$ par}
\end{cases}\]
Luego, $S_{2k+1} = S_1 \Rightarrow S_1 = S_1^c$ $\contra$.
\end{itemize}
\subsubsection*{c)}
\begin{center}
\includegraphics[width=0.3\textwidth]{a91c.pdf}
\end{center}
Si $M$ es emparejamiento perfecto, entonces $M = \{e_1,e_3\}$. Luego, $P(G) =
\{(1,0,1,0)\}$. Sea $x\in P_F(G)$. Entonces,
\begin{align*}
1 & = \sum_{e\in\Gamma(v_1)} x_e = x_{e_1}\\
1 & = \sum_{e\in\Gamma(v_2)} x_e = x_{e_1} + x_{e_2} + x_{e_4} \Rightarrow
x_{e_2} + x_{e_4} = 0\Rightarrow x_2 = x_4 = 0\\
1 &= \sum_{e\in\Gamma(v_4)} x_e = x_{e_2} + x_{e_4} = x_{e_3}
\end{align*}
Luego, $x = (1,0,1,0)$. Por lo tanto, $P(G) = P_F(G)$.
\subsection*{P2}
Sean $n\in\N$ y $G=K_{n,n}$ el grafo bipartito completo. Tenemos que
$|E(G)| = n^2$.
Dado $x\in \R^E$, construyamos $E_x$ como $(E_x)_{ij} = x_{ij}$. $M$ es
emparejamiento perfecto en $K_{n,n}$ $\iff$ exactamente un vértice de
$\{e_{ik}\}_{k=1}^n, \{e_{lj}\}_{l=1}^n, \forall i,j$ $\iff$ $E_{x_M}$ tiene
exactamente un $1$ por fila y por columna $\iff$ $E_{X_M}$ es matriz de
permutación.
Además,
\begin{align*}
x\in P_F(G) &\iff \sum_{e\in\Gamma(v)} X_e = 1, \forall v\\
& \iff \sum_{k=1}^{n}x_{ik} = \sum_{l=1}^{n}x_{lj}, \forall i,j\\
& \iff E_x \text{ es doblemente estocástica}
\end{align*}
Por Birkhoff-von Neumann,
\begin{align*}
\{\text{$M$ doblemente estocástica}\} &= P_F(K_{n,n})\\
& = \conv(\{X_m: \text{$M$ emp. perfecto}\}\\
& = \conv(\{E: \text{$E$ es matriz de permutación}\}
\end{align*}
\subsection*{P3}Sea $x\in P_F(G)$. Si $x$ no es un emp. perfecto, entonces $E_x
= \{e\in E: x_e\not\in\{0,1\}\}\neq \varnothing$. Consideremos el grafo $G_x =
(A\dotcup B, E_x)$. Sea $v$ inceidente a $e\in E_x$. Como $\sum_{e\in\Gamma(v)}
x_e = 1$, entonces es incidente a al menos dos aristas. Luego, el grafo tiene un
ciclo $C$. Como es bipartito, $C$ es par.
Sean $E(C) = \{e_1,\dots, e_{2k}\}, C^+ = \{e_i:\text{$i$ impar}\},
C^-=\{e_i:\text{$i$ par}\}$.
Recordemos que $0 < x_{e_i} < 1$, así que elegimos
\begin{align*}
\delta^+ =& \min\left\{\min_{e\in C^+} (1-x_e), \min_{e_\in
C^-}x_e\right\}\\
\delta^- =& \min\left\{\min_{e\in C^-} (1-x_e), \min_{e_\in
C^+}x_e\right\}
\end{align*}
Construyamos los vectores $x^+, x^-$ como
\[ x_e^+ = \begin{cases} x_e & e\not\in C\\ x_e+\delta^+ & e\in C^+\\
x_e-\delta^+ & e\in C^-\end{cases}\]
\[ x_e^- = \begin{cases} x_e & e\not\in C\\ x_e-\delta^- & e\in C^+\\
x_e+\delta^- & e\in C^-\end{cases}\]
Por elección de $\delta^+, \delta^-$, tenemos que $x^+,x^-\in P_F(G)$. Tenemos
que existe una coordenada donde se alcanza el mínimo de $\delta^+$ y $\delta^-$.
Entonces,
\[|\{[e\in E: x_e^+\not\in\{0,1\}| < |\{e\in E: x_e\not\in\{0,1\}\}|\]
y se tiene lo mismo para $x^-$. Sean $w\in\R^E$ el vector de pesos y
$W=\sum_{e}w_ex_e = x^tw$.
\begin{align*}
(x^+)^tw &= \sum_{e} w_ex_e^+
= \sum{e\not\in C} w_ex_e + \sum_{e\in C^+}w_e(x_e + \delta^+) +
\sum_{e\in C^-}w_e(x_e-\delta^-)\\
&= W + \delta^+\left(\sum_{e\in C^+}w_ex_e - \sum_{e\in C^-}w_ex_e\right)
\end{align*}
De igual forma,
\[(x^-)^tw = W - \delta^-\left(\sum_{e\in C^+}w_ex_e - \sum_{e\in
C^-}w_ex_e\right)\]
Luego, basta repetir el procedimiento anterior.
\subsubsection*{b)} El algoritmo queda dado por \textbf{a)}. El análisis de
orden queda como [Ejercicio].
\end{document}