\documentclass[11pt]{article}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage[dvips]{graphicx,psfrag}

\pagestyle{empty}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{23cm}
\setlength{\oddsidemargin}{0mm}
\setlength{\topmargin}{0mm}

\newcommand{\N}{\mbox{{\bf N}}}
\newcommand{\Z}{\mbox{{\bf Z}}}
\newcommand{\R}{\mbox{{\bf R}}}
\newcommand{\sse}{\Longleftrightarrow}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
\newcommand{\ceil} [1]{\lceil{#1}\rceil}


\def\risonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\smile$}}}$}}
\def\tristonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\frown$}}}$}}

\begin{document}

\begin{center}
{\large
{\bf 
MAC 5711 - Análise de Algoritmos \\
}
}
{\em Departamento de Ciência da Computação} \\
Segundo semestre de 2002 \\

\vspace{3mm}
{\large
{\bf Lista 8}
}
\vspace{3mm}
\end{center}

\begin{enumerate}
  
\item {\bf (Exercício 23.2-2 do CLR)} Mostre o resultado da execução do
  algoritmo de busca em largura no grafo da figura 23.3 (abaixo), usando o
  vértice $u$ como início.

\begin{figure}[h]
 \begin{center}
  \includegraphics{fig23.3.eps}
 \end{center}
\end{figure}

  
\item {\bf (Exercício 23.2-6 do CLR)} Descreva um algoritmo eficiente
  para determinar se um grafo é bipartido. (Um grafo é {\em
    bipartido\/} se não contém nenhum circuito de comprimento ímpar.)
  
\item {\bf (Problema 23-2 do CLR)} Seja $G=(V,E)$ um grafo conexo
  não-orientado. Um {\em vértice de articulação\/} de $G$ é um vértice
  cuja remoção desconecta $G$. Uma {\em ponte\/} em $G$ é uma aresta
  cuja remoção desconecta $G$. Uma {\em componente biconexa\/} de $G$ é
  um conjunto maximal de arestas tal que quaisquer duas arestas no
  conjunto estão em um mesmo circuito. Podemos determinar vértices de
  articulação, pontes e componentes biconexas usando busca em
  profundidade. Seja $G_{\pi}$ uma árvore de busca em profundidade de
  $G$.
\begin{enumerate}
\item Prove que a raiz de $G_{\pi}$ é um vértice de articulação de $G$
  se e somente se ela tem pelo menos dois filhos em $G_{\pi}$.
\item Seja $v$ um vértice de $G_\pi$ que nao seja a raiz. Prove que
  $v$ e um vértice de articulação de $G$ se e somente se $v$ tem um
  filho $s$ tal que nao existe nenhuma aresta de retorno de $s$ ou de
  qualquer descendente de $s$ para um ancestral proprio de $v$.
\item Uma aresta $(u,w)$ é {\em de retorno\/} se $w$ é descentente de
  $u$. Seja 
{\small 
$$
l[v] \ = \ \min\{d[v],\{d[w]: (u,w) \mbox{\ é uma aresta de retorno
    para algum descendente $u$ de $v$}\}\}.
$$
}
Mostre como calcular $l[v]$ para todos os vértices $v$ em $V$ em tempo
$O(|E|)$. 
\item Mostre como computar todos os pontos de articulação de $G$ em
  tempo $O(|E|)$. 
\item Prove que uma aresta de $G$ é uma ponte se e somente se ela não
  pertence a nenhum circuito. 
\item Mostre como calcular todas as pontes de $G$ em tempo $O(|E|)$. 
\item Prove que as componentes biconexas de $G$ particionam as arestas
  de $G$ que não são pontes.
\item Dê um algoritmo que consuma tempo $O(|E|)$ e rotule cada aresta
  de $G$ com um inteiro positivo $cb[e]$ tal que $cb[e]=cb[e']$ se e
  somente se $e$ e $e'$ estão na mesma componente biconexa de $G$. 
\end{enumerate}
  
\item Um grafo orientado é {\em acíclico\/} se não tem nenhum circuito
  orientado. Uma {\em ordenação topológica\/} de um grafo orientado
  acíclico $G$ é uma ordenação $v_1,\ldots,v_n$ de seus vértices em
  que toda aresta $v_iv_j$ de $G$ é tal que $i<j$ (ou seja, todos os
  arcos vão da esquerda para a direita). Dê um algoritmo que, em tempo
  linear, imprima uma ordenação topológica de um grafo dado. Baseie-se
  em busca em profundidade. 

\item Caracterize todos os grafos (não-orientados) que contém um
  vértice $v$ tal que existe uma árvore DFS enraizada em $v$ e uma
  árvore BFS enraízada em $v$ que coincidem. 

\item {\bf (Exercício 24.1-8 do CLR)} Seja $T$ uma árvore geradora mínima de
  um grafo $G$, e seja $L$ uma lista ordenada dos pesos das arestas de $T$.
  Mostre que, para qualquer outra árvore geradora mínima $T'$ de $G$, a lista
  $L$ é também uma lista ordenada dos pesos das arestas de $T'$.
  
\item {\bf (Exercício 24.2-4 do CLR)} Suponha que o peso de
  cada aresta do grafo é um inteiro no intervalo de 1 a $|V|$. Qual o tempo de
  execução da implementação mais rápida que você consegue descrever para o
  algoritmo de Kruskal? E se os pesos estiverem entre 1 e~$W$, para uma
  constante $W$?
  
\item {\bf (Exercício 24.2-5 do CLR)} Suponha que o peso de
  cada aresta do grafo é um inteiro no intervalo de 1 a $|V|$. Qual o tempo de
  execução da implementação mais rápida que você consegue descrever para o
  algoritmo de Prim? E se os pesos estiverem entre 1 e $W$, para uma constante
  $W$?
  
\item Aplique o algoritmo de Kruskal e o algoritmo de Prim (começando
  do vértice $u$) ao grafo abaixo. Mostre o resultado da execução de
  cada um dos algoritmos após cada iteração.

\begin{figure}[h]
 \begin{center}
  \includegraphics{fig2.eps}
 \end{center}
\end{figure}

\item Desenhe um grafo com custos nas arestas que tenha mais de uma
  árvore geradora mínima. Mostre que, se todos os custos no grafo são
  distintos, então o grafo contém uma única árvore geradora mínima. 

  
\end{enumerate}

\vspace{1cm}

\begin{center}
{\bf Entregue no dia 18/11 os exercícios 2, 3, 6, 7 e 8.}
\end{center}

\end{document}