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.
 

129 lines
3.3 KiB

\documentclass{article}
\usepackage{bstr}
\fancyhead[L]{MA4701 - Optimización Combinatorial}
\fancyhead[R]{Primavera 2013}
\fancyfoot[C]{}
\title{Auxiliar 6}
\author{}
\date{}
\begin{document}
\maketitle
\thispagestyle{fancy}
\subsection*{P1}
Adaptamos $\textsc{Dijkstra}(v)$:
\begin{algorithm}
$d_s\gets\infty$\;
$d_v\gets 0,\forall v\in V-s$\;
$Q\gets V$\;
\While{$Q\neq\varnothing$}{
Sacar $v\in Q$ con $d_v$ máximo\;
\For{$w\in N(v)$}
{
$d_w\gets\max\{d_w,\min\{d_u,c(u,w)\}\}$\;
}
}
\Return $d_t$
\end{algorithm}
El orden es igual al de \textsc{Dijkstra}, $O(|V|\log|V| + |E|)$. Veamos
ahora, que el algoritmo es correcto.
Sea $S$ el conjunto de nodos etiquetados de $Q$. Entonces, demostraremos que
\[\forall v\in S, d_v = \max_{\text{$P$ $(s,v)$-camino}} \min_{e\in P}c(e).\]
Procederemos por inducción en $|S|$.
\begin{itemize}
\item $|S|=1 \Rightarrow S=\{s\}\Rightarrow d_s=\infty\ \checkmark$
\item Sea $u$ e siguiente nodo agregado a $S$. El algoritmo construye un
camino de capacidad $d_u$. Veamos que es mínimo. Sea $P'$ otro
$(s,u)$-camino. Sea $e'=xy$ la primera arista de $P$ que sale de $S$.
Entonces,
\[\min_{e\in P'} c(e)\leq \min\{d_x,c(e')\}\leq d_y\leq d_u = \min_{e\in P}
c(e)\]
Luego, $d_u=\max\limits_{\text{$P'$ $(s,u)$-camino}}\min\limits_{e\in P'}
c(e)$.
\end{itemize}
\subsection*{P2}
Guardaremos los nodos como dice el \textit{hint} en un arreglo $A$ indexado por
$0,\dots,C|V|$. Implementaremos $\textsc{Dijkstra}(v)$:
\begin{algorithm}[H]
$A[0]\gets \{v\}$\;
$d_v = 0$\;
$A[C|V|]\gets V\setminus\{v\}$\;
$d_u=C|V|, \forall v\neq v$\;
$i\gets0$\;
\While{$i\neq C|V|$}{
\While{$A[i]\neq\varnothing$}{
$i\gets i+1$\;
}
Sacar $u$ de $A[i]$\;
\For{$w\in N(u)$}{
Sacar $w$ de $A[d_w]$\;
$d_w\gets \min{d_w}$\;
Meter $w$ en $A[d_w]$\;
}
}
\end{algorithm}
El algoritmo es claramente correcto. Veamos el orden:
\begin{itemize}
\item Recorro $A$ una sola vez, lo que toma $=(C|V|)$.
\item Actualizar los vecinos toma $\sum_{v\in V} O(d(v))=O(|E|)$.
\end{itemize}
\subsection*{P3}
$\textsc{Yo}(G,c)$
\begin{algorithm}
$d\gets\textsc{FloydWarshall}(G,c)$\;
$ans\gets\infty$\;
\For{$v\in V$}{
\For{$u\neq N^-(v)$}{
$ans\gets\min\{ans,d_{vu}+c(u,v)\}$\;
}
$ans\gets\min\{ans,c(v,v)\}$\;
}
\Return $ans$
\end{algorithm}
El algoritmo tiene orden $=(|V|^3)$ (por F-W). Ahora veamos la correctitud. Si
$C$ es un ciclo de largo mínimo, sus subcaminos son de largo mínimo. Si $C={v}$,
está considerado, pues revisamos los \textit{loops}. SI no, existen $u$, $v$ en
$C$ ($u$ antecesor de $v$), tales que $d_{vu} + c(u,v)$ es el largo del ciclo.
\subsection*{P4}
Sean $e^*$ tal que $c(e^*)<0$ y $P$ un $(v,u)$-camino de costo mínimo. Tenemos
dos casos
\begin{enumerate}
\item $e^*\not\in P$
Entonces, corriendo \textsc{Dijkstra} en $(V,E\setminus\{E^\})$ encontramos
un $(v,u)$-camino del costo de $P$.
\item $e^*\in P$
Si $e^*=xy$, entonces $P_{(v,x)}$ y $P_{(y,u)}$ son óptimos.
\end{enumerate}
Entonces, podemos usar el siguiente algoritmo
$\textsc{Ox}(G,c)$
\begin{algorithm}
Buscar $e^*$ con $c(e^*)<0$, $e^=(x,y)$\;
$d\gets\textsc{Dijkstra}(G-e^*,v)$\;
$d^*\gets\textsc{Dijkstra}(G-e^*,y)$\;
\For{$u\in V$}{
$d_vu=\min\{d_u,d_x+c(e^*)+d^*(u)\}$\;
}
\end{algorithm}
El orden de \textsc{Dijkstra} es mayor al del resto de las operaciones, por lo
que el algoritmo corre en ese orden.
\end{document}