Lista 12 Resolução

Resolução da Lista 12 de CAnA.

(Implicação Lógica) Supondo que φ pode ser satisfeito. Mostrar que existe uma 3-coloração para o grafo G=(V,E) gerado a partir de φ.

Seja Γ uma função Γ: VImplicação Lógica{v,f,i}, a função de coloração que vamos construir. Como φ pode ser satisfeito então existe um conjunto de atribuição de valores para as variáveis de φ que torna φ verdadeiro. Seja Ξ uma atribuição destas.

1) Vamos colorir primeiro os vértices que representam as variáveis.

  • Se Ξ(xi)=1 então Γ(xi)=v e Γ(¬xi)=f.
  • Se Ξ(xi)=0 então Γ(xi)=f e Γ(¬xi)=v.

Como o vértice u liga-se à todos as variáveis, logo ele vai está em contato com 2 cores distintas, o que obriga Γ(u)=i.

Exemplo) Para φ = (x1∧x2∧¬x3)∨(¬x1∧¬x2∧x4), temos uma atribuição Ξ = {<x1,1>, <x2,0>,<x3,1>,<x4,1>} que satisfaz φ. Várias outras atribuições seriam possíveis. Vamos denotar por verde como a cor para v, vermelho para f, cinza para i e preto para as cores que ainda não escolhemos.
A coloração que temos até agora é esta:

Grafo Diamante Parcialmente Colorido 1

2) Vamos colorir agora os pentágonos.

Grafo de Pentágono

Seja Pj o pentágono que corresponde à cláusula Cj. Seja Pij o i-éssimo vértice do pentágono Pj. Como a fórmula é verdadeira, toda cláusula Ci é verdadeira (porque ela é construída com ou’s). Como todo pentágono está ligado à uma cláusula, então todo pentágono está ligado à pelo menos um vértice cuja coloração é v (devido à (1)). Vamos escolher um desses vertices, digamos o vértice pxj, vamos atribuir Γ(Pxj)=i.

Exemplo) Para o φ que já vinhamos usando como exemplo já que já colorimos o seu interior. O pentagono de cima, vamos chamar de P1 se liga aos vértices x1, x2 e ¬x3. O único vertice que tem coloração v é o x1 então vamos colorir de i o vértice de P1 ligado a ele

O pentagono de baixo, vamos chamar de P2, está ligado aos vértices ¬x1,¬x2 e x4. Há dois vértices com coloração v (¬x2 e x4). Vamos escolher o vértice de P2 ligado a x4 para ter coloração i. A nova coloração que temos é esta:

Grafo Diamante Parcialmente Colorido 2

(continua…)

Deixe um comentário »

RSS feed for comments on this post. TrackBack URI

Deixe uma resposta

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

Blog no WordPress.com.
Entries e comentários feeds.

%d blogueiros gostam disto: