Construcao e Analise de Algoritmos – Teste 12

       O problema de colorir um grafo com 3 cores consiste em atribuir uma
cor a cada vertice, de um conjunto com 3 cores, digamos Preto, Branco e Azul, 
de modo que dois vertices vizinhos não possuem a mesma cor. A versao de decisao 
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 e´ NP-completo, mostrando que

                      3-SAT  <  3-CORES.

       Dada uma formula Phi = C1 e C2 e ... e Cn, onde Ci = (zi1 ou zi2 ou
zi3), construimos um grafo G da seguinte maneira:

a) G possui dois vertices para cada variavel que aparece na formula correspondendo 
  'as suas versoes positiva e negativa.

b) Adicionamos dois vertices u e v, conectados entre si, e Conectamos o vertice u a 
  todas as variaveis negadas ou não-negadas.

c) Finalmente, incluimos um pentagono para cada clausula (zi1 ou zi2 ou zi3), onde 
  conectamos dois vertices vizinhos do pentagono ao vertice v, e os tres restantes 
  aos literais que compoem a clausula.

Exemplo:  Phi = (x1 ou x2 ou ~x4) E (~x1 ou ~x2 ou x3)


                     *----------------------------
                  /     \                        |
                 *       *-----------------------|
                / \     /                        |
               /  * -- *                         |
              /   |     \                        |
             /    |      \                       |
            x1   x2  x3   \  x4 -----------\     |
                     |     \         ... -- u -- v
           ~x1 ~x2   | ~x3  ~x4 -----------/     |
            |   |    |                           |
            |   |    |                           |
            |   * -- *                           |
             \ /     \                           |
              *       *--------------------------|
               \     /                           |
                  *-------------------------------


1) Prove que o grafo G construido como acima pode ser colorido com 3
cores se e somente se Phi pode ser satisfeita.

2) Mostre como a reducao acima pode ser usada para provar que
o problema de decidir se um grafo pode ser colorido com 3 ou 4 cores.
(Nota: Neste problema, sabe-se que o grafo pode ser
colorido com no maximo 4 cores.)