PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Período: 2000.2
11 de outubro de 2000
Horário: 3as-feiras e 5as-feiras de 14 às 16 horas
Estruturas Discretas (INF 1631)

1o Trabalho de Implementação
Estes trabalhos devem ser entregues em papel e em meio magnético.

Apresente o teorema e a respectiva prova por indução que garantem a corretude do seu algoritmo. Em seguida escreva seu código explicitando os trechos do mesmo que contém a prova (cada um dos seus passos) do caso base e do passo indutivo.

Teste seu algoritmo em no mínimo 10 instâncias diferentes do problema. Utilize o gerador de grafos usado em aula. Teste em uma instância pequena, desenhe o grafo e mostre que o seu código encontrou a solução correta.

  1. (já foi feito) Problema: Enumerar todas as permutações de { 1, 2, ..., n }.

  2. Problema: Dado um grafo orientado G=(V,E), distâncias associadas aos seus arcos duv, (u,v) Î E e um vértice s. Determine o vértice w Î V mais distante de s em G.

  3. Problema: Dado um grafo conexo e não-orientado G=(V,E), as distâncias associadas às arestas duv=dvu, (u,v) Î E; o diâmetro de G corresponde à distância caminho-mais-curto entre o par de vértices mais distante. Determine o diâmetro de G.

  4. Problema: Seja G=(V,E) um grafo orientado. O fecho transitivo de G é o conjunto de pares ordenados F(G) = { (i,j) tal que existe um caminho (orientado) de i para j em G }. Determine o fecho transitivo.
This document was translated from LATEX by HEVEA.