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.
 

143 lines
4.4 KiB

\documentclass{article}
\usepackage{bstr}
\fancyhead[L]{MA4701 - Optimización Combinatorial}
\fancyhead[R]{Primavera 2013}
\fancyfoot[C]{}
\title{Auxiliar 2}
\date{}
\begin{document}
\maketitle
\thispagestyle{fancy}
\section*{P1}
$\mathrm{BFS}(G,v)$:
\begin{algorithm}
\DontPrintSemicolon
$S \gets \{v\}$ \tcp*{Las asignaciones son $O(1)$}
$V(T) \gets \{v\}$ \;
$E(T) \gets \emptyset$ \;
\While{$S\neq\emptyset$}
{
$x\gets \text{el primer elemento de $S$}$ \tcp*{$O(1)$}
borrar $x$ de $S$ \tcp*{$O(1)$}
\For{$y\in N(x)$}
{
\If{$y\not\in V(T)$}
{
$S \gets S\cup\{y\}$ \tcp*{tanto verificar la condición}
$V(T) \gets V(T)\cup\{y\}$ \tcp*{como las operaciones son $O(1)$}
$E(T) \gets E(T)\cup\{xy\}$\;
}
}
}
\Return{$(V(T),E(T))$}
\end{algorithm}
Notemos un vértice entra a $S$ si y sólo si entra a $V(T)$, por lo que cada
vértice entra a $S$ una sóla vez.
El ciclo \textbf{for} se ejecuta $d(x)$ veces por cada $x$, luego se ejecuta en
total
\[ \sum_{v\in V} d(v) = 2|E|\]
\vspace*{-1.5em}\fuente{\textit{Handshaking Lemma}}
Por lo tanto, la complejidad del algoritmo es $O(|V| + |E|)$. Si es conexo, se
escribe como $O(|E|)$. Si tenemos un árbol, entonces $|V| = |E|+1$, así que el
algoritmo tiene orden $O(|V|)$.
\section*{P2}
\subsection*{a)}
\begin{itemize}
\item[$\Rightarrow$] Por contradicción, supongamos que existen $e\in E(T)$ y
$f$ en el corte formado por quitar $e$ a $T$ tal que $w(e) < w(f)$.
Sea $T' = T+f-e$. $T'$ es conexo y de $n-1$ arcos, por lo que es árbol
generador. Pero
\[w(T') = w(T) + w(f) - w(f) < w(T)\]
Pero $T$ es AGM $\contra$.
\item[$\Leftarrow$] Sea $v$ una hoja del árbol de $T$. Ejecutaremos
\texttt{PRIM} partiendo de $v$.
Sea $e=uv$ el arco que conecta la hoja en $T$. Entonces, $e$ está en el
corte $\delta(v)$. Tenemos que $w(e) \leq w(f), \forall f\in\delta(v)$.
Luego, \texttt{PRIM} elige $e$ al ejecutar. Procediendo inductivamente,
construimos $T$.
\end{itemize}
\subsection*{b)}
\begin{itemize}
\item[$\Rightarrow$] Por contradicción, supongamos que existen $f =
uv\not\in T$ y $e$ en el $(u,v)$-camino tales que $w(e) < w(f)$.
Sea $T' = T+f-e$. $T'$ es árbol, pues al agregar $f$ formamos un ciclo y al
sacar $e$ (que está en dicho ciclo) sigue siendo conexo. Pero,
\[w(T') = w(T) +w(f) - w(e) < w(T) \contra\]
\item[$\Leftarrow$] \textbf{Pdq} $\forall f$ en el corte formado por quitar
$e$, $w(e) \leq w(f)$.
Sea $e\in T$ y sean $T_1, T_2$ las componentes conexas de quitar $e$ de $T$.
Sea $f = uv\in\delta(T_1)$. Tenemos dos casos
\begin{enumerate}
\item $f = e \Rightarrow w(e) = w(f)$
\item $f\neq e \Rightarrow f\not\in T$. Como $e$ está en un
$(u,v)$-camino, entonces $w(e)\leq w(f)$.
\end{enumerate}
\end{itemize}
\subsection*{c)} Por contradicción, sean $L_1 = e_1,\dots,e_{n-1}$ y $L_2 =
f_1,\dots,f_n$ las listas de aristas de $T_1$ y $T_2$ ordenadas por peso.
Sea $i$ el mínimo índice tal que $w(e_i)\neq w(f_i)$. Spg, $w(e_i) < w(f_i)$. Si
agregamos $e_j$ ($j\leq i$) a $T_2$, hay dos casos:
\begin{enumerate}
\item $e_j \in T_2$
\item $e_j \not\in T_2$
Entonces se forma un ciclo $C$. Tenemos que $\forall f\in ,C w(f) \leq
w(e_j) \leq w(e_i) < f_i$. Es decir, $e_j$ es adyacente a algún $f_k$ en
$T_2$, con $k < i$.
\end{enumerate}
Sea $H = T_2\setminus\{f_i,\dots,f_{n-1}\}$. Tenemos que $\cc(H) = n-i+1$.
Además, $c\cc(H) = \cc(H\cup\{e_1,\dots,e_i\}) \leq cc(\{e_1,\dots,e_i\}) = n-i$
(pues corresponde a quitarle $n-i-1$ arcos a $T_1$) $\contra$.
\section*{P3}
El algoritmo retorna un árbol generador $T$, pues $(V,S)$ es conexo durante todo el
algoritmo. Además, retorna un subgrafo acíclico.
Veamos que es de peso mínimo. Para ello, usaremos \textbf{P2 b)}.
\textbf{Pdq} $\forall f=uv$ que no está en $T$ y cualquier arco $e$ en el $(u,v)$-camino de
$T$, $w(e) \leq w(f)$.
Por contradicción. Sean $f\not\in T$ y $e$ en el $(u,v)$-camino de $T$ tales que
$w(e) > w(f)$. Entonces, el algoritmo ``ìnspeciona'' $e$ antes que $f$ y no lo
descarta. Luego, quitar $e$ desconecta el grafo $(V,S)$ en ese paso, por lo que $e$
no pertenece a un ciclo. Pero, $f$ y el $(u,v)$-camino forman un ciclo en $(V,S)$ en
ese paso.
Ahora, veamos la complejidad.
\begin{itemize}
\item Ordenar:$O(|E|\log|E|) = O(|E|\log|V|^2) = O(|E|\log|V|)$.
\item Ciclo: entra $O(|E|)$ veces
\begin{itemize}
\item Revisar conexidad: $O(|V| + |E|) = O(|E|)$ (con BFS/DFS).
\end{itemize}
\end{itemize}
En total, toma $O(|E|^2 + |E|\log|V|) = O(|E|^2)$.
\end{document}