1. Considere que a representação de um grafo (não-orientado) G=(V,E), assim como a do peso de suas arestas, é feita através de uma matriz (de adjacência).
   1. Proponha uma implementação do algoritmo de Prim para obter a árvore geradora mínima que execute em O(n²).
   2. Considere que a árvore geradora mínima é conhecida. Suponha que um novo vértice foi acrescentado, assim como arestas a todos os demais vértices (que estavam no grafo). Projete um algoritmo O(n log n) para obter a nova árvore geradora é mínima. Qual a complexidade mínima para obter esta nova árvore ? É possível projetar um algoritmo com esta complexidade ? No caso afirmativo, apresente este algoritmo.
   
   
2. Considere o problema da Mochila em sua versão fracionária (n é o número de itens candidatos a entrar na mochila, é possível colocar uma parte de um item na mochila e os itens tem pesos w₁, ..., w_n e valores v₁, ..., v_n e a mochila tem capacidade máxima W).
   1. Proponha um algoritmo que encontre sua solução ótima em O(n log n)
   2. Proponha um algoritmo que encontre sua solução ótima em O(n)
   
   
3. Dado um grafo G=(V,E) e pesos w_e para as arestas e, e Î E, seja T=(V,E) uma árvore. Proponha um algoritmo linear (O(|V|)) para encontrar o diâmetro da árvore T. (O diâmetro é dado pelo par de vértices cuja caminho em T é o mais longo entre todos os pares.)
   
   
4. Dê um algoritmo de complexidade polinomial para encontrar um conjunto independente maximal em um grafo (não orientado) G=(V,E). (Obs: Maximal é quando não é possível aumentar acrescentando mais um elemento. Máximo é o maior de todos, ou seja com mais elementos, nesse caso.) Qual a complexidade do seu algoritmo ? Apresente um algoritmo de complexidade linear.
   
   
5. Dado um conjunto de n inteiros, projete uma algoritmo O(n log n) para determinar se existem dois elemento cuja soma é um inteiro S. Quando é possível ter uma coplexidade menor ? Justifique.

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