CIC 111Análise e Projeto de Análise e Projeto de

Algoritmos IIAlgoritmos II

Universidade Federal de Itajubá

Prof. Roberto Affonso da Costa Junior

AULA 17AULA 17

– Strong connectivity• Kosaraju’s algorithm• 2SAT problem

Fortemente ConectadoFortemente Conectado

Em um grafo direcionado, as arestas podem ser percorridas apenas em uma direção, portanto, mesmo que o grafo esteja conectado, isso não garante que haveria um caminho de um nó para outro nó. Por esse motivo, é significativo definir um novo conceito que requer mais do que a conectividade.

Um grafo está fortemente conectado se houver um caminho de qualquer nó para todos os outros nós no grafo. Por exemplo, na figura a seguir, o grafo esquerdo está fortemente conectado enquanto o gráfico direito não estiver.

Fortemente ConectadoFortemente Conectado

O grafo direito não está fortemente conectado porque, por exemplo, não há caminho do nó 2 para o nó 1.

1

4

1

43

1

4

1

43

Fortemente ConectadoFortemente Conectado

Os componentes fortemente conectados de um grafo dividem o grafo em partes fortemente conectadas que são tão grandes quanto possível. Os componentes fortemente conectados formam um grafo de componente acíclico que representa a estrutura profunda do grafo original.

Por exemplo, para o grafo

11 32

14 65

7

Fortemente ConectadoFortemente Conectado

os componentes fortemente conectados são os seguintes:

O grafo de componente correspondente é o seguinte:

11 32

14 65

7

Fortemente ConectadoFortemente Conectado

Os componentes são A = {1, 2}, B = {3, 6, 7}, C = {4} e D = {5}.

Um grafo de componente é um grafo acíclico e direcionado, por isso é mais fácil de processar do que o grafo original. Uma vez que o grafo não contém ciclos, podemos sempre construir um grafo topológico ordenado e usar técnicas de programação dinâmicas como as apresentadas na aula anterior.

1A B

1C D

Kosaraju’s algorithmKosaraju’s algorithm

O algoritmo de Kosaraju é um método eficiente para encontrar os componentes fortemente conectados de um grafo direcionado. O algoritmo executa duas buscas de profundidade:

a primeira pesquisa constrói uma lista de nós de acordo com a estrutura do grafo e a segunda pesquisa forma os componentes fortemente conectados.

Sites a visitarSites a visitar

PROGRAMA Kosaraju’s

Pesquisa 1Pesquisa 1

A primeira fase do algoritmo de Kosaraju constrói uma lista de nós na ordem em que uma pesquisa em profundidade primeiro os processa. O algoritmo passa pelos nós e inicia uma busca em profundidade em cada nó não processado. Cada nó será adicionado à lista depois de ter sido processado.

No grafo do exemplo, os nós são processados na seguinte ordem:

10/13

4/5 3/6 11/12

Pesquisa 1Pesquisa 1

A notação x / y significa que o processamento do nó começou no tempo x e terminou no tempo y. Assim, a lista correspondente é a seguinte:

11 32

14 65

7

1/8 2/7 9/14

Pesquisa 1Pesquisa 1

Nó Tempo Processamento

4 5

5 6

2 7

1 8

6 12

7 13

3 14

Pesquisa 2Pesquisa 2

A segunda fase do algoritmo forma os componentes fortemente conectados ao grafo. Primeiro, o algoritmo inverte todas as arestas no grafo. Isso garante que durante a segunda pesquisa, sempre encontraremos componentes fortemente conectados que não possuem nós extras.

Depois de reverter as arestas, o grafo do exemplo é o seguinte:

Pesquisa 2Pesquisa 2

Depois disso, o algoritmo passa pela lista de nós criados pela primeira busca, na ordem inversa. Se um nó não pertence a um componente, o algoritmo cria um novo componente e inicia uma busca de profundidade que adiciona todos os novos nós encontrados durante a busca para o novo componente.

11 32

14 65

7

Pesquisa 2Pesquisa 2

No grafo do exemplo, o primeiro componente começa no nó 3:

Observe que, uma vez que todas as arestas são invertidas, o componente não “foge” para outras partes no grafo.

11 32

14 65

7

Pesquisa 2Pesquisa 2

Os próximos nós na lista são os nós 7 e 6, mas eles já pertencem a um componente, então o próximo componente novo começa no nó 1:

11 32

14 65

7

Pesquisa 2Pesquisa 2

Finalmente, o algoritmo processa os nós 5 e 4 que criam os demais componentes conectados fortemente:

A complexidade do tempo do algoritmo é O(n + m), porque o algoritmo executa duas buscas de profundidade.

11 32

14 65

7

Problema 2SATProblema 2SAT

A forte conectividade também está vinculada ao problema 2SAT. Neste problema, recebemos uma fórmula lógica:

onde cada ai e b

i é uma variável lógica (x

1, x

2, …, x

n)

ou uma negação de uma variável lógica (¬ x1, ¬ x

2, …,

¬ xn). Os símbolos “ ” e “ ” indicam operadores ∧ ∨

lógicos “e” e “ou”. Nossa tarefa é atribuir a cada variável um valor para que a fórmula seja verdadeira ou afirmar que isso não é possível.

(a1∨b1)∧(a2∨b2)∧…∧(am∨bm)

Problema 2SATProblema 2SAT

Boolean Satisfiability ou simplesmente SAT é o problema de determinar se uma fórmula booleana é satisfatória ou insatisfatória.

Satisfatório: se as variáveis booleanas puderem ser atribuídas valores tais que a fórmula se torne TRUE, então dizemos que a fórmula é satisfatória.

Insatisfatório: se não for possível atribuir esses valores, então dizemos que a fórmula é insatisfatória.

Problema 2SATProblema 2SAT

Para que o valor do CNF (Forma Conjuntiva Normal) seja TRUE, o valor de cada cláusula deve ser TRUE. Deixe uma das cláusulas ser (A ∨ B).

(A B) = ∨ TRUE é equivalente a (¬A => B) (¬B => A)∧

Graficamente seria:

¬A B

¬B A

Problema 2SATProblema 2SAT

No entanto, a fórmula:

é verdadeiro quando as variáveis são atribuídas da seguinte maneira:

L1=(x2∨¬x1)∧(¬x1∨¬x2)∧(x1∨x3)∧(¬x2∨¬x3)∧( x1∨x4)

{x1= falsex2= falsex3=truex4=true

Problema 2SATProblema 2SAT

Por exemplo, a fórmula:

é sempre falso, independentemente de como atribuímos os valores. A razão para isso é que não podemos escolher um valor para x

1 sem criar uma

contradição. Se x1 for falso, ambos x

2 e ¬ x

2 devem ser

verdadeiros, o que é impossível e se x1 for verdadeiro,

ambos x3 e ¬ x

3 devem ser verdadeiros, o que também

é impossível.

L2=(x1∨x2)∧(x1∨¬x2)∧(¬x1∨x3)∧(¬x1∨¬x3)

Problema 2SATProblema 2SAT

O grafo para a fórmula L1 é:

¬ x3

x2

¬ x1

x4

¬ x4

x1

¬ x2

x3

Problema 2SATProblema 2SAT

E o grafo para a fórmula L2 é:

¬ x3

x2

¬ x1

x1

¬ x2

x3

Problema 2SATProblema 2SAT

A estrutura do grafo nos diz se é possível atribuir os valores das variáveis para que a fórmula seja verdadeira. Acontece que isso pode ser feito exatamente quando não há nós x

i e ¬ x

i, de modo que

ambos os nós pertençam ao mesmo componente fortemente conectado. Se existem tais nós, o gráfico contém um caminho de x

i a ¬ x

i e também um

caminho de ¬ xi para x

i, então ambos x

i e ¬ x

i devem

ser verdadeiros, o que não é possível.

Problema 2SATProblema 2SAT

No grafo da fórmula L1 não existem nós x

i e ¬ x

i de

modo que ambos os nós pertençam ao mesmo componente fortemente conectado, então existe uma solução. No grafo da fórmula L

2, todos os nós

pertencem ao mesmo componente fortemente conectado, portanto, uma solução não existe.

Problema 2SATProblema 2SAT

Se existe uma solução, os valores das variáveis podem ser encontrados através dos nós do grafo componente em uma ordem de classificação topológica reversa. Em cada etapa, processamos um componente que não contém arestas que levam a um componente não processado. Se as variáveis no componente não tiverem sido atribuídas valores, seus valores serão determinados de acordo com os valores no componente, e se eles já tiverem valores, eles permanecem inalterados. O processo continua até que cada variável tenha sido atribuída um valor.

Problema 2SATProblema 2SAT

O componente do grafo para a fórmula L1 é o

seguinte:

DB CA

Problema 2SATProblema 2SAT

Os componentes são A = {¬ x4}, B = {x

1, x

2, ¬ x

3}, C =

{¬ x1, ¬ x

2, x

3} e D = {x

4}. Ao construir a solução,

primeiro processamos o componente D onde x4 se

torna verdadeiro. Depois disso, processamos o componente C onde x

1 e x

2 tornam-se falsos e x

3 se

torna verdadeiro. Todas as variáveis foram atribuídas valores, portanto, os componentes restantes A e B não alteram as variáveis.

Problema 2SATProblema 2SAT

Observe que esse método funciona, porque o grafo possui uma estrutura especial: se houver caminhos do nó x

i para o nó x

j e do nó x

j para o nó ¬ x

j, o nó x

i

nunca se torna verdadeiro. A razão para isso é que existe também um caminho do nó ¬ x

j para o nó ¬ x

i,

e ambos xi e x

j se tornam falsos.

Um problema mais difícil é o problema 3SAT, onde cada parte da fórmula é da forma (a

i ∨ b

i ∨ c

i). Este

problema é NP-hard, então nenhum algoritmo eficiente para resolver o problema é conhecido.

Site a visitarSite a visitar

ExercícioExercício

Resolva o problema 2SAT para as expressões L1 e L

2,

utilizando o programa de Kosaraju.

Resolva para as expressões:

L3=(x1∨¬x2)∧(¬x1∨¬x2)

L4=(x4∨¬x2)∧(¬x3∨¬x2)∧(x1∨x4)∧(¬x1∨¬x3)