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.
 

151 lines
5.3 KiB

\documentclass{article}
\usepackage{bstr}
\fancyhead[L]{MA4701 - Optimización Combinatorial}
\fancyhead[R]{Primavera 2013}
\fancyfoot[C]{}
\title{Auxiliar 10}
\author{}
\date{}
\begin{document}
\maketitle
\thispagestyle{fancy}
\subsection*{P1}
\subsubsection*{a)}
Sean $\{s_i\}_{i=1}^n, \{t_i\}_{i=1}^m$ los nodos de origen y destino. Basta
agregar nuevos nodos $s$ y $t$ y los arcos $(s,s_i)$, $(t_j,t)$, $i\in[n],j\in[m]$
con capacidades $+\infty$.
Sea $f$ un flujo máximo en el grafo original $G$. Definimos $f'$ en $G'$ como
\[f' = \begin{cases} f(e) & \text{si $e\in E(G)$}\\ f^{\mathrm{out}}(s_i) &
\text{si $e=(s,s_i)$}\\ f^{\mathrm{in}}(t_i) & \text{si
$e=(t_ti,t)$}\end{cases}\]
Claramente, $\forall e\in E(G'), 0\leq f'(e)\leq u(e)$. Veamos que se conserva
el flujo,
\begin{itemize}
\item $v\in V(G)$ $\checkmark$
\item $v=s_i \Rightarrow f'^{\mathrm{out}}(s_i) = f^{\mathrm{out}}(s_i) =
f'^{in}(s_i)$
\item $v=t_i$ es análogo
\end{itemize}
Por lo tanto, $f'$ es flujo. Además,
\[|f'| = \sum_{e\in\delta^+(s)}f'(e) = \sum_{i=1}^n f^{\mathrm{out}}(s_i) =
|f|\]
Luego, $\max\{\text{flujo en $G$}\}\leq \max\{\text{flujo en $G'$}\}$.
Por otro lado, sea $f'$ flujo máximo en $G'$. Definamos $f=f'|_{E(G)}$. Tenemos
que $f$ es flujo y $|f| = |f'|$. Entonces, $\max\{\text{flujo en $G$}\}\geq \max\{\text{flujo en $G'$}\}$.
\subsubsection*{b)}
Para cada $v\in V(G)$, construiremos $v_{\mathrm{in}}, v_{\mathrm{out}}$ de
modo que $\delta^{-}(v_{\mathrm{in}}) = \delta^{-}(v)$,
$\delta^{+}(v_{\mathrm{out}}) = \delta^{+}(v)$ y
$c(v_{\mathrm{in}}v_{\mathrm{out}}) = c(v)$.
\subsection*{P2}
Escribiremos $x_e = f(e)$. El problema de flujo máximo es
\begin{align*}
\max & \sum_{e\in\delta^+(s)} x_e - \sum_{e\in\delta^-(s)} x_e\\
& 0\leq x_e\leq u_e,\ \forall e\in E\\
& \sum_{e\in\delta^-(v)}x_e-\sum_{e\in\delta^+}x_e = 0,\ \forall v\in
V\setminus\{s,t\}
\end{align*}
equivalentemente,
\begin{align*}
(P) = \max & \sum_{e\in\delta^+(s)} x_e\\
& 0\leq x_e\leq u_e,\ \forall e\in E\\
& \sum_{e\in\delta^-(v)}x_e-\sum_{e\in\delta^+}x_e \leq 0,\ \forall
v\in V\setminus\{s,t\}\\
& \sum_{e\in\delta^-} x_e\leq 0 \forall e\in E
\end{align*}
Entonces, el dual es
\begin{align*}
(D) = \min & \sum_{e\in E} y_eu(e)\\
& y_e - y_u + y_v \geq 0 \forall (u,v)\in E\\
& y_s - y_t \geq 1\\
& y_e \geq 0\forall e\in E\\
& t_v \geq 0\forall v\in V
\end{align*}
Veamos que $(D)$ incluye a los $(s,t)$-cortes. Sea $(S,T)$ un $(s,t)$-corte. Definimos
\begin{align*}
y_v &= \begin{cases}1 & \text{si $v\in S$}\\ 0 & \text{si $v\in
T$}\end{cases}\\
y_e &= \begin{cases}1 & \text{si $e\in E[S,T]$}\\ 0 & \sim\end{cases}
\end{align*}
Claramente, $y\geq 0, y_s-y_t = \geq 1$. Veamos que $y_e-y_u+y_v \geq 0,
\forall e=(u,v)\in E$:
\begin{itemize}
\item $u\in S, v\in S\Rightarrow y_e-y_u+y_v = 0-1+1 = 0$
\item $u\in T, v\in T\Rightarrow y_e-y_u+y_v = 0-0+0 = 0$
\item $u\in S, v\in T\Rightarrow y_e-y_u+y_v = 1-1+0 = 0$
\item $u\in T, v\in S\Rightarrow y_e-y_u+y_v = 0-0+1 = 1\geq 0$
\end{itemize}
\subsection*{P3}
Sea $M = \sum_{v\in V}d^+_v$. Si $\sum_{v\in V}d^-_v\neq M$, entonces no se
puede. En caso contrario, construitemos $G$ como sigue: tomemos dos copias de
$V$, que llamamos $V_{\mathrm{in}}, V_{\mathrm{out}}$. Agregaremos $s,t$ con
$c(sv_{\mathrm{out}} = d^+_v, c(v_{\mathrm{in}}t) = d^-_v$. A cada
arco en $V_{\mathrm{out}}\times V_{\mathrm{in}}$ le asignaremos capacidad 1.
Veamos que existe un grafo con los grados pedidos ssi el flujo máximo del grafo
construido es $M$
\begin{itemize}
\item[$\Rightarrow$] Sea $G'$ un grafo con la lista de grados dada. Sea $f$
dada por
\[f(v_{\mathrm{out}},u_{\mathrm{in}}) = \begin{cases}1 & (v,u)\in E(G')\\ 0
& \sim\end{cases}\]
$f(s,v_\mathrm{out})=d^+_v, f(v_\mathrm{in},t)=d^-_v$. Veamos que $f$ es
flujo:
\begin{itemize}
\item Claramente respeta las capacidades
\item Conservación (los otros casos son análogos):
\[f^{\mathrm{in}}(v_\mathrm{out}) = d^+_v -
\sum_{u\in \delta^+(v)} f(v_{\mathrm{out}},u_{\mathrm{in}}) =
d^+(v) - d^+(v) = 0\]
\end{itemize}
Además, $|f|=\sum_{v\in V}d_v^+ = M$. Por oto lado,
\[\max_{\text{$f$ flujo}} |f|\leq\min_{\text{$S$ $(s,t)$-corte}}|S| \leq
M\]
Luego, $\max\limits_{\text{$f$ flujo}} |f| = M$.
\item[$\Leftarrow$] Sea $f$ flujo de tamaño máximo de $G$, con $|F| = M$.
Por \textit{spoiler}, $f(v_{\mathrm{out}}v_\mathrm{in})\in\{0,1\}$.
Definamos $G'=(V,E)$ con $e=(u,v)\in E\iff
f(u_{\mathrm{out}}v_{\mathrm{in}}) = 1$. Claramente, $G'$ no tiene arcos
repetidos. Veamos que cumpla la lista de grados. Sea $v\in V$, entonces
\[d^+_{G}(V) = \sum_{u:(v,u)\in E} 1 = \sum_{u\in
V}f(u_{\mathrm{out}}v_{\mathrm{in}}) = d^+_v\]
Análogamente, se tiene para $d^-_G(v)$.
\end{itemize}
\subsection*{P4}
Sea $p^*$ el DIM. Para $p\in P$, sea
\[g_p = \#\text{ puntos ganados en el campeonato}\]
Además, para $p,p'\in P$, con $p\neq p'$,
\[r_{p,p'} = \#\text{ partidos que faltan por jugar entre $p$ y $p'$}\]
Sea $N = g_{p^*} +
2\sum_{p\neq p^*}r_{p,p^*}$. Definimos $V' = \{p,p'\}: p,p'\in P-p^*, p\neq
p'\}$. Sea $G = (V,E)$ con $V = \{s\} \cup \{t\}\cup V'\cup(P\-p^*)$.
Asignaremos las siguiente capacidades
\begin{align*}
c(s,p) &= N-g_p-1, p\neq p^*\\
c(p,\{p,p'\}) &= \infty, p'\neq p,p^*\\
c(\{p,p'\},t) &= 2r_{p,p'}, p,p'\neq p^*, p\neq p'
\end{align*}
Tenemos que el DIM puede ganar ssi el flujo máximo de $G$ es $\sum_{p\neq
p'}2r_{p,p'}$ [Ejercicio].
\end{document}