\documentclass[12pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}

\setlength{\parskip}{0.3cm}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{21.5cm}
\input{epsf}
\begin{document}
\begin{center}
{\large MAC 323 -- Estruturas de Dados -- Prim. Sem. 1998}

Sexta (e última!!) Lista de Exerc\'\i cios (30 pontos) -- Entrega: 13 de junho
\end{center}

\begin{enumerate}

\item (Valor 5+5 pontos) \\
Considere o seguinte grafo. 
$$\epsffile{l6f1.eps} $$
a. Simule o algoritmo do caminho mais curto para achar a dist\^ancia entre
o v\'ertice $3$ e todos os outros v\'ertices do grafo. \\
b. Simule o algoritmo da \'arvore geradora mínima. 

\item (Valor 10 pontos) \\
Dado um par de cidades $u$ e $v$, desejamos descobrir se existe no grafo
pelo menos dois caminhos independentes (disjuntos nas arestas) ligando 
$u$ e $v$. Voc\^e \'e capaz de modificar o algoritmo do caminho mais curto 
para resolver este problema? 

\item (Valor 10 pontos) \\
Se os pesos das arestas puderem ser também números negativos, o algoritmo de
achar um caminho mínimo ainda funciona? Se não funciona, apresente um exemplo
em que ele falha. 

\item (Valor 5+10 pontos) \\
a. Escreva uma implementação da classe {\it winged edge} descrita em sala de
aula, explicando as estruturas utilizadas. \\
b. Escreva um método {\tt void ListaArestasdaFace(Face F)} que lista todas as
arestas de uma face de um polígono representado pela estrutura {\it winged
edge}. 

\end{enumerate}

\begin{center}
{\bf Boas férias!!}
\end{center}
\end{document}