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 φ = C1∨C2…Cn, onde Ci = (zi1∧zi2∧zi3), 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 (zi1∧zi2∧zi3), 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 φ = (x1∧x2∧¬x3)∨(¬x1∧¬x2∧x4) temos o grafo:

Grafo Diamante
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).

Anúncios

Deixe um comentário »

RSS feed for comments on this post. TrackBack URI

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

Crie um website ou blog gratuito no WordPress.com.
Entries e comentários feeds.

%d blogueiros gostam disto: