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.
 

153 lines
4.4 KiB

\documentclass{article}
\usepackage{bstr}
\fancyhead[L]{MA4701 - Optimización Combinatorial}
\fancyhead[R]{Primavera 2013}
\title{Auxiliar 1}
\date{}
\begin{document}
\maketitle
\thispagestyle{fancy}
\section*{P1}
\begin{itemize}
\item[\textbf{Forma Algorítmica}] Consideremos el siguiente algoritmo:
\begin{algorithm}[H]
\DontPrintSemicolon
$v \gets v_0$ \tcp*{cualquiera}
$v_1 \gets \text{algún vecino de $v$}$ \tcp*{existe pues
$d(v)\geq2$}
\While{el universo no se acabe}
{
$v_{i+1} \gets \text{algún vecino de $v_i$ distinto de
$v_{i-1}$}$\;
}
\end{algorithm}
Como el grafo es finito, en algún momento $v_i$ se repite. Supongamos
que $v_k$ es el primer vértice que se repite, y que la segunda vez que
aparece es en $l > k$. Entonces, $v_kv_{k+1}\dots v_l$ es un ciclo.
\item[\textbf{Forma Grafística}]
Sea $P = v_0v_1\dots v_k$ un camino en $G$ de largo máximo. Como
$d(v_0)\geq 2$, entonces $v_0$ tiene un vecino en $P$ que no es $v_1$
(debe estar en $P$ pues es camino máximo). Si tal vecino es $v_j,
j\in\{2,\dots,k\}$, entonces $v_1\dots v_j$ es un ciclo.
\end{itemize}
\section*{P2}
\begin{itemize}
\item[$1\Rightarrow4$] Tenemos que $T$ es acíclico. Sea $e = {u,v} \not\in
E(G)$. Como $T$ es conexo, entonces existe $P$ un $(u,v)$-camino,
digamos $uw_1\dots w_kv$. Entonces, al agregar $e$ a $P$ obtenemos un
ciclo.
\item[$4\Rightarrow3$] \textbf{Pdq} $T$ es conexo:
Sean $u,v$ cualesquiera:
\begin{enumerate}
\item Si $\{u,v\}\in E(T)$ $\checkmark$
\item Si no, entonces $T + \{u,v\}$ tiene un ciclo $C = uvw_1\dots
w_k$, pero $\{w_1,w_2\},\dots \{w_{k-1},w_k\}\in E(T)$, por lo
que $uw_1\dots w_kv$ es un $(u,v)$-camino en $T$.
\end{enumerate}
\textbf{Pdq} $\forall e\in E(T)$, $T-e$ no es conexo.
Sea $e=\{u,v\}\in E(T)$ cualquiera. Veremos que en $T-e$ no hay un
$(u,v)$-camino. Si existiera, $P=uw_1\dots w_kv$ en $T-e$, entonces
$uw_1\dots w_k$ es un ciclo en $T$ $\contra$.
\item[$3\Rightarrow2$]
\begin{lema} Si en $G$ existen un $(u_1,u_2)$-camino y un
$(u_2,u_3)$-camino entonces existe un $(u_1,u_3)$-camino.
\end{lema}
\begin{dem}
Sean $P_1 = u_1v_1\dots v_ku_2$ un $(u_1,u_2)$-camino y $P_2 =
u_2w_1\dots w_lu_3$ un $(u_2,u_3)$-camino. Sea $i\in\{0,\dots,
k+1\}$ tal que $v_i\in P_2\Rightarrow v_i=w_j$ e $i$ es mínimo
(existe, porque al menos se encuentra en $v_{k+1} = v_2$). Entonces,
$u_1v_1\dots v_iw_j\dots w_lu_3$ es un $(u_1,u_3)$-camino.
\end{dem}
\textbf{Pdq} $\forall\{u,v\}\in\binom{V}{2}\exists!$ $(u,v)$-camino.
Supongamos que existen $P_1 = uw_1\dots w_kv, P_2 = ux_q\dots x_rv$
$(u,v)$-caminos distintos. Como $P_1\neq P_2$, existe $e\in
E(P_1)\setminus E(P_2)$, digamos $e = w_iw_{i+1}$.
\textbf{Pdq} $T-e$ es conexo (con esto se conluye)
Sean $x,y$ vértices en $V(T)$, entonces existe un $(x,y)$-camino en $T$:
\begin{itemize}
\item Si este camino no usa $e$, entonces está en $T-e$ $\checkmark$
\item Si usa $e$, podemos escribir $P = xz_1z_2\dots
w_iw_{i+1}\dots z_ny$ en $T$. Luego,
\begin{align*}
xz_1\dots w_i &\in T-e\\
w_iw_i{i-1}\dots u &\in T-e\\
ux_1\dots x_rv &\in T-e\\
w_{i+1}\dots z_ny &\in T-e
\end{align*}
Del lema. existe un $(x,y)$-camino en $T-e$.
\end{itemize}
\item[$2\Rightarrow1$] Como existe un camino entre todo par de vértices,
entonces $T$ es conexo.
Si hubiera un ciclo $uw_1\dots w_nv$, entonces $uv$ y $uw_1\dots w_nv$ son
dos $(u,v)$-caminos distintos $\contra$.
\end{itemize}
\section*{P4}
Propuesto D:
\section*{P5}
\begin{itemize}
\item \textbf{BFS}
$\mathrm{BFS}(G,v)$
\begin{algorithm}[H]
\DontPrintSemicolon
%\KwIn{$G,v$}
%\KwOut{$T = E(T),V(T)$}
$S \gets \{v\}$\;
$V(T) \gets \{v\}$\;
$E(T) \gets \emptyset$\;
\While{$S\neq\emptyset$}
{
$x \gets \text{el primer elemento de $S$, borrar de $S$}$\;
\ForEach{ $y\in N(x)$}
{
\If{$y\not\in V(T)$}
{
$S \gets S\cup\{y\}$\;
$V(T) \gets V(T)\cup\{y\}$\;
$E(T) \gets E(T)\cup\{xy\}$\;
}
}
}
\end{algorithm}
\item \textbf{DFS}
\begin{algorithm}
\DontPrintSemicolon
$V(T) \gets \emptyset$\;
$E(T) \gets \emptyset$\;
$\mathrm{DFS}(G,v):$\;
$V(T)\gets V(T)\cup\{v\}$\;
\ForEach{$y\in N(x)$}
{
\If{$y\not\in V(T)$}
{
$E(T) \gets E(T)\cup\{xy\}$\;
$\mathrm{DFS}(G,y)$
}
}
\end{algorithm}
\end{itemize}
\end{document}