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 Raw Permalink Blame History

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