%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 17 Apr 2007 07:32:22am BRT yoshi@turan.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

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

%\usepackage{refcheck}
\usepackage{srcltx}

\usepackage{fullpage}
\usepackage{setspace}

\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]{Primeira Prova de Algoritmos em
  grafos\\BCC, 1{\tiny o.} semestre de 2007} %\date{Versão de \today}
\maketitle
\footskip=20pt

\vspace{-\medskipamount}
\noindent{\bf Instruções:}
\begin{enumerate}\small
\item Não destaque as folhas do caderno de soluções.
\item A prova pode ser feita a lápis.  Cuidado com a legibilidade.
%\item Há~$3$ questões na prova. Verifique antes de começar a prova
%se o seu caderno de questões está completo.
\item Não é permitido o uso de folhas avulsas para rascunho.
%\item Nas questões que envolvem elaboração de programas, coloque
%comentários suficientes para que o programa seja facilmente
%compreendido.
\item Não é necessário apagar rascunhos no caderno de soluções.
\item Asserções imprecisas valem pouco.  Justifique suas asserções (dentro do
  razoável!). 
\end{enumerate}

\smallskip
\onehalfspacing

\begin{enumerate}
\thispagestyle{empty}  
\item{}[3~pontos] Um \textit{$(n,m)$-digrafo} é um grafo dirigido com~$n$
  vértices e~$m$ arcos.  Desenhe, a menos de isomorfismo, \textit{todos} os
  $(2,2)$-digrafos \textbf{(são quatro)} e \textit{todos} os
  $(3,3)$-digrafos.  (Dê seus diagramas de forma organizada.)
  
\item{}[4~pontos] Considere a função recursiva 
  {\small
\begin{verbatim}
void dfsR(Graph G, Edge e)
  { link t; int w = e.w;
    pre[w] = cnt++; st[e.w] = e.v;
    for (t = G->adj[w]; t != NULL; t = t->next)
      if (pre[t->v] == -1) 
        dfsR(G, EDGE(w, t->v)); 
  }
\end{verbatim}
}\noindent
Seja~$G$ o grafo de~$10$ vértices e~$13$ arestas dado por {\small
\begin{verbatim}
0: 3            |    5: 4 3 1  
1: 6 2 3 5      |    6: 2 1 7  
2: 3 6 1        |    7: 6      
3: 2 0 5 1      |    8: 9 4    
4: 9 5 8        |    9: 4 8    
\end{verbatim}
}%
\noindent 
(\textit{i})~Desenhe~$G$.  (\textit{ii})~Simule a execução de %
\verb|dfsR(G, {0,0})| (busca em profundidade (BeP) a partir do
vértice~\verb|0|).  (\textit{iii})~Desenhe a árvore de BeP obtida.
(\textit{iv})~Caracterize as arestas de corte de~$G$ \textsl{em termos de sua
  árvore de BeP}; esta caracterização \textsl{deve ser aquela em que se baseia
  o algoritmo de tempo linear que vimos nas aulas para a identificação de tais
  areastas} (fale, \textbf{necessariamente}, do vetor~\verb|low[]| etc).

\item{}[3~pontos] Suponha que executamos uma busca em profundidade (BeP) em um
  grafo conexo~$G$ a partir de um vértice~$r$.  Suponha que orientamos todas
  as arestas da árvore de BeP `para baixo' (desenhando a árvore `com a
  raiz~$r$ para cima') e orientamos todas as arestas fora da árvore de BeP
  `para cima'.  Obtemos assim um grafo dirigido~$\vec G$.  (\textit{i})~Mostre
  que todo vértice de~$G$ é acessível a partir de~$r$ por um caminho dirigido.
  (\textit{ii})~Suponha agora que~$G$ não tem arestas de corte.  Mostre
  que~$r$ é acessível a partir de todo vértice de~$G$ por um caminho dirigido.
  \textbf{Argumente cuidadosamente}; em particular, diga exatamente onde em
  seu argumento você usa o fato de~$G$ não ter arestas de corte.  O resultado
  valeria sem essa hipótese?  Justifique.
 
\end{enumerate}

\end{document}

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

