1. Dado um grafo não-orientado G=(V,E) e pesos w_e, não necessariamente positivos, e Î E, analise a complexidade dos problemas abaixo seguindo o roteiro que se segue:
   • Verifique se o problema está na classe NP (prove no caso afirmativo);
   • Caso exista, apresente um algoritmo de complexidade polinomial (O(n^k), para algum k fixo);
   • Caso não seja conhecido um algoritmo de complexidade polinomial para este problema, como se poderia classificar a dificuldade de se encontrar uma solução ótima ?
   • Ainda no caso de não ser conhecido um algoritmo de complexidade polinomial, apresente algoritmos de complexidade polinomial para obter uma ("boa") solução e para obter uma ("boa") estimativa da melhor solução possível, e com isso permitindo indicar a que percentual máximo do ótimo que está a solução gerada.
   
   
   1. Árvore Geradora de Peso Mínimo (AGM): Determinar uma árvore em G que conecta todos os vértices em V, cuja soma dos pesos das arestas é mínimo.
      
      
   2. Árvore de Peso Mínimo (AM): Determinar a árvore em G cuja soma dos pesos das arestas é mínimo. [ O problema de Steiner em Grafos, encontrar a árvore de peso mínimo que conecta um subconjunto T dos vértices em V, pode ser "facilmente" transformado neste problema. ]
      
      
   3. Árvore Geradora de Peso Mínimo com Restrição de Grau (AGM-Grau): Determinar uma árvore em G que conecta todos os vértices em V, cuja soma dos pesos das arestas é mínimo, onde nenhum vértice tenha grau maior que q (esse grau é na árvore e não no grafo, em termos práticos, imagine que você possui "hubs" de no máximo q portas e em cada vértice ficará um "hub"). [ O problema do Caixeiro Viajante pode ser "facilmente" transformado neste problema. ]
      
      
   4. Árvore Geradora de Peso Mínimo com Restrição de Capacidade (Cap-AGM): Dado que o vértice r Î V é a raiz e que os demais vértices possuem uma demanda d_v, para v Î V, e uma capacidade D; determinar uma árvore em G que conecta todos os vértices em V, cuja soma dos pesos das arestas é mínimo, onde a soma das demandas dos vértices em cada sub-árvore ligada à raiz r não ultrapassa D. [ O problema de Particonamento, (PART) abaixo, pode ser "facilmente" transformado neste problema. ]
   
   
2. Defina (sem mencionar Máquina de Turing):
   1. Transfomação (ou redução) Polinomial de um Problema para outro.
   2. Classe NP de Problemas.
   3. Classe NP-completo de Problemas.
   4. Classe NP-difícil.
   5. Relacione as 3 classes acima.
   
   
3. Sabe-se que o problema (VC), abaixo, pertence a NP-completo. Use este conhecimento para provar que (SCP) também pertence a NP-completo.
   
   Vertex Cover (VC) - Dado um grafo não-orientado G=(V,E) e um inteiro K, 1<K<|E|.
   
   Pergunta-se se existe um conjunto de vértices SÍ V tal que |S| £ K e " (u,w) Î E pelo menos um entre u e w pertence a S.
   
   Recobrimento de Conjuntos (SCP) - Dada uma coleção de subconjuntos C= { c₁, ..., c_m } de um conjunto U e um inteiro K, 1<K<M.
   
   Pergunta-se se existe um subconjunto R Í U de elementos de U tal que |R| £ K, que contém pelo menos um dos elementos de cada conjunto c_i, para i=1,2,...,m.
   
   (Dica: Siga os passos para provar que um problema é NP-completo. Na transformação você deve mostrar que a respota sim para o problema (SCP) acontece se e somente se acontece a resposta sim na instância obtida pela tranformação do problema (VC)).
   
   
4. Sabe-se que o problema (MC), abaixo, pertence a NP-completo. Use este conhecimento para provar que (MS) também pertence a NP-completo.
   
   Clique-Máximo (MC) - Dado um grafo não-orientado G=(V,A) e uma constante K. Pergunta-se se este grafo G possui um clique (isto é um sub-grafo completo) de cardinalidade maior ou igual à K.
   
   Estável-Máximo (MS) - Dado um grafo não-orientado G=(V,A) e uma constante K. Pergunta-se se este grafo G possui um conjunto de vértices independentes (isto é, um conjunto de vértices onde não existe aresta entre nenhum par do conjunto) de cardinalidade maior ou igual à K.
   
   
5. Sabe-se que o problema (PART), abaixo, pertence a NP-completo. Use este conhecimento para provar que (KP) também pertence a NP-completo.
   
   (PART) Instância: Dado um conjunto de elementos X={x₁, x₂, ..., x_n} e seu respectivos tamanhos T={t₁, t₂, ..., t_n }.
   
   Questão: Existe um subconjunto S de X tal que å_{xi Î S} T_i = å_{xi Î X-S} T_i ?
   
   (KP) Instância: Dado um conjunto de elementos X={x₁, x₂, ..., x_n}, seus respectivos tamanhos T={t₁, t₂, ..., t_n } e seus respectivos valores V={v₁, v₂, ..., v_n }, e as constantes T₀ e V₀.
   
   Questão: Existe um subconjunto de S de X tal que a soma dos tamanhos dos elementos em S seja menor ou igual a T₀ e tal que a soma dos seus respectivos valores seja superior ou igual a V₀ ?

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