Lista 12

Problema retirado do Teste 12 da Disciplina de Construção e Análise de Algoritmos.

O problema de colorir um grafo com 3 cores consiste em atribuir uma cor a cada vértice, de um conjunto com 3 cores, digamos preto, branco e azul, de modo que dois vértices vizinhos não possuem a mesma cor. A versão de decisão deste problema consiste em decidir se um dado grafo G=(V,E) pode ser colorido com apenas 3 cores.

A seguir provaremos que este problema é NP-Completo mostrando que 3-SAT < 3-Cores.

Dado uma fóruma φ = C₁∨C₂…C_n, onde C_i = (z_i1∧z_i2∧z_i3), construímos um grafo G da seguinte maneira:

• G possúi dois vértices, conectados entre si, para cada variável que aparece na fórumala correspondendo às suas versões positiva e negativa.
• Adicionamos dois vértices ue v conectados entre si, e conectamos o vértice u à todas as variáveis negadas ou não negadas.
• Incluímos um pentágono para cada cláusula (z_i1∧z_i2∧z_i3), onde conectamos dois vértices vizinhos do pentágono ao vértice v, e os trÊs restantes aos literais que compõem a cláusula.

Exemplo:

Para a fórmula φ = (x₁∧x₂∧¬x₃)∨(¬x₁∧¬x₂∧x₄) temos o grafo:

3) Prove que o grafo G construído pode ser colorido com 3 cores se e somente se φ pode ser satisfeita.

4) Mostre como a redução acima pode ser usada para provar que o problema de decidir se um grafo po ser colorido com 3 ou 4 cores é NP-Completo. (Nota: Neste problema, sabe-se que o grafo pode ser colorido com no máximo 4 cores).