Estudante

Fundação Edson Queiroz
Universidade de Fortaleza – UNIFOR
Centro de Ciências Tecnológicas – CCT
Coordenação do Curso de Ciência da Computação

Disciplina: Teoria dos Grafos
Código: N583 T10 (M35CD)
Professor: André Coelho
Data de entrega do código-fonte e apresentação: 21/11/2013
Instruções: Grupos de, no máximo, 2 pessoas. Os grupos devem ser registrados por email (para [e-mail]) até o dia 14/11. Todos os grupos devem estar presentes na data acima. O não-comparecimento de um dos integrantes implicará em nota zero.
ATIVIDADE COMPUTACIONAL
Esta atividade computacional envolve duas tarefas a serem resolvidas via programação de código Java
(versão 1.6) pelos alunos que estão cursando a disciplina de Teoria dos Grafos. Para tanto, os alunos poderão lançar mão das classes do TAD-Grafo que estão no arquivo disponível no Unifor
Online. As tarefas estão descritas na sequência.

Tarefa 1 (4,0 pontos)
Nesta tarefa, deve-se implementar o algoritmo de Fleury destinado a resolver o problema do Tour de Euler em um grafo não-dirigido. Como parte dessa implementação, será necessário projetar uma versão modificada da Busca em Profundidade (DFS) para indicar se uma dada aresta sob análise é uma ponte. O método main() do programa deve receber como entrada (via teclado ou interface gráfica) o nome (path) do arquivo contendo a especificação do grafo em matriz de adjacência, conforme a formatação dada abaixo. Porém, por conta do uso da DFS, o algoritmo de Fleury deve operar com listas de adjacência, sendo necessário, portanto, fazer a conversão entre as representações. À medida que uma nova aresta for visitada pelo algoritmo, deve-se indicar na tela se ela é uma ponte ou não. Caso ela seja escolhida, deve-se mostrar como fica o novo tour em construção. Caso o algoritmo detecte que o grafo não seja euleriano, ele deve abortar a execução e indicar tal fato na tela. Ao final da execução, caso o grafo seja euleriano, deve-se apresentar o tour de