\documentclass[11pt]{book}
\usepackage{aprox}
%\usepackage[brazil]{babel}
%\usepackage[latin1]{inputenc} 
\usepackage{amscd}
%\usepackage{amsfonts}
\usepackage{epsf}
\usepackage{graphicx}
%\setlength{\textwidth}{39pc}
%\setlength{\textheight}{53pc}
%\setlength\oddsidemargin{0cm}  
%\setlength\evensidemargin{0cm}  
%\setlength{\topmargin}{-1cm}
%\setlength{\parskip}{0pc}
%\setlength{\paperwidth}{216mm}
%\setlength{\paperheight}{279mm}

%\newcommand{\BbbZ}{\mathbb{Z}} já definido no style 
%\newcommand{\BbbR}{\mathbb{R}}
%\newcommand{\BbbQ}{\mathbb{Q}}
\newcommand{\BbbP}{\mathbb{P}}
\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}
\newcommand{\cala}{{\cal A}}
\newcommand{\calc}{{\cal C}}
\newcommand{\cali}{{\cal I}}
\newcommand{\calr}{{\cal R}}
\newcommand{\calt}{{\cal T}}
\newcommand{\calu}{{\cal U}}
\newcommand{\opt}{{\rm OPT}}
%\newtheorem{teorema}{Teorema}[section]
%\newtheorem{proposicao}[teorema]{Proposição}
%\newtheorem{corolario}[teorema]{Corolário}
%\newtheorem{fato}[teorema]{Fato}
%\newtheorem{exemmplo}[teorema]{Exemplo}
%\newtheorem{lema}[teorema]{Lema}
%\newtheorem{observacao}[teorema]{Observação}
\def\prova{\noindent{\it Prova}. \ignorespaces}

\def\endprova{\hfill\vbox{\hrule height0.6pt\hbox{%
   \vrule height1.3ex width0.6pt\hskip0.8ex
   \vrule width0.6pt}\hrule height0.6pt
  }}

\newtheorem{exercicio}{Exercício}[section]

%-------
\bibliographystyle{plain}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%---------------------------------------------------------------------------
\begin{document}
%---------------------------------------------------------------------------
%\centerline{\Large \bf  O método Primal-Dual}
%---------------------------------------------------------------------------

\chapter{Floresta de Steiner}
\centerline{\footnotesize{Versão: \today}}
\centerline{\footnotesize{Responsáveis: Flávio, Cid, Cadão, Yoshiko}}
\section{Introdução}


Neste capítulo veremos como obter um algoritmo 2-aproximado para o
Problema da Floresta de Steiner usando o método primal-dual.


[Acrescentar: aplicações e referências.]


\section{Definição e Formulação}


\begin{quote}
  {\bf Problema da Floresta de Steiner (PFS).} Dado um grafo
  $G=(V,E)$ com custos{\footnote{Ainda que pareça mais
      restritivo, não haveria perda de generalidade se supuséssemos
      que a função custo obedece a desigualdade triangular. (Você
  saberia explicar por quê?)}} nas
  arestas $c:E\rightarrow \BbbQ^+$, e uma função de requisitos de
  conexidade $r:V\times V\rightarrow \{0,1\}$, encontrar um subgrafo
  $F$ de custo mínimo tal que quaisquer dois vértices $u$ e $v$ de $G$
  pertençam a uma mesma componente de $F$ sempre que $r(u,v)=1$.
\end{quote}


% Ainda que pareça mais restritivo, não haveria perda de generalidade se
% supuséssemos que a função custo obedece a desigualdade triangular.
% De fato, caso exista uma aresta $(u,v)$ cujo custo não satisfaz a
% desigualdade triangular, podemos substituir o seu custo pelo custo de
% um caminho mais barato de $u$ para $v$.  Claramente, uma solução ótima
% do grafo com os esses novos custos será também uma solução ótima do
% grafo original.


No que segue o conceito de corte será usado extensivamente. Lembramos
que se $S\subseteq V$, então o corte definido por $S$ é o 
conjunto das arestas com um extremo em $S$ e outro em $\overline{S}$, denotado
por $\delta(S)$. Algumas vezes, por abuso de linguagem, dizemos
simplesmente o corte $S$.

Para formular o PFS como um PLI, definimos primeiramente a seguinte
função sobre os cortes de $G$,
 $$f:2^V\rightarrow \{0,1\},$$ 
\noindent
que especifica o número mínimo de arestas que devem incidir em cada
corte em qualquer solução viável:
\[f(S) = \left\{\begin{array}{ll}
    1, & \mbox{ se }\; \exists\;   u\in S\;\mbox{ e }\; v\in \overline{S}\mbox{ tais que }r(u,v)=1, \\
    0, & \mbox{ caso contrário.}
    \end{array}\right.\]
  Associamos uma variável $x_e\in\{0,1\}$ para cada aresta $e\in E$ e
  formulamos o PFS fazendo uso da função $f$ para impor restrições
  sobre essas variáveis, com a seguinte interpretação: $x_e = 1$ se e
  somente se a aresta $e$ pertence à uma solução de PFS.  Obtemos
  assim a seguinte formulação para esse problema.


%  
%  \noindent Primal Inteiro (PI)
%  \[\begin{array}{lll}
%            \min    & \sum_{e\in E}c_e\cdot x_e \\
%  \mbox{sujeito a } & \\
%                    & \sum_{e:e\in \delta(S)}x_e\geq f(S) & S\subseteq V,\\
%                    & x_e\in \{0,1\}        &e\in E,
%  \end{array}\]
%onde $\delta(S)$ denota o conjunto de arestas do corte
%$(S,\overline{S})$. 


\[\begin{array}{llll}
                  &\min  & \sum_{e\in E}c_e\cdot x_e 
                                                       \vspace{0.5cm} \\
\mbox{(PI)}\qquad &      & \sum_{e:e\in \delta(S)}x_e\geq f(S) & \quad S\subseteq V,
                                                        \vspace{0.3cm}\\
                  &      & x_e\in \{0,1\}                      & \quad e\in E.
\end{array}\] 



Para usarmos resultados de dualidade em programação linear, vamos 
considerar o programa linear (P) que resulta da relaxação linear de
(PI) e o seu dual.  

\bigskip

\[\begin{array}{llll}
                  &  \min & \sum_{e\in E}c_e\cdot x_e & \vspace{0.5cm}\\
\mbox{(P)}\qquad  &       & \sum_{e:e\in \delta(S)}x_e\geq f(S) & \quad S\subseteq V,\vspace{0.3cm}\\
                  &       & x_e\geq 0        & \quad e\in E.\\
\end{array}\]

\bigskip


\[\begin{array}{llll}
                  &  \max & \sum_{S\subset V}f(S)\cdot y_S & \vspace{0.5cm}\\
\mbox{(D)}\qquad  &       & \sum_{S: e\in \delta(S)}y_S\leq c(e) & \quad e\in E,\vspace{0.3cm}\\
                  &       & y_S\geq 0        & \quad \emptyset\neq S\subset V.\\
\end{array}\]


\section{O Algoritmo}

O algoritmo que descrevemos a seguir produz um conjunto de arestas
$F'$ cujo vetor de incidência é viável para (PI). Observamos que em
nenhum momento o algoritmo resolve explicitamente um sistema linear.
O algoritmo mantém uma floresta inviável $F$ que vai crescendo até se
tornar viável; nesse ponto ela é `podada' (sem se tornar inviável)
resultando em uma floresta $F'$.

O processo de construção da floresta $F'$ pode ser dividido em três
fases: {\sc inicialização, aumentação} e {\sc poda}.

Na fase de {\sc inicialização} é definida uma floresta inicial $F$,
que consiste da floresta sem arestas e com $|V|=n$ vértices.

Na fase de {\sc aumentação} são feitas várias iterações para aumentar
o número de arestas da floresta $F$, visando satisfazer todos os
requisitos de conexidade definidos pela função $f$. Em cada
iteração é adicionada uma aresta que liga duas componentes distintas
de $F$, formando uma nova componente que é a união destas duas.  Essa
fase de aumentação é encerrada quando $f(C)=0$ para todas as
componentes $C$ de $F$. Como em cada iteração uma aresta é adicionada,
nessa fase são feitas no máximo $n-1$ iterações.

Após ter construído uma floresta $F$ que satisfaz os requisitos de
conexidade, passa-se para a fase de {\sc poda}. Nessa fase são
removidas as arestas de $F$ que não são necessárias para manter
satisfeitos os requisitos de conexidade. Isto é, são removidas as
arestas $e$ tais que para toda componente $C$ de $F-e$, tem-se que
$f(C)=0$.  O conjunto de arestas final, $F'\subseteq F$, é a solução
gerada pelo algoritmo.

Resta-nos ainda detalhar a fase de aumentação, que é o coração do
algoritmo. Embora esteja claro que sempre é possível acrescentar novas
arestas de modo a satisfazer os requisitos de conexidade, não está
claro como podemos fazer isto sem aumentar muito o custo.

Como estamos interessados em soluções aproximadas, a idéia central
consiste em relaxar as condições de folgas complementares (FC)
correspondentes ao par (P) e (D) dados, e construir uma solução que
satisfaz tais condições. A relaxação dessas condições FC é que nos
permitirá obter uma solução com alguma garantia de qualidade.  Tal
qualidade estará diretamente relacionada com o grau de relaxação das
condições FC. No caso do PFS, para obter um fator de aproximação 2,
consideramos as seguintes condições de folgas complementares. Note que
apenas a condição FC dual está relaxada.

\medskip

\begin{quote}
\noindent
{\bf Condição Primal (CP):} Para cada aresta $e\in E$, $x_e>0
\Rightarrow \sum_{S:e\in \delta(S)}y_S=c_e$. Isto é, para cada aresta
na solução $F'$ a sua correspondente inequação dual deve ser justa
(valer com igualdade). 
\end{quote}

\begin{quote}
\noindent
{\bf Condição Dual Relaxada (CDR):} Para cada $S\subseteq V$, $y_S\neq
0 \Rightarrow \sum_{e\in \delta(S)}x_e\leq 2\cdot f(S)$. Isto é, em
cada corte $S$ com $y_S>0$, deve incidir  no máximo 2 arestas. 
\end{quote}

Note que se soubermos construir (em tempo polinomial) um conjunto
$F'\subseteq E$ tal que o seu vetor de incidência, digamos
$(x_e)_{e\in E}$, juntamente com um vetor $(y_S)_{S\subseteq V}$
correspondente a uma solução dual satisfizer as duas condições acima,
então teremos um algoritmo 2-aproximado para o PFS. De fato, neste
caso teríamos o seguinte.

\bea
c(F') &=&  \sum_{e\in F'}x_e\cdot c_e 
      \ =\   \sum_{e\in F'}x_e\sum_{S:e\in \delta(S)}y_S \\
      &=&  \sum_{S\subset V}y_S\sum_{e\in\delta(S)}x_e
      \ \leq\   2\sum_{S\subset V}y_S\cdot f(S)\\
      &\leq&  2 \cdot \opt.
\eea

Infelizmente não sabemos como obter um par de soluções $(x,y)$
satisfazendo as duas condições acima. Veremos, no entanto, que ainda
assim podemos obter um algoritmo 2-aproximado relaxando ainda mais a
condição (CDR).  A idéia consiste em permitir que haja variáveis duais
não-nulas associadas a cortes com um número variado de arestas, desde
que, {\it na média} (considerando todos os tais cortes) esse número
seja no máximo 2. Vejamos como isso pode ser feito.

Na construção da floresta $F$, em cada iteração focalizamos nossa
atenção apenas nas componentes que chamamos de \textit {
  ativas }\index{componente ativa}: componentes $C$ de $F$ tais que
$f(C)=1$.  Essas componentes são cortes que estão violando a restrição
de conexidade. Como em qualquer solução viável deve existir alguma
aresta ligando algum vértice $u\in C$ a um vértice $v\in
\overline{C}$, procuramos acrescentar a $F$ uma aresta incidindo em
alguma componente ativa. Denotamos por $\cala$ o conjunto das
componentes ativas de $F$.

Em cada iteração, o algoritmo tenta aumentar uniformemente os valores
de $y_S$ para as componentes ativas $S\in \cala$, sem violar as
restrições do tipo $\sum y_S\leq c_e$.  Naturalmente, nesse processo
de aumentação vai ser encontrada alguma aresta $e$ que limita o
crescimento das variáveis duais das componentes ativas. Seja $e$ uma
tal aresta (nesse caso temos que $\sum y_S=c_e$), onde $e$ liga duas
componentes, digamos $C_1$ e $C_2$ (pelo menos uma delas deve ser
componente ativa). Neste caso, o algoritmo adiciona a aresta $e$ à
floresta $F$, combinando as duas componentes em uma.

\medskip

\noindent
{\bf Algoritmo AFS (Floresta de Steiner)}
\begin{enumerate}\setlength{\itemsep}{1pt}
\item {\sc [inicialização]} \\
  $F\leftarrow \emptyset$; \\
  Para cada $S\subseteq V$, $y_S\leftarrow 0;$
\item {\sc [aumentação]}\\
  Enquanto $F$ não é viável, faça 
  \begin{enumerate}\setlength{\itemsep}{1pt}
  \item Seja $\cala$ o conjunto das componentes ativas de $F$;
  \item Aumente uniformemente os valores de $y_S$, $S\in \cala$, até
  que seja encontrada uma  aresta $e\notin F$ tal que $\sum_{S:e\in\delta(S)}y_S=c_e$.
  \item $F\leftarrow F\cup \{e\}$;
  \end{enumerate}
\item {\sc [poda]}\\
  $F'\leftarrow \{e\in F\; |\ F\!-\!\{e\} \mbox{ é solução inviável}\}$;\\
  Devolva $F'$.
\end{enumerate}

\begin{figure}[ht!]
\begin{minipage}[t]{7cm}
\epsfxsize 7cm \epsfbox{circ1.eps}
\caption{\label{fig1}\footnotesize Inicialmente, $F\leftarrow\emptyset$. Objetivo:
  Ligar os triângulos, losangos e quadrados, de modo que vértices de
  mesmo tipo fiquem numa mesma componente. Suposição: grafo completo
  com custo dado pela distância euclidiana.}
\end{minipage}
\hfill
\begin{minipage}[t]{7cm}
\epsfxsize 7cm \epsfbox{circ2.eps}
\caption{\footnotesize Os círculos representam o crescimento das
  variáveis duais ($\sum_Sy_S$). A cada iteração os valores de $y_S$
  são aumentados uniformemente para as componentes ativas.}
\end{minipage}
\newline
\medskip

\begin{minipage}[t]{7cm}
\epsfxsize 7cm \epsfbox{circ3.eps}
\caption{\footnotesize Com mais duas iterações, englobamos estas duas
  novas arestas que estão à mesma distância das componentes ativas.}
\end{minipage}
\hfill
\begin{minipage}[t]{7cm}
\epsfxsize 7cm \epsfbox{circ4.eps}
\caption{\footnotesize Após esta iteração, todos os triângulos já
  estão ligados e temos uma componente ativa a menos.}
\end{minipage}
\end{figure}
\begin{figure}
\begin{minipage}[t]{7cm}
\epsfxsize 7cm \epsfbox{circ5.eps}
\end{minipage}
\hfill
\begin{minipage}[t]{7cm}
\epsfxsize 7cm \epsfbox{circ6.eps}
\end{minipage}
\newline
\bigskip

\begin{minipage}[t]{7cm}
\epsfxsize 7cm \epsfbox{circ7.eps}
\caption{\footnotesize Após as iterações acima não há mais componentes
  ativas. Obtemos a floresta $F$.}
\end{minipage}
\hfill
\begin{minipage}[t]{7cm}
\epsfxsize 7cm \epsfbox{circ8.eps}
\caption{\label{figfinal}\footnotesize Após a remoção das arestas desnecessárias
  obtemos $F'$.}
\end{minipage}
\end{figure}

\begin{figure}
\begin{center}
\begin{minipage}[t]{14cm}
\epsfxsize 14cm \epsfbox{circulos3.eps}
\caption{\label{figcores}\footnotesize A floresta $F'$ final e os círculos
  gerados. Os círculos de mesma cor têm raios iguais. Cada cor,
  englobando uma componente $S$, representa o incremento de $y_S$
  naquela componente.}
\end{minipage}
\end{center}
\end{figure}


\medskip

Nas figuras \ref{fig1}---\ref{figfinal} apresentamos uma simulação do
algoritmo aplicado à uma instância do PFS que consiste de 9 vértices
representados por triângulos, losangos, quadrados e bolinhas.  O
objetivo é interligar esses vértices, de modo que vértices de mesmo
tipo fiquem numa mesma componente, com exceção dos vértices
representados por bolinhas, para os quais não há nenhuma restrição de
conexidade. Para simplificar a apresentação, vamos considerar que o
grafo é completo e o custo das arestas é dado pela distância
euclidiana. Na figura \ref{figcores}, representamos os incrementos das
variáveis duais em cada iteração através de cores distintas.


Observe que a fase de {\sc poda} é necessária para que o algoritmo
tenha uma garantia de desempenho limitado por uma constante. Na figura
\ref{fipoda} apresentamos um grafo com um vértice central ligado a
outros $n-1$ vértices com arestas de custo 1, exceto uma que tem custo
3. O objetivo é conectar o vértice central e o vértice ligado pela
aresta de custo 3. Neste caso, o algoritmo gera uma árvore $F$ com
$n$ vértices e custo $n+1$, sendo que após a poda o algoritmo gera
uma árvore $F'$ com apenas uma aresta de custo 3.\\
\begin{figure}[ht!]
\centerline{\epsfxsize 6cm \epsfbox{Flinha.eps}}
\caption{\label{fipoda}\footnotesize Exemplo da necessidade da
  fase de {\sc poda}.}
\end{figure}



\section{Análise do Algoritmo}

Primeiro vamos mostrar que o algoritmo gera soluções viáveis para
$(P)$ e $(D)$, respectivamente. Em seguida mostraremos que o valor
destas soluções estão distantes do valor ótimo por um fator menor que
2.

\begin{lema}
  Ao terminar, o algoritmo devolve uma floresta $F'$ que corresponde a
  uma solução viável para o problema primal $(P)$,  e uma solução $y$
  viável para o problema dual $(D)$.
\end{lema}
\begin{prova}
  Claramente a floresta $F$ satisfaz todos os requisitos de
  conexidade. De fato, se isso não ocorresse, existiria uma componente
  ativa $C$ de $F$ com $f(C)=1$ que poderia ter o valor de $y_C$
  aumentado.  Neste caso, o algoritmo não teria terminado.  Além
  disso, como $F'$ é gerado a partir de $F$ removendo-se todas as
  arestas desnecessárias, temos que $F'$ é uma solução viável para
  $(P)$.
  
  Agora vamos provar por indução que $y$ é uma solução dual viável.
  Claramente, a solução inicial $y=0$ é uma solução dual viável. Seja
  $\cala$ o conjunto das componentes ativas em uma dada iteração.
  Considere a aumentação das variáveis $y_C$, $C\in\cala$.  Após 
  essa aumentação,  as únicas restrições de $(D)$ que poderiam ficar
  violadas são aquelas correspondentes às arestas que saem das
  componentes ativas. Note que nenhuma inequação de $(D)$, associada a
  uma aresta dentro de uma componente ativa pode ser violada, já que
  apenas as variáveis duais associadas às componentes ativas são
  incrementadas. Como o incremento das variáveis duais é feito até que
  a restrição associada a uma aresta seja satisfeita com igualdade, ao
  fim desta iteração todas as restrições duais continuam satisfeitas.
  Ou seja, o novo vetor  $y$ continua sendo uma solução dual viável.
\end{prova}
\bigskip

Agora vamos mostrar que o algoritmo gera uma solução viável $F'$, cujo
custo está distante de no máximo um fator $2$ do valor de uma solução
ótima. Para isto, vamos usar a solução dual $y$ construída pelo
algoritmo e mostrar que o custo de $F'$ está distante de no máximo um
fator $2$ do valor dessa solução dual.

\begin{teorema}
O algoritmo gera uma solução $F'$ viável para $(PI)$ tal que
\[c(F')\leq 2\cdot \opt.\]
\end{teorema}
\begin{prova}
Primeiramente  observe que pela escolha das arestas $e\in F$, a seguinte
equação é válida para essas arestas:
\begin{equation}\label{eqce}
c_e=\sum_{S:e\in\delta(S)}y_S.
\end{equation}
Portanto, o custo $c(F')$  da floresta $F'$  é dado pelas seguintes
equações:
\[\begin{array}{llll}\displaystyle
   c(F') &=& \displaystyle\sum_{e\in F'}c_e \\
         &=&\displaystyle \sum_{e\in F'}\sum_{S:e\in\delta(S)}y_S     & \quad\mbox{(usando (\ref{eqce}))}\\
         &=& \displaystyle\sum_{S\subset V}y_S\cdot|\delta_{F'}(S)|, & %\quad\mbox{(trocando as somas)}
\end{array}\]
onde $\delta_{F'}(S)$ é o conjunto das arestas de $F'$ que têm
exatamente uma extremidade em $S$. Assim, para obtermos um fator de
aproximação 2, basta provarmos a validade da inequação
\begin{equation}\label{eqbound1}
\sum_{S\subset V}y_S\cdot|\delta_{F'}(S)|\leq 2\sum_{S\subset V}y_S.
\end{equation}

Note que o valor da somatória do lado direito da inequação acima é
limitado pelo valor ótimo do problema dual (D), que é igual ao valor
ótimo do problema primal (P), e que por sua vez é no máximo o valor
ótimo de (PI).  Portanto, o lado direito dessa inequação é no máximo
$2\cdot \opt$.

Provaremos a validade da inequação (\ref{eqbound1}) por indução no
número de iterações.  Claramente, essa inequação é válida no início da
primeira iteração do algoritmo, uma vez que inicialmente $y=0$.
Supondo que a inequação é válida no início de uma iteração qualquer,
vamos mostrar que ela também é válida no início da próxima iteração.

Note que de uma iteração para a seguinte, os únicos valores de $y_S$
que mudam na inequação (\ref{eqbound1}) são aqueles para os quais o
conjunto $S$ é ativo. Assim, vamos mostrar que a atualização das
variáveis duais, realizada nesta iteração, produz um incremento no
lado esquerdo de (\ref{eqbound1}) que é menor do que o incremento no
seu lado direito. Seja $\cala$ o conjunto das componentes ativas desta
iteração. Se o incremento em cada variável dual associada a uma
componente ativa desta iteração for dado por um valor $\Delta$, basta
provarmos a seguinte inequação:
\[\Delta\sum_{S\in\cala}|\delta_{F'}(S)|\leq 2\cdot\Delta\cdot |\cala|.\]
Em vez de considerarmos a inequação acima, consideraremos a 
inequação equivalente
\begin{equation}\label{eqgraumedio}
\frac{\sum_{S\in\cala}|\delta_{F'}(S)|}{|\cala|} \leq 2,
\end{equation}

\noindent que nos fornece uma interpretação que pode ser melhor explorada.

Para provarmos a validade dessa inequação, vamos provar que o grau
médio dos vértices em uma dada floresta é no máximo $2$. Esta
floresta, relativa à iteração corrente, que denotaremos por $H$, é
obtida da floresta $F'$ contraindo-se as componentes desta iteração.

Mais precisamente, definimos $H$ como sendo o grafo cujo conjunto de
vértices é formado por componentes ativas e inativas desta iteração,
sendo que duas componentes $C_1$ e $C_2$ estão conectadas por uma
aresta se existem vértices $v_1\in C_1$ e $v_2\in C_2$, tais que
$\{v_1,v_2\}$ é uma aresta de $F'$. Além disso, removemos todos os
vértices isolados que resultam, correspondentes a componentes
inativas. Note que $H$ é uma floresta, uma vez que $F'$ também é.

A seguir, provaremos um resultado auxiliar que relaciona a fase de
{\sc poda} com a prova da inequação (\ref{eqgraumedio}). Denotamos por
$\cala$ o conjunto dos vértices de $H$ correspondentes às componentes
ativas, e por $\cali$ o conjunto dos demais vértices de $H$
correspondentes às componentes inativas.

\begin{quote}
\begin{fato}
  Todas as folhas de $H$ correspondem a componentes ativas desta iteração.
\end{fato}
\end{quote}
\begin{prova}
  Suponha que exista uma folha $v$ de $H$ correspondente a uma
  componente desta iteração, digamos $C_v$, que não é ativa. Seja $e$
  a aresta de $H$ incidente a $v$, e $C$ a componente de $F'$ que
  contém $C_v$.  Como $e$ é uma aresta de $H$, deve existir uma aresta
  $e'$ de $F'$ correspondente a $e$, cuja remoção separa $C$ em duas
  outras componentes, digamos $C'$ e $C''$, tal que existem vértices
  $v'\in C'$ e $v''\in C''$ com $r(v',v'')=1$ (caso contrário, a
  aresta $e'$ teria sido removida na fase de {\sc poda}). Sem perda de
  generalidade, considere $C_v\subseteq C'$. Como $v$ é folha,
  $C_v=C'$. Os requisitos de conexidade nos indicam que
  $f(C')=f(C'')=1$, e portanto $C'$ é uma componente ativa,
  contrariando nossa suposição.
\end{prova}


%No grafo $H$, o grau $d_v$ do vértice $v$ correspondente a componente
%$C_v$ deve ser $|\delta_{F'}(C_v)|$. 
Note que o lado esquerdo da inequação (\ref{eqgraumedio}) corresponde
ao cálculo do grau médio dos vértices ``ativos'' (conjunto $\cala$) de
$H$.  Denotando o grau de um vértice $v$ em $H$ por $\delta_H(v)$,
temos \bea \sum_{S\in\cala}|\delta_{F'}(S)|
&=& \sum_{v\in \cala}\delta_H(v) \\
&=& \sum_{v\in \cala\cup \cali}\delta_H(v)-\sum_{v\in\cali}\delta_H(v)\\
&\leq&2(|\cala|+|\cali|-1)-2|\cali|\\
&\leq& 2|\cala|.  \eea Com isto completamos a prova da inequação
(\ref{eqgraumedio}) e  a prova do teorema.
\end{prova}
\bigskip

Observamos aqui que a prova do fator de aproximação do algoritmo teve
como base a comparação entre o custo da solução primal $F'$ e o custo
de uma solução dual, também gerada pelo algoritmo.

O seguinte exemplo mostra que o limite de aproximação deste algoritmo
não pode ser melhorado seguindo esta análise.

\begin{proposicao}
  Existe uma instância do PFS para a qual o custo da solução $F'$
  gerada pelo algoritmo está distante de um fator tão próximo de 2
  quanto se queira do custo da solução dual gerada pelo algoritmo.
\end{proposicao}
\begin{prova}
  Considere uma instância onde o grafo é um caminho com $n$ vértices,
  sendo que um vértice está distante de duas unidades do vértice
  seguinte. Suponha que todos os vértices devem ser interligados.  A
  floresta $F'$ gerada pelo algoritmo é o próprio caminho, apresentado
  na figura seguinte.  \bigskip

  \centerline{\epsfxsize 6cm \epsfbox{reta.eps}}
 
\noindent Observe que $F'$ é uma solução ótima de custo $2(n-1)$. 
Por outro lado, temos $n$ conjuntos ativos (conforme o algoritmo)
associados a variáveis duais não-nulas. Cada uma dessas variáveis
duais tem valor 1 (raio), e portanto sua soma é igual a $n$. Assim, a
razão entre o custo da solução $F'$ e o custo da solução dual gerada
pelo algoritmo pode ser tão próxima de 2 quanto se queira.
\end{prova}


\begin{proposicao} O fator de aproximação 2 do algoritmo é justo.
\end{proposicao}
\begin{prova}
ENCONTRAR UM EXEMPLO.
\end{prova}


\section{Detalhes de Implementação}

Nesta seção apresentaremos uma implementação deste algoritmo com
complexidade de tempo $O(n^2\log n)$.\bigskip

ESCREVER.

\section{Extensões}
O algoritmo apresentado neste capítulo pode ser aplicado para uma
classe de problemas que inclui o Problema da Floresta de Steiner como
caso especial. De fato, o mesmo limite pode ser provado para problemas
que podem ser formulados através de funções próprias.

Dizemos que uma função $f:2^V\rightarrow \{0,1\}$ é {\it
  própria}\index{função própria} se ela satisfaz as seguintes
propriedades:
\begin{enumerate}
\item $f(V)=0$;
\item $f(S)=f(\overline{S})$; 
\item Se $A$ e $B$ são dois conjuntos disjuntos de $V$ e $f(A\cup
  B)=1$, então ou $f(A)=1$ ou $f(B)=1$.
\end{enumerate}

Outros exemplos de problemas que podem ser formulados através de
funções próprias são o problema da conexão ponto-a-ponto, o problema 
da $T$-junção mínima, o problema do emparelhamento perfeito de peso
mínimo, etc. 

[Definir todos no apêndice? ou aqui?]


% 
% \begin{quote}
% {\bf O Problema da Conexão Ponto-a-ponto.} ??? Point-to-point
% connection 
% \end{quote}
% 
% \begin{quote}
% {\bf O Problema da $T$-junção Mínima} ...
% \end{quote}
% 
% \begin{quote}
% {\bf O Problema do Emparelhamento Perfeito de Peso Mínimo.} ...
% \end{quote}
% 


\begin{exercicio}
  O grau médio dos vértices de uma floresta com $|\cala|$ vértices é
  na verdade menor que $2-\frac{2}{|\cala|}$. Use este fato para
  mostrar que o algoritmo tem um fator de aproximação
  $\left(2-\frac{2}{|\cala|}\right)$.
\end{exercicio}

\begin{exercicio}
  Mostre que o algoritmo que descrevemos aplicado ao problema da
  árvore geradora de peso mínimo se comporta como o algoritmo de
  Kruskal (e portanto gera uma árvore geradora de custo mínimo).
\end{exercicio}
\end{document} 
 
