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.
 

137 lines
5.1 KiB

\documentclass{article}
\usepackage{bstr}
\fancyhead[L]{MA4701 - Optimización Combinatorial}
\fancyhead[R]{Primavera 2013}
\fancyfoot[C]{}
\title{Auxiliar 11}
\author{}
\date{}
\begin{document}
\maketitle
\thispagestyle{fancy}
\subsection*{P1}
Notemos que la capacidad máxima de un $(s,t)$-camino está en $[0,u^*+1)$.
Además, si $m^*\in[0,u^*]$ es el valor buscado, entonces
\begin{itemize}
\item $\forall i\leq m^*,\exists$ $(s,t)$-camino de valor $\geq i$
\item $\forall i>m^*$, no existe tal camino.
\end{itemize}
\begin{lema}
$\forall k, m^*\in[a_k,b_j)$
\end{lema}
\begin{dem}
Por inducción
\begin{itemize}
\item $a_0=0, b-0=m^*+1$ $\checkmark$
\item Supongamos que $a_k,b_k$ cumple la propiedad. Entonces, $m_k =
\lfloor\frac{a_k+b_k}{2}\rfloor$ es tal que $a_k\leq m_k<b_k$.
\begin{itemize}
\item Si hay un $(s,t)$-camino con valor $m_k$ $\Rightarrow$
$m^*\in[m_k,b_k)$
\item Si no, entonces $m^*\in[a_k,m_k)$
\end{itemize}
\end{itemize}
\end{dem}
Además, en cada paso $b_k-a_k$ disminuye. Si $b_k-a_k=1$, entonces $m^*=a_k$.
Por lo tanto, el algoritmo devuelve el camino ssi $m^*>0$
Veamos ahora la complejidad:
\begin{itemize}
\item Cada búsqueda de $(s,t)$-camino se hace con BFS (o DFS), y por lo
tanto, toma $O|V|+|E|)=O(|E|)$, pues el grafo es conexo.
\item Veamos cuantas veces itera el \texttt{while}. Sea $k$ tal que
$2^k\leq m^*+1<2^{k+1}$. \textbf{Pdq} $\forall j\geq0, b_j-a_j\leq
\frac{2^{k+1}}{2^j}$.
\begin{dem}
Por inducción
\begin{itemize}
\item $b_0-a_0 = m^*+1<2^{k+1}$
\item Supongamos $b_j-a_j\leq\frac{2^{k+1}}{2^j}$. Sin importar
que intervalo elige el algoritmo,
$b_{j+1}-a_{j+1}\leq\left\lfloor\frac{b_j-a_j}{2}\right\rfloor
\leq\left\lceil\frac{b_j-a_j2}{2}\right\rceil$
Luego, $b_{j+1}-a_{j+1}\leq \lceil\frac{2^{k+1}}{2^{j+1}}\rceil
= \frac{2^{k+1}}{2^{j+1}}$
\end{itemize}
\end{dem}
\end{itemize}
Luego, el orden total es $O(|E|\log u^*)$
\begin{tabular}{|l|c|c|c|}
\hline
Algoritmo & Manera de encontrar CA & Orden CA & Orden Total\\\hline
Ford-Fulkerson & ? & ? & $\infty$\\\hline
Edmods-Karp & Más corto(BFS) & $O(|E|)$ & $O(|V||E|^2)$\\\hline
EK2 & Más gordo (Dijkstra) & $O(|E|+|V|\log|V|)$ & $O((|E| +
|V|\log|V|)(|E|\log u^*))$\\\hline
EK2 & Más gordo & $O(|E|\log n^*)$ & $O(|E|^2\log^2 n^*)$\\\hline
\end{tabular}
\subsection*{P2}
Al igual que en EK buscaremos caminos aumentantes en grafos residuales.
Notemos que si $f$ es un flujo factible entero para $(G,u,s,t)$, entonces la
red residual tiene capacidades $\{0,1\}$.
En cada etapa, usaremos BFS. Esto es correcto porque es una especialización de
FF. Veamos ahora cuál es el orden del algoritmo.
\begin{itemize}
\item Cada BFS toma $O(|V|+|E|)=O(|E|)$
\item Cada camino aumentante aumenta el flujo en 1. Luego, el algoritmo
itera a lo más $|f^*|$ veces. Por MAXFLOW-MINCUT, $|f^*|\leq |C|, \forall
C$ corte. Pero, las aristas que salen de $s$ forman un $(s,t)$-corte de
capacidad $d(s)\leq |V|$.
\end{itemize}
\subsection*{P3}
\subsubsection*{a)}
$S$ indep. $\iff$ $\forall u,v\in S, uv\not\in E \iff \forall e=xy\in E,
x\not\in S\lor y\not\in S \iff V\setminus S$ es VC.
\subsubsection*{b)}
Sea $G$ dado por $V(G) = U, E(G) =E(G) = \{ij:\text{$i,j$ son amigos}\}$.
Consideremos $\bar{G}$ el complemento de $G$. Tenemos que $\bar{G}$ es
bipartito. El problema se reduce a encontrar $S\subseteq V$ inpenediente en
$\bar{G}$ de peso máximo. Como $q\geq 0$ se tiene que
\[\text{$S$ indep. de suma máxima} \iff \text{$V\setminus S$ es cubrimiento de
peso mínimo}\]
\subsubsection*{c)}
Consideremos la red $(G',u,s,t)$ dada por $V(G') = V\dotcup\{s,t\}, E(G') =
\{(a,b): a\in A, b\in B, ab\in E\}\cup \{(s,a): a\in A\}\cup\{(b,t):b\in B\}$ y
\[u(e)=\begin{cases}q(a) & e=(s,a), a\in A\\ q(b) & (b,t), b\in B\\ \infty &
\sim\end{cases}\]
Sea $K$ finito. Entonces,
\[\text{$\bar{G}$ tiene un cub. de veértices de peso $K$} \iff
\text{$(G',u,s,t)$ tienen un $(s,t)$-corte de peso $K$}\]
\begin{dem}
\begin{itemize}
\item[$\Rightarrow$] Sea $S$ un cub. de vértices de pseo $K$ en
$\bar{G}$. Consideremos el $(s,t)$-corte generado por
$W=\{s\}\cup(A\setminus S)\cup(B\cap S)$. El valor del corte es la suma
de las capacidades de las aristas que salen de $W$, pero solo hay
aristas de la forma $(s,a), (b,t)$ con $a\in A\cap S, b\in B\cap S$.
Luego, $c(W) = \sum_{v\in S} q(a) = K$.
\item[$\Leftarrow$] Si $W$ es corte de $(G',u,s,t)$ con valor $K$
finito, entonces si $(a,b)$ es arco, $a\in W\Rightarrow b\in W$ (si no,
el corte tiene capacidad infinita). Sea $S = (A\setminus W)\cup (B\cap
W)$. Veamos que $S$ es cub. de vértices. Si $uv$ no está cubierto por
$S$, $u\not\in S\Rightarrow u\in W\Rightarrow v\in W\Rightarrow v\in
S\contra$.
El peso de $W$ son las aristas que salen. Ninguna arista con capacidad
infinita sale de $W$, pues solo salen de $\{s\}$ a $A$ o de $B$ a
$\{t\}$. Luego, $c(W) = \sum_{A\setminus W} q{v} + \sum_{B\cap W}q{v}$.
\end{itemize}
\end{dem}
De las reducciones que tenemos, basta resolver flujo máximo en $(G',u,s,t)$, lo
que se puede hacer con EK. Luego, hay un algoritmo que corre en
$O(|V(G')||E(G|^2) = O(|V|^5)$.
\end{document}