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.
 

167 lines
5.2 KiB

\documentclass{article}
\usepackage{bstr}
\fancyhead[L]{MA4701 - Optimización Combinatorial}
\fancyhead[R]{Primavera 2013}
\fancyfoot[C]{}
\title{Auxiliar 5}
\author{}
\date{}
\begin{document}
\maketitle
\thispagestyle{fancy}
\subsection*{P1}
\subsubsection*{a)}
\begin{itemize}
\item[$\Leftarrow$] Supongamos que $G$ tiene orden topológico y tiene un
ciclo. Entonces, existen $e_i\in E(G)$ tales que $t(e_i) = v_i, h(e_i) =
v_{i+1}$ para $i<n$ y $t(v_n) = v_n, h(v_n) = v_1$. Como $\pi$ es orden
topológico, entonces
\[\pi(v_1) < \pi(v_2) < \dots < \pi(v_n) < \pi(v_1)\ \contra\].
\item[$\Rightarrow$] Ver \textbf{b)}.
\end{itemize}
\subsubsection*{b)}
Queremos usar una variación de DFS, pero un DFS partiendo desde $v$ sólo
considera los vértices visibles desde $v$.
Consideremos el grafo aumentado $G'$ dado por $V(G')=V(G)+v_0, E(G') = E(G)
\cup \{e: t(e) = v_0, h(e)=v, \forall v\in V(G)\}$. Primero, notemos que agregar
$v_0$ no agrega ciclos. Además, si tenemos un o.t. en G', $v_0$ recibe el número
más bajo, por lo que quitando $v_0$ seguimos teniendo un o.t.
Realizaremos un DFS a partir de $v_0$. Cuando un nodo se cierre le asignaremos
una etiqueta, en orden decreciente. En seudocódigo
$\textsc{OrdenTopológico}(G)$
\begin{algorithm}
$V(T)\gets\varnothing$\;
$E(T)\gets\varnothing$\;
$\pi\gets\varnothing$\;
Constuir el grafo aumentado $G'$\tcp*{$O(n)$}
$I\gets |V(G)|$\;
$\textsc{DFSTop}(G,v_o)$\tcp*{$O(n+m)$}
Eliminar $v_0$ de $\pi$\;
\Return $\pi$
\end{algorithm}
$\textsc{DFSTop}(G,v)$
\begin{algorithm}
$V(T)\gets V(t)\cup\{v\}$\;
\ForEach{$y\in N^+(v)$}{
\If{ $y\not\in V(T)$}{
$E(T)\gets E(T) + (v,y)$\;
$\textsc{DFSTop}(G,y)$\;
$\pi(v)\gets I$\;
$I\gets I-1$\;
}
}
\end{algorithm}
Tenemos $\pi\colon V(G) \to[n]$. Supongamos que existe $e\in E$ con
$t(e) = v, h(w) = w$ y $\pi(v) > \pi(w)$. Entonces, $v$ termina de revisar sus
vecinos antes que $w$ pero no accedió a él. Luego, en el momento en el que $v$
recibió su etiqueta $w$ no había terminado de revisar sus vecinos.
Además, tenemos que en un DFS, los vértices visitados entre la primera vez que
se visita $w$ hasta que se cierra están en el subárbol de $T$ enraizado en $w$.
Por lo tanto, $v$ está en el subárbol de $T$ enraizado en $w$. Entonces, existe
un $(w,v)$-dicamino, por lo que hay un ciclo $\contra$.
\subsection*{P2}
Sea $c(u,v)$ la cantidad de $(u,v)$-dicaminos. Tenemos que
\[c(u,v) = \sum_{w\in\delta^-(v)} c(u,w).\]
Dado $\pi$ o.t., definamos $f\colon [n]\to\N$, tal que $f(h)$ es la cantidad de
caminos desde $u$ hasta $\pi^{-1}(h)$.
$\textsc{CantidadCaminos}(G,u)$
\begin{algorithm}
$\pi$ o.t. de $g$ \tcp*{$O(n+m)$}
\For{$k = 1:\pi{u}-1$}{
$f(k)\gets 0$\;
}
$f(\pi(u))\gets 1$\;
\For{$k=\pi(u)+1:n$}{
$f(k)\gets \sum_{} f(u)$\;
}
\Return $f$
\end{algorithm}
\subsection*{P3}
Sean
\begin{align*}
V(G) = & \{s,t\} \cup \{i_1,i_2\}_{i=1}^n\\
E(G) = & \{(s,1_1),(s,1_2),(n_1,t),(n_2),t\} \cup
\{(i_a,(i+1)_b):i\in[n],a,b\in[2]\}
\end{align*}
Donde cada $i_j$ representa «el dominó $i$ se orientó escogiendo primero el
valor $j$». A cada arista le asignaremos como peso el costo de elegir el dominó
de esa forma (a las que salen de $s$ o entran a $t$ le asignamos 0). Luego, hay
un camino de costo $k$ entre $s$ y $t$ $\iff$ existe una orientación de los
dominós con costo $k$.
$\textsc{Dominó}(n, (1_1,1_2),\dots(n_1,n_2))$
\begin{algorithm}
Construye $G$ \tcp*{$O(n)$}
\Return peso mínimo de un $(s,t)$ camino.
\end{algorithm}
Usando B-F, el algoritmo corre en $O(|V(G)||E(G)|) = O(n^2)$. Como los pesos son
positivos, podemos usar Dijkstra, en cuyo caso corre en $O(|E(G)| +
|V(G)|\log|V(G)|) = O(n\log n)$. Si notamos que $G$ tiene un orden topológico,
podemos hacer que corra en $O(|E(G)| + |V(G)|) = O(n)$.
\subsection*{P4}
Construiremos el grafo obvio, $V(G_\mathdollar) = [n], E(G_\mathdollar) = [n]\times[n]$ con función de
peso
\begin{align*}
w\colon E &\to\R\\
e_{ij} &\mapsto c_i{ij}
\end{align*}
Una serie de transacciones corresponde a un paseo en $G$ que parte en CLP y
termina en CLP, $u_1u_2\dots u_n$ con valor $\alpha c_{u_iu_2}\dots
c_{u_{n-1}u_n} = \alpha\prod_{i=1}^{n-1}c_{u_iu_{i+1}}$.
\begin{lema}
$G_\mathdollar$ permita ganar arbitrariamente harta plata $\iff$ $\exists C$
ciclo tal que $\prod_{e\in C}C_e > 1$
\end{lema}
\begin{dem}
\begin{itemize}
\item[$\Leftarrow$] Sean $v\in C$ cualquiera u=CLP. Entonces, $uwC^kwu$
es un paseo en $G_\mathdollar$ y $\alpha c_{uv}\left(\prod_{e\in C}
C_e\right)^kc_{vu}\xrightarrow[k\to\infty]{}\infty$.
\item[$\Rightarrow$] Supongamos que $\forall C, \prod_{e\in C}C_e < 1$.
Dado un paseo, al sacarle un ciclo tenemos un paseo de tasa mayor.
Pero todos los paseos sin ciclos tienen tasa acotada.
\end{itemize}
\end{dem}
Notemos que $\prod_{e\in C}c_E< 1\iff -\sum_{e\in C}\log(c_e) < 0$. Luego, basta
encontrar ciclos de peso negativo.
$\textsc{Millonario}\left(n, \{c_{ij}\}_{\{i,j\}\in\binom{[n]}{2}}\right)$
\begin{algorithm}
Construir $G_\mathdollar$ \tcp*{$O(n^2)$}
$w(i,j)\gets -\log(c_{ij})$ \tcp*{$O(n^2)$}
\Return $\textsc{BF}(G_\mathdollar,w)$ \tcp*{$O(n^3)$}
\end{algorithm}
Donde BF es la versión de Bellman-Ford que determina si $G$ tiene ciclos
negativos. Por lo tanto, tenemos que el algoritmo corre en $O(n^3)$.
\end{document}