O prazo último de entrega é 24 de junho na secretaria do bacharelado. Recomendo fortemente que os grupos entreguem antes (e enviem um mail comunicando) para terem logo a nota. Cada grupo de 3 receberá um dos dois problemas abaixo.  Entregar o programa em disquete, junto com uma listagem do código comentado e uma listagem da saída do programa para 3 casos. De preferência fazer em Pascal, C ou C++, caso o aluno prefira usar alguma linguagem "estranha", pode ser necessário marcar um horário para a demonstração do programa. Nesse caso a entrega obrigatoriamente deve ser antecipada.
 

1 - Problema do Ciclo Euleriano
 

• Entrada: arquivo especificando um grafo simples e conexo com vértices numerados de 1 até N. Esse arquivo terá o seguinte formato:

• Saída: A sequencia dos vértices em um ciclo euleriano ou uma mensagem indicando que tal ciclo não existe.

6
7
1 2
1 3
2 3
3 4
3 5
4 6
5 6

Saída: 1 - 3 - 4 - 6 - 5 - 3 - 2 - 1

3
2
1 2
2 3

Saída: O grafo não tem ciclo euleriano.
 

2 - Problema do Caminho Mais Curto
 

• Entrada: arquivo especificando um grafo ponderado simples e conexo com vértices numerados de 1 até N. Esse arquivo terá o seguinte formato:

• Saída: As distâncias do vértice 1 aos demais vértices.
• Obs: É obrigatório o uso do algoritmo de Dijkstra (mostrado em classe e no livro).

Exemplo:

6
7
1 2 2
1 3 5
2 3 1
3 4 1
3 5 8
4 6 2
5 6 3

Saída:

d(1,1) = 0
d(1,2) = 2
d(1,3) = 3
d(1,4) = 4
d(1,5) = 9
d(1,6) = 6