1. (3.0) 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 em no mínimo 10 instâncias diferentes do problema (estas estarão disponíveis na página). Teste em uma instância pequena, desenhe o grafo e mostre que o seu código encontrou uma solução correta.
   
   
2. (3.0) 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 2  (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 em no mínimo 10 instâncias diferentes do problema (estas estarão disponíveis na página). Teste em uma instância pequena, desenhe o grafo e mostre que o seu código encontrou uma solução correta.
   
   
3. (4.0) Considere que você possui um caminhão com capacidade para transportar P quilos. Sua missão é retirar de um armazém um grupo de objetos cujo peso total não excede a capacidade do caminhão (P) e cujo valor total é o maior possível. Você possui uma lista de todos os objetos do armazém, os objetos em N={1,2, ...,n}, onde para cada objeto i é apresentado seu peso em quilos w_i (w_i é um inteiro positivo) e seu valor v_i. Seja o teorema abaixo.
   Teorema 3  (K): Sabe-se obter um subconjunto S^K(u) de N^K={1, 2, ..., K } e seu valor total V^K(u) tal que V^K(u) é máximo, onde u é o peso total dos objetos em S^K(u), para u=0, 1, ..., P; isto é, para cada peso possível de estar no caminhão.
   
   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 em no mínimo 10 instâncias diferentes do problema (estas estarão disponíveis na página). Teste em uma instância pequena, mostrando que o seu código encontrou uma solução correta.

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