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.
 

121 lines
4.6 KiB

\documentclass{article}
\usepackage{bstr}
\fancyhead[L]{MA4701 - Optimización Combinatorial}
\fancyhead[R]{Primavera 2013}
\fancyfoot[C]{}
\title{Auxiliar 13}
\author{}
\date{}
\begin{document}
\maketitle
\thispagestyle{fancy}
\subsection*{P1}
Notemos que $(0,\dots,0)$ siempre es factible para $P_{m,\varepsilon}$. Si en cada
desigualdad escogemos $x_i = \varepsilon x_{i-1}$ o $x_i = 1-\varepsilon x_{i-1}$,
siempre tenemos vértices del poliedro, por lo que este tiene al menos $2^n$
vértices. Además, $\mathrm{opt}(P_{n,\varepsilon}) = 1$ y se alcanza en
$(0,\dots,0,1)$. Probemos el resultado por inducción
\begin{itemize}
\item Si $n=2$, escogemos
\begin{align*}
P_1 &= (0,0)\\
P_2 &= (1,\varepsilon)\\
P_3 &= (1,1-\varepsilon)\\
P_4 &= (0,1)
\end{align*}
se aumenta la función objetivo de forma estricta en cada paso y ocupa $2^n$
vértices.
\item En dimensión $n$, tenemos $p_1,\dots, p_{2^n}$ vértices de
$F(P_{n,\varepsilon})$ tales que
\[v(p_1) < \dots < v(p_{2^n}) = 1\]
Notemos que si $_i$ es vértice de con $i\in\{1,\dots,2^n\}$, entonces
\[\tilde{p}_i = (p_i,\varepsilon(p_i)_n)\in\R^n\]
Este nuevo vector está en el cubo $P_{n+1,\varepsilon}$, las primeras
desigualdades se cumplen porque está en el cubo $P_{n+1,\varepsilon}$ y la
última se cumple por construcción. Análogomante,
\[\tilde{q}_i = (p_{2^n-i+1}, 1-\varepsilon(p_{2^n-i+1})_n)\in R^{n+1}\]
también son vértices de $(P_{n+1,\varepsilon})$.
Tenemos que
\[v(\tilde{p}_i = \varepsilon(p_i)_n = \varepsilon v(p_i)\]
Entonces,
\[0 = v(\tilde{p}_i) < \dots < v(\tilde{p}_{2^n})\]
Además,
\[v(\tilde{q}_i) = 1-\varepsilon (p_{2^n-i+1}) = 1-\varepsilon v(p_{2^n-i+1}\]
Luego,
\[v(\tilde{q}_1) < \dots < v(\tilde{q}_{2^n}) = 1\]
Falta ver que $v(\tilde{p}_{2^n}) = v(\tilde{q}_1)$. Pero,
\[v(\tilde{p}_{2^n}) = \varepsilon v(p_{2^n}) = \varepsilon < 1-\varepsilon
= 1-\varepsilon v(p_{2^n} = v(\tilde{q}_1)\]
\end{itemize}
\subsection*{P2}
Definimos una red $(G,u,s,t)$, dada por
\begin{align*}
V(G) &= \{s\} \cup \{t\} \cup \{(i^1,j^1):i,j\in[n]\} \cup
\{(i^2,j^2):i,j\in[n]\}\\
E(G) &= \{(s,(i_k^1,j_k^1)): k\in[m]\} \cup \{((i^1,j^1),(i^2,j^2)):
i,j\in[n]\}\\
&\phantom{=} \cup \{((i^2,j^2),(k^2,l^2)): i,j,k,l\in[n], |k-i| + |l-j|=
1\}\\
&\phantom{=} \cup \{((i^2,j^2),t): \{i,j\}\cap\{1,n\}\neq\varnothing, i,j\in[n]\}\\
u &\equiv 1
\end{align*}
\textbf{Pdq} $(G,u,s,t)$n obtiene un flujo de valor $m$ $\iff$
\textsc{Factible}.
\begin{itemize}
\item[$\Leftarrow$] Si la grilla es \textsc{Factible}, entonces existen
caminos $P1,\dots, P_m$ caminos vértice-disjuntos tales que van desde
$(i_k,j_k)$ hasta el borde. Sea $P_k = v_0^k\dots v_{l(k)}^k$ el camino $k$.
Entonces la red admite un flujo de valor $M$ dado por
$f((v_i^k)^2,(v_{i+1}^k)^^2)=1, f((v_i^k)^1,(v_i^k)^2)$.
\item[$\Rightarrow$] El flujo determina los caminos, pues desde un vértice
se puede saltar a su copia (lo que hace que los caminos sean disjuntos) o
a un vecino (lo que hace que el flujo efectivamente sea un camino).
\end{itemize}
Por lo tanto, usando EK podemos resolver el problema en $O(|V(G)||E(G)|^2)$,
pero $|V(G)| = 2n^2+2, |E(G)|\leq 4n^2$. Luego, podemos resolver el problema en
$O(n^6)$.
\subsection*{P3}
\begin{itemize}
\item[$\Rightarrow$] SI $G=(A\cup B,E)$ es bipartito con grados
$(a_1,\dots,a_m),(b_1,\dots,b_n)$. Entonces,
\[\sum_{i=1}^m a_i = |E| = \sum,_{j=1}^nb_j\]
Además, la cantidad de aristas que salen de los primeros $k$ vértices es
\[\sum_{i=1}^k a_i \leq
\sum_{j=1}^n\underbrace{\min\{b_j,k\}}_{\substack{\text{las
aristas}\\\text{anteriores que}\\\text{caen en $j$}}}\]
\item[$\Leftarrow$] Consideremos la red $(G,u,s,t)$ dada por
\begin{align*}
V(G) &= \{s,t\}\cup \{v_i\}_{i=1}^m\cup \{w_j\}_{j=1}^n\\
E(G) &= \{(s,v_i): i\in[n]\} \cup \{(v_i,w_j):i\in[n],j\in[m]\} \cup
\{(w_j,t):j\in[m]\}\\
u(e) &=\begin{cases} a_i & e=(s,v_i)\\ b_j & e=(w_j,t)\\ 1 & \sim
\end{cases}
\end{align*}
Si $f$ es un flufo en esta red de valor $\sum a_i=\sum b_j$, significa que
cada $v_i$ recibió flujo $a_i$ y, por lo tanto, envía flujo 1 a $a_i$
vecinos en $b$ y viceversa. Luego, $G=(A\cup B, \{u_iv_j:f(u_i,v_j)=1\}$ es
el grafo que queríamos.
Basta ver que $\textsc{MinCut}\geq \sum_{a_i}\Rightarrow$ existe $f$ de
valor $\sum a_i$. Sea $S$ un corte arbitrario. Entonces
\begin{align*}
v(S) &= \sum_{i\not\in A\cap S}a_i + |A\cap S|(n-|B\cap S) + \sum_{j\in
B\cap S} b_j\\
&\geq \sum_{i>|A\cap S|}a_i + |A\cap S|(n-|B\cap S|) + \sum_{j \geq
n-|B\cap S|} b_j\\
&\geq \sum a_i - \underbrace{\sum_{i\leq |A\cap S|}a_i +\sum{j\geq
n-|b\cap S|}b_j + |A\cap S|(n-|B\cap S|)}_{\geq 0}
\end{align*}
\end{itemize}
\end{document}