Baixe o app para aproveitar ainda mais
Prévia do material em texto
Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Roteiro da Aula 21 1 NP-completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) 2 Exerc´ıcio: Conjunto Independente (IS) 3 Exerc´ıcio: Circuito Hamiltoniano (HC) Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Clique Instaˆncia: grafo G = (V,E) e inteiro positivo k • Vamos reduzir 3SAT a Clique: • Dada uma 3CNF-fo´rmula φ, constru´ımos em tempo polinomial, um grafo G e um k, tal que: φ e´ satisfat´ıvel sse G possui uma clique de tamanho k Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Clique φ = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) x1 x2 x3 x2 x3x1 x1 x2 x3 x1 x2 x3 C1 C2 C3 C4 Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Clique φ = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) x1 x2 x3 x2 x3x1 x1 x2 x3 x1 x2 x3 C1 C2 C3 C4 Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Clique φ = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) x1 x2 x3 x2 x3x1 x1 x2 x3 x1 x2 x3 C1 C2 C3 C4 Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Clique φ = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) x1 x2 x3 x2 x3x1 x1 x2 x3 x1 x2 x3 C1 C2 C3 C4 Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Clique φ = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3) x1 x2 x3 x2 x3x1 x1 x2 x3 x1 x2 x3 C1 C2 C3 C4 • Se φ tem 4 cla´usulas, enta˜o G tem uma clique de tamanho 4, se e somente se φ e´ satisfat´ıvel. Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Situac¸a˜o atual P NP NP-Completo SAT 3SAT Clique Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Cobertura de Ve´rtices (Vertex Cover) 1 2 3 5 7 6 4 1 2 3 5 7 6 4 • Dado um grafo na˜o-direcionado G = (V,E) e um natural k, decidir se existe um subconjunto dos ve´rtices de G, Vc ⊆ V , |Vc| = k, tal que: • Para toda aresta (a, b) ∈ E: • a ∈ Vc; ou • b ∈ Vc. Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Cobertura de Ve´rtices (Vertex Cover) 1 2 3 5 7 6 4 1 2 3 5 7 6 4 Cobertura M´ınima • Dado um grafo na˜o-direcionado G = (V,E) e um natural k, decidir se existe um subconjunto dos ve´rtices de G, Vc ⊆ V , |Vc| = k, tal que: • Para toda aresta (a, b) ∈ E: • a ∈ Vc; ou • b ∈ Vc. Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Cobertura de Ve´rtices (Vertex Cover) Mas VC e´ NP-completo tambe´m... como mostrar? Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Cobertura de Ve´rtices (Vertex Cover) Mas VC e´ NP-completo tambe´m... como mostrar? • Vamos reduzir Clique a VC; Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Cobertura de Ve´rtices (Vertex Cover) Mas VC e´ NP-completo tambe´m... como mostrar? • Vamos reduzir Clique a VC; • Reduc¸a˜o claramente polinomial: Dada instaˆncia para clique G = (V,E), k, construa a instaˆncia G = (V,E), |V | − k para VC. • G possui cobertura de tamanho |V | − k sse G possui clique de tamanho k. Por queˆ? Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Conjunto Dominante (Dominating Set) 1 2 3 5 7 6 4 • Dado um grafo na˜o-direcionado G = (V,E) e um natural k, decidir se existe um subconjunto dos ve´rtices de G, Vc ⊆ V , |Vc| = k, tal que: • Para todo ve´rtice v ∈ V : • v ∈ Vc; ou • existe aresta (a, v) ∈ E e a ∈ Vc. Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Conjunto Dominante (Dominating Set) 1 2 3 5 7 6 4 • Dado um grafo na˜o-direcionado G = (V,E) e um natural k, decidir se existe um subconjunto dos ve´rtices de G, Vc ⊆ V , |Vc| = k, tal que: • Para todo ve´rtice v ∈ V : • v ∈ Vc; ou • existe aresta (a, v) ∈ E e a ∈ Vc. Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Conjunto Dominante (Dominating Set) 1 2 3 5 7 6 4 • Dado um grafo na˜o-direcionado G = (V,E) e um natural k, decidir se existe um subconjunto dos ve´rticesde G, Vc ⊆ V , |Vc| = k, tal que: • Para todo ve´rtice v ∈ V : • v ∈ Vc; ou • existe aresta (a, v) ∈ E e a ∈ Vc. Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Conjunto Dominante (Dominating Set) 1 2 3 5 7 6 4 Conjunto Dominante M´ınimo • Dado um grafo na˜o-direcionado G = (V,E) e um natural k, decidir se existe um subconjunto dos ve´rtices de G, Vc ⊆ V , |Vc| = k, tal que: • Para todo ve´rtice v ∈ V : • v ∈ Vc; ou • existe aresta (a, v) ∈ E e a ∈ Vc. Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Conjunto Dominante (Dominating Set) Mas DS e´ NP-completo tambe´m... como mostrar? Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Clique Situac¸a˜o atual Cobertura de Ve´rtices (Vertex Cover) Conjunto Dominante (Dominating Set) Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Conjunto Dominante (Dominating Set) Mas DS e´ NP-completo tambe´m... como mostrar? • Vamos reduzir VC a DS. Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Exerc´ıcio: Conjunto Independente (IS) Mostre que o seguinte problema e´ NP-completo 1 2 3 5 7 6 4 • Dado um grafo na˜o-direcionado G = (V,E) e um natural k, decidir se existe um subconjunto dos ve´rtices de G, Vc ⊆ V , |Vc| = k, tal que: • Se a ∈ Vc e b ∈ Vc, enta˜o (a, b) 6∈ Vc Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Caminho Hamiltoniano (HP) e´ NP-completo Ha´ uma reduc¸a˜o muito interessante de 3SAT para HP no Sipser Vale a pena conferir... Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Exerc´ıcio: Circuito Hamiltoniano (HC) Mostre que o seguinte problema e´ NP-completo 1 2 3 5 7 6 4 • Dado um grafo na˜o-direcionado G = (V,E), decidir se existe um circuito hamiltoniano em G. Quer dizer, uma permutac¸a˜o (x1, x2, x3, . . . , xn) dos ve´rtices, tal que: • (xi, xi+1) ∈ E, 1 ≤ i ≤ n− 1; e • (xn, x1) ∈ E. DICA: reduza HP a HC Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Exerc´ıcio: Circuito Hamiltoniano (HC) Mostre que o seguinte problema e´ NP-completo 1 2 3 5 7 6 4 • Dado um grafo na˜o-direcionado G = (V,E), decidir se existe um circuito hamiltoniano em G. Quer dizer, uma permutac¸a˜o (x1, x2, x3, . . . , xn) dos ve´rtices, tal que: • (xi, xi+1) ∈ E, 1 ≤ i ≤ n− 1; e • (xn, x1) ∈ E. DICA: reduza HP a HC Ana´lise de Algoritmos 113859 Aula 21 Roteiro NP- completude: exemplos Exerc´ıcio: Conjunto Independente (IS) Exerc´ıcio: Circuito Hamiltoniano (HC) Situac¸a˜o atual P NP NP-Completo SAT 3SAT Clique VC DS IS HP HC PRIMES PRIMES ? ? Roteiro NP-completude: exemplos Clique Situação atual Cobertura de Vértices (Vertex Cover) Conjunto Dominante (Dominating Set) Exercício: Conjunto Independente (IS) Exercício: Circuito Hamiltoniano (HC)
Compartilhar