1. Seja um grafo conexo G=(V,E), não-orientado, e w_e, para e Î E os pesos associados às arestas de G. Seja o problema de encontrar a árvore geradora de peso máximo de G que contém o vértice 1 Î V e o teorema abaixo.
   
   
   Teorema 1  (K): Sabe-se encontrar a árvore de peso máximo de G=(V,E) que contém o vértice 1 e possui K vértices.
   
   1. Prove este teorema por indução simples.
   2. Apresente o algoritmo correspondente.
   3. 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, a prova garante a corretude do seu algoritmo.
   4. Teste seu algoritmo e mostre que ele encontra a solução correta.
   
   
2. Seja um grafo conexo G=(V,A), orientado, e _a, para a Î A os pesos associados aos arcos de G. Seja o problema de encontrar o caminho mais curto entre todos os pares de vértices em V. Seja o teorema abaixo.
   
   
   Teorema 2  (K): Sabe-se encontrar o caminho mais curto ente u e w " u,w Î V (ou seja, entre todos os pares de vértices em V) que utiliza no máximo K arcos.
   
   1. Prove este teorema por indução simples.
   2. Apresente o algoritmo correspondente.
   3. 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, a prova garante a corretude do seu algoritmo.
   4. Teste seu algoritmo e mostre que ele encontra a solução correta.
   
   
3. Considere um grafo não-orientado G=(V,E). Seja o problema de encontrar um CONJUNTO INDEPENDENTE maximal. Um conjunto independente C Í V, é um conjunto de vértices tal que para qualquer par de vértices v e w em C, (v,w) ÏE. Isto é, um conjunto independente é um subgrafo sem arestas.
   Teorema 3  (K): Sabe-se obter uma conjuno independente MAXIMAL de G^K=(V^K,E^K), onde V^K={1, 2, ..., K } e E^K={ (u,w) | u Î V^K Ù w Î V^K }.
   
   1. Prove este teorema por indução simples. Argumente porque essa prova garante que o novo conjunto encontrado é maximal.
   2. Apresente o algoritmo correspondente.
   3. 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, a prova garante a corretude do seu algoritmo.
   4. Teste seu algoritmo e mostre que ele encontra a solução correta.

This document was translated from L^AT_EX by H^EV^EA.