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

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc} % isso é quase redundante
\usepackage{textcomp}
\usepackage[T1]{fontenc}
%----------------------------

%\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\diam{\mathop{\rm diam}\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]{Terceira 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] 
%   \begin{enumerate}
%   \item[(\textit{i})]Suponha que queremos implementar uma fila de prioridade,
%     mas temos a informação adicional de que as prioridades dos elementos na
%     fila serão inteiros positivos não maiores que um dado inteiro~$n$.
%     Descreva em detalhe uma implementação de uma tal fila que é eficiente no
%     seguinte sentido: (\textit{a})~inicializar uma fila com $n$~elementos
%     dados custa tempo~$O(n)$, (\textit{b})~a extração do elemento de maior
%     prioridade custa tempo~$O(1)$, (\textit{c})~a inserção de um elemento novo
%     à fila custa tempo~$O(1)$, e (\textit{c})~a alteração da prioridade de um
%     elemento custa tempo~$O(1)$.
    
%   \item[(\textit{ii})]Suponha que temos um grafo dirigdo~$G=(V,E)$ e uma
%     função custo $c\:E\to\RR$ nos arcos de~$G$, com a propriedade adicional
%     que~$c(e)$ é um inteiro e que~$1\leq c(e)\leq n$ para todo arco~$e$
%     de~$G$.  Seja~$s$ um vértice fixo de~$G$.  Descreva um algoritmo com
%     complexidade de tempo~$O(n+m)$ que descobre a distância de~$s$ a todo
%     vértice~$t$ de~$G$.  Você deve justificar por que seu algoritmos tem a
%     complexidade desejada.
%   \end{enumerate}


\item{}[2~pontos] Lembre que um \textit{vertebrado} é uma tripla~$(T,x,y)$,
  onde~$T$ é uma árvore e~$x$ e~$y$ são vértices de~$T$ ($x$~é a
  \textit{cabeça} do vertebrado e~$y$ é a \textit{cauda} do vertebrado).
  Lembre que existe uma bijeção entre vertebrados com~$n$ vértices e
  funções~$f\:[n]\to[n]$, onde, como de usual, $[n]=\{1,\dots,n\}$.  O
  \textit{diâmetro}~$\diam(G)$ de um grafo conexo~$G$ é o máximo das
  distâncias entre dois vértices em~$G$, isto é,
  \begin{equation}
    \label{eq:diam_def}
    \diam(G)=\max\{\dist_G(x,y)\:x,\,y\in V(G)\}.
  \end{equation}
  Descreva cuidadosamente como podemos estimar computacionalmente o diâmetro
  médio de uma árvore~$T$ com~$n$ vértices, para~$n$ razoavelmente grande
  (digamos, $n=20$).  Isto é, como podemos estimar
  \begin{equation}
    \label{eq:diametro_medio}
    n^{-(n-2)}\sum\diam(T),
  \end{equation}
  onde a soma é sobre toda árvore~$T$ com conjunto de vértices~$[n]$?  (Nesta
  questão, não é necessário escrever código; basta você esboçar um
  procedimento, e dizer por que ele funciona.)
  
\item{}[2~pontos] Considere o seguinte trecho de código, que implementa a
  essência do algoritmo de Warshall:
\begin{verbatim}
for (i = 0; i < V; i++)
  for (s = 0; s < V; s++)
    for (t = 0; t < V; t++)
      if (A[s][i] && A[i][t])
        A[s][t] = 1;
\end{verbatim}
  \begin{enumerate}
  \item[(\textit{i})]Execute o trecho de código acima na matriz
    \begin{equation}
      \label{eq:cycle}
      A=
      \begin{bmatrix}
        1& 1& 0& 0& 0& 0 \\
        0& 1& 1& 0& 0& 0 \\
        0& 0& 1& 1& 0& 0 \\
        0& 0& 0& 1& 1& 0 \\
        0& 0& 0& 0& 1& 1 \\
        1& 0& 0& 0& 0& 1 
      \end{bmatrix}
    \end{equation}
    (Você deve dizer o estado da matriz~$A$ após cada iteração do \verb|for|
    mais externo.)
  \item[(\textit{ii})]Generalize~(\textit{i}): considere o grafo
    dirigido~$G_n$ com~$n$ vértices generalizando o grafo em~(\textit{i}).
    (Assim, $G_6$~é o grafo do item~(\textit{i}).)  Descreva a matriz~$A$
    correspondente ao grafo~$G_n$ após a execução do corpo do \verb|for|
    externo para um~$i$ genérico ($0\leq i<n=V$).
  \end{enumerate}
  
\item{}[2~pontos] (Nesta questão, os grafos são não-orientandos.)  Suponha que
  temos~$G=(V,E)$ um grafo com função custo nas arestas $c\:E\to\RR$.  Seja
  ainda~$s$ um vértice fixo de~$G$.  Por simplicidade, suponha~$c(e)$ positivo
  para todo~$e\in E$.  Podemos definir \textit{uma árvore de caminhos mínimos
    com raiz~$s$} como sendo uma árvore geradora~$T$ de~$G$ que tem a
  propriedade de que, para todo~$t\in V$, a distância~$\dist_G(s,t)$ de~$s$
  a~$t$ em~$G$ é igual à distância~$\dist_T(s,t)$ em~$T$.  É verdade que uma
  tal árvore de caminhos mínimos com raiz~$s$ é necessariamente uma árvore
  geradora mínima?  Prove ou dê um contra-exemplo.  Se você for dar um
  contra-exemplo, ele deve ser tal que~$0<c(e)\leq1$ para todo~$e$, mas o
  custo das árvores em questão (árvore de caminhos mínimos e árvore geradora
  mínima) diferem de pelo menos~$10^{10}$.
  
\item{}[4~pontos] Seja~$G=(V,E)$ um grafo conexo e~$c\:E\to\RR$ uma função
  custo nas arestas de~$G$.
  \begin{enumerate}
  \item[(\textit{i})]Seja~$A\subset E$ um conjunto de arestas de~$G$ que está
    contida em alguma árvore geradora mínima de~$G$.  Seja~$U\subset V$ tal
    que~$A\cap E(U,V\setminus U)=\emptyset$, onde~$E(U,V\setminus
    U)=\big\{\{u,w\}\in E\:u\in U,\,w\in V\setminus U\big\}$ é o corte
    definido por~$U$.  Suponha que~$e\in E(U,V\setminus U)$ tem custo mínimo
    dentre as arestas em~$E(U,V\setminus U)$.  Mostre que~$A\cup\{e\}$ está
    contida em alguma árvore geradora mínima de~$G$.
  \item[(\textit{ii})]Descreva o algoritmo de Kruskal precisamente e prove sua
    correção.
  \item[(\textit{iii})]Descreva o algoritmo de Prim precisamente e prove sua
    correção.
  \end{enumerate}
\end{enumerate}  
 
\end{document}

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