%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Monday 26 Apr 2004 09:42:48pm 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]{Primeira 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{}[3~pontos] Desenhe de forma organizada \textit{todas} as árvores com o
  conjunto de vértices~$\{1,2,3,4\}$.  Seja~$t_n$ o número total de
  árvores \textit{não-isomorfas} com~$n$ vértices (por exemplo, $t_4=2$).
  Determine~$t_5$ e~$t_6$.
  
\item{}[3~pontos] Seja~$G=(V,E)$ um grafo.  Podemos definir um grafo
  dirigido~$\vec G=(V,\vec E)$ a partir de~$G$, atribuindo para cada
  aresta~$e=\{x,y\}$ de~$G$ uma de suas duas possíveis orientações
  (formalmente, temos~$(x,y)\in\vec E$ ou~$(y,x)\in\vec E$, mas não ambos).
  Podemos chamar um tal~$\vec G$ de uma \textit{orientação} de~$G$.  Suponha
  que~$G$ tem duas árvores geradoras~$T_1$ e~$T_2$ disjuntas nas arestas, isto
  é, $T_1$~e~$T_2$ são subárvores de~$G$ com~$V(T_1)=V(T_2)=V(G)$ e
  $E(T_1)\cap E(T_2)=\emptyset$.  Mostre que~$G$ admite uma orientação~$\vec
  G$ fortemente conexa, isto é, uma orientação~$\vec G$ tal que, para
  quaisquer~$x$ e~$y\in V(\vec G)$, há um caminho dirigido de~$x$ para~$y$.
  \textbf{Se você usar o Exercício~14 da lista, você deve resolvê-lo na
    prova!  (Há uma solução sem usar este exercício.)}

\item{}[4~pontos] O que é uma \textit{ponte}?  Considere a rotina de
  identificação de pontes vista em sala (Programa 18.7): {\small
\begin{verbatim}
void bridgeR(Graph G, Edge e)
{ link t; int v, w = e.w;
  pre[w] = cnt++; low[w] = pre[w];
  for (t = G->adj[w]; t != NULL; t = t->next)
    if (pre[v = t->v] == -1) {
      bridgeR(G, EDGE(w, v)); 
      if (low[w] > low[v]) low[w] = low[v];
      if (low[v] == pre[v]) { bcnt++; printf("%d-%d\n", w, v); }
    } else if (v != e.v)
      if (low[w] > pre[v]) low[w] = pre[v];
}
\end{verbatim}
}
Seja~$G$ o grafo de~$13$ vértices e~$16$ arestas dado por {\small
\begin{verbatim}
 0:  6  5  1          |    6:  7  2  0  
 1:  2  0             |    7: 10  8  6  
 2:  6  1             |    8: 10  7     
 3:  5  4             |    9: 11  4     
 4: 11  9  5  3       |   10:  8  7     
 5:  4  3  0          |   11: 12  9  4  
                      |   12: 11        
\end{verbatim}
} Execute o Programa 18.7 acima em~$G$, a partir do vértice~$0$, destacando
sua saída.  Determine também \verb|pre[v]| e \verb|low[v]| para todo
vértice~\verb|v|.  Por que o Programa~18.7 funciona?  (Argumente de forma
sucinta e informal.) 

\end{enumerate}  
 
\end{document}

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

