Prova 3c - Algoritmos em Grafos - 2021-1

Instituto de Matem´atica e Estat´ıstica - UERJ Prova 3c de Teoria dos Grafos Professor: Luerbio Faria Data: 29/11/2021 1. V ou F+Justificativa e/ou contra-exemplo se for o caso. (a) Dado R 2 NP ´e verdade que: i. [0.2 + 0.3] ( ) Existe algoritmo polinomial que resolve um certificado de R para resposta Sim. ii. [0.2 + 0.3] ( ) Se R ´e completo e R 2 P, ent˜ao P=NP. (b) Se P6=NP, ent˜ao i. [0.2 + 0.3] ( ) Todo problema num´erico possui algoritmo pseudopolinomial. ii. [0.2 + 0.3] ( ) Nenhum problema NP-completo forte possui algoritmo pseudopolinomial. 2. mochila (a) [0.5] Enuncie a Programa¸c˜ao Dinˆamica do Problema (b) [1.0] Rode para o exemplo: S = n (`, !) | (5, 2), (4, 3), (2, 2), (4, 2), (2, 1) o . (c) [1.0] Resolva as instˆancias, usando a tabela, para o problema de decis˜ao da mochila (S, L1, M1) = (S, 14, 7) e (S, L2, M2) = (S, 16, 8). 3. Considere o grafo G = (V, E) e seu complemento G = (V, E). b b a b c d e f g a b c d e f g G G colorac¸˜ao instˆancia: Grafo G = (V, E) e inteiro positivo k. pergunta: Existe uma parti¸c˜ao (V1, V2, . . . , Vk) = V para V em k conjuntos independentes? • [0.4] Determine se a instˆancia (G, 4) e (G, 3) s˜ao instˆancias Sim de colorac¸˜ao. • [0.6] No(s)caso(s) positivo(s) do item anterior determine o(s) certificado(s) apropriado(s). Considere o problema cobertura por cliques instˆancia: Grafo G = (V, E) e inteiro positivo k. pergunta: Existe uma parti¸c˜ao (V1, V2, . . . , Vk) = V para V em k cliques? • [0.4] Determine se a instˆancia (G, 4) e (G, 3) s˜ao instˆancias Sim de cobertura por cliques. • [0.6] No(s)caso(s) positivo(s) do item anterior determine o(s) certificado(s) apropriado(s). • [0.6] Prove que o problema cobertura por cliques est´a em NP. • [1.5] Prove que colorac¸˜ao / cobertura por cliques . 4. Mostre que: (a) [1.6] 3sat ´e NP-completo usando sat. (b) Usando sua redu¸c˜ao, dˆe 2 exemplos de instˆancias I1 e I2 de sat com 5 cl´ausulas cada: quatro cl´ausulas de tamanho 2, e uma de tamanho 4. Tal que: i. [0.4] I1 ´e satisfat´ıvel e mostre a instˆancia satisfat´ıvel de 3sat correspondente. ii. [0.4] I2 ´e n˜ao satisfat´ıvel e mostre a instˆancia n˜ao satisfat´ıvel de 3sat correspondente. h h