%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 22 Jun 2004 09:52:12am BRT yoshi@erdos.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
%----------------------------

%\usepackage{refcheck}
\usepackage{srcltx}

\let\:=\colon
\let\epsilon=\varepsilon
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\bsigma{\bar\sigma}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
%\let\sim=\thicksim

\def\inR{\mathrel{\in_{\text R}}} 

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cC{\mathcal C}
\def\cD{\mathcal D}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cI{\mathcal I}
\def\cL{\mathcal L}
\def\cP{\mathcal P}
\def\cR{\mathcal R}
\def\cS{\mathcal S}

\def\barp{{\bar p}}

\def\Bi{\mathop{{\rm Bi}}\nolimits}
\def\Var{\mathop{{\rm Var}}\nolimits}
\def\Cov{\mathop{{\rm Cov}}\nolimits}
\def\dev{\mathop{{\rm dev}}\nolimits}
\def\og{\mathop{{\rm og}}\nolimits}

\def\EE{\mathop{\hbox{\hbox{${\mathbb E}$}}}\nolimits}
\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}
\def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits}

\def\RP{\mathbf{RP}}
\def\BPP{\mathbf{BPP}}

\def\bfx{\textbf{x}}
\def\bfy{\textbf{y}}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$}
\def\sugestao#1{[\textit{Sugestão.} #1]}
\def\observacao#1{[\textit{Observação.} #1]}

\begin{document}
\title[MAC0328 Algoritmos em Grafos]{Segunda Prova de Algoritmos em
  grafos\\BCC, 1{\tiny o.} semestre de 2004} %\date{Versão de \today}
\maketitle
\footskip=20pt

%\noindent\textbf{Instruções.}  

%\bigskip

\begin{enumerate}
\thispagestyle{empty}  

\item{}[2~pontos] Descreva o que ocorre quando executamos o algoritmo de
  Kosaraju em um DAG.

\item{}[3~pontos] Seja~$G$ um grafo conexo e~$c\:E(G)\to\RR$ uma função custo
  definida nas arestas de~$G$.  Por simplicidade, suponha que~$c$ é injetora,
  isto é, não há arestas com custos iguais em~$G$.  Seja~$T$ uma árvore
  geradora de~$G$.  Para~$e\in E(T)$, sejam~$T_1^e$ e~$T_2^e$ os dois
  componentes de~$T-e$.  Prove que são equivalentes:
  \begin{enumerate}
  \item[(\textit{i})] $T$~é uma árvore geradora de custo mínimo em~$G$.
  \item[(\textit{ii})] Toda aresta~$e\in E(T)$ tem peso mínimo dentre as
    arestas do corte $E(V(T_1^e),V(T_2^e))=\big\{\{u,v\}\in E(G)\:u\in
    V(T_1^e),\;v\in V(T_2^e)\big\}$. 
  \end{enumerate}
  \sugestao{Para provar que~(\textit{ii}) implica~(\textit{i}), faça o
    seguinte: suponha que~$T$ não seja uma árvore mínima e seja~$T^*$ uma
    árvore mínima.  Seja~$e$ uma aresta em~$E(T)\setminus E(T^*)$, e
    considere~$E(V(T_1^e),V(T_2^e))$.  Seja~$f$ uma aresta em~$E(T^*)\cap
    E(V(T_1^e),V(T_2^e))$ adequada.  Considere~$T^*+e-f$.}
  
\item\label{q:pot}[3~pontos] Seja~$G$ um grafo dirigido e~$c\:E(G)\to\RR$ um
  função custo definida nos arcos de~$G$.  Por simplicidade, suponha que o
  custo de todo arco é não-negativo.  Fixe~$s\in V(G)$, e suponha que todo
  vértice de~$G$ é acessível a partir de~$s$.  Para todo~$x\in V(G)$,
  escrevemos~$d_c(s,x)$ para o custo mínimo dos caminhos dirigidos de~$s$
  a~$x$.  Um \textit{potencial~$p$ para~$(G,c)$} é uma função $p\:V(G)\to\RR$
  tal que
  \begin{equation}
    \label{eq:pot_prop}
    p(v)\leq p(u)+c(u,v)\text{ para todo~$(u,v)\in E(G)$}.
  \end{equation}
  Ademais, dizemos que um arco~$(u,v)$ é \textit{justo} se vale a
  \textit{igualdade} em~\eqref{eq:pot_prop}.  Suponha que um potencial~$p$
  satisfaz as seguintes duas propriedades:
  \begin{enumerate}
  \item[(\textit{a})]$p(s)=0$,
  \item[(\textit{b})]todo vértice~$x\in V(G)$ é acessível a partir de~$s$
    por um caminho que só contém arcos justos.
  \end{enumerate}
  Prove os seguintes fatos:
  \begin{enumerate}
  \item[(\textit{i})]Para todo~$x\in V(G)$, vale que $p(x)\leq d_c(s,x)$.
    \observacao{Para este item, a única hipótese necessária sobre o
      potencial~$p$ é que~$p(s)\leq0$.}
  \item[(\textit{ii})]Para todo~$x\in V(G)$, vale que $d_c(s,x)\leq p(x)$.
    \sugestao{Seja~$(P_k)$ a seguinte asserção: \textsl{se~$x$ é acessível a
        partir de~$s$ através de um caminho com~$k$ arcos, todos eles justos,
        então~$d_c(s,x)\leq p(x)$}.  Prove que~$(P_k)$ vale para todo~$k$ por
      indução em~$k$.}
  \end{enumerate}
  Conclua que~$d_c(s,x)=p(x)$ para todo vértice~$x$ de~$G$.
  
\item{}[4~pontos] Considere a implementação do algoritmo de Dijkstra visto em
  sala (Programa~21.1): {\small
\begin{verbatim}
#define GRAPHpfs GRAPHspt
#define P (wt[v] + t->wt)
void GRAPHpfs(Graph G, int s, int st[], double wt[])
  { int v, w;  link t;
    PQinit(); priority = wt;
    for (v = 0; v < G->V; v++)
      { st[v] = -1; wt[v] = maxWT; PQinsert(v); }
    wt[s] = 0.0; PQdec(s);
    while (!PQempty())
      if (wt[v = PQdelmin()] != maxWT)
        for (t = G->adj[v]; t != NULL; t = t->next)
          if (P < wt[w = t->v]) 
            { wt[w] = P; PQdec(w); st[w] = v; }
  }
\end{verbatim}
  } Seja~$G$ o grafo de~$5$ vértices e~$10$ arcos com custos nos arcos dado
  por {\small
\begin{verbatim}
0: 1(5) 3(10)
1: 2(2) 3(3) 4(9)
2: 0(7) 4(6)
3: 1(2) 4(1)
4: 2(4)
\end{verbatim}
  } Na notação acima, por exemplo, \verb|0: 1(5)| significa que há um arco
  de~\verb|0| para~\verb|1| de custo~\verb|5|.  
  \begin{enumerate}
  \item[(\textit{i})]Execute o Programa~21.1 no grafo~$G$ dado acima,
    com~$s=0$, ilustrando a evolução do algoritmo através de diagramas
    convenientes (uns~6 diagramas bastam).
  \item[(\textit{ii})]Determine um potencial~$p\:V(G)\to\RR$ para certificar
    que você encontrou as distâncias de~$0$ a todos os outros vértices em~$G$
    em~(\textit{i}) acima corretamente (veja a Questão~\ref{q:pot}).  Você
    deve dizer explicitamente por que sua função~$p$ é um potencial e por que
    ela de fato certifica as distâncias encontradas.
  \item[(\textit{iii})]Descreva um algoritmo de complexidade~$O(n+m)$ que
    poderia ser executado após o Programa~21.1 para verificar que de fato as
    distâncias a partir de~$s$ foram determinadas corretamente.  Por
    simplicidade, suponha que todos os vértices de~$G$ são acessíveis a partir
    de~$s$.  (Como você pode se livrar dessa hipótese?)
  \end{enumerate}

\end{enumerate}  
 
\end{document}

% Local Variables: 
% mode: latex
% eval: (Portug-mode)
% TeX-master: t
% End: 

