Algoritmo em Grafos - Notas de Aula

Prévia do material em texto

Universidade do Estado do Rio de Janeiro
Centro de Tecnologia e Ciências
Instituto de Matemática e Estat́ıstica
Matéria: Algoritmo em Grafos
Notas de aula
Prof. Dr.: Luérbio Farias
Rio de Janeiro
SUMÁRIO
1 GRAFOS E SUBGRAFOS 3
1.1 Notação O, ω, θ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Grau do Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Subgrafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Tipos de Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Isomorfismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 Classes de Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6.1 Grafo Completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6.2 Grafo Bipartido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6.3 Clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6.4 Grafo Complementar . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6.5 Grafo Caminho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6.6 Grafo Ciclo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6.7 Grafo Roda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6.8 Grafo n-Cubo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6.9 Grafo R-regular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.10 Grafo Trivial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 CONECTIVIDADE 13
2.1 Componente Conexa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Grafo Conexo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Busca em Profundidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Corte de Vértices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Corte de Arestas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 ÁRVORES E FLORESTAS 18
3.1 Árvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Geodésia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4 PLANARIDADE 25
5 COLORAÇÃO 32
6 TRILHAS EULERIANAS E CICLOS HAMILTONIANO 33
6.1 Trilha Euleriana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
6.2 Ciclo Hamiltoniano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
7 PROBLEMAS DE DECISÃO 37
7.1 Classe P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
7.2 Classe NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.3 Satisfabilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.4 Transformação Polinomial . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.5 NP-Completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7.6 3 Satisfabilidade (3SAT) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
7.6.1 SAT ∝ 3SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
7.6.2 3SAT ∝ ConjuntoIndependente . . . . . . . . . . . . . . . . . . . 45
7.6.3 Conjunto Independente está em NP . . . . . . . . . . . . . . . . . 46
3
Caṕıtulo 1
GRAFOS E SUBGRAFOS
1.1 Notação O, ω, θ
Definição 1.1: Dado um par de funções f, g : R→ R, dizemos que
• f é O(g) se existe α ∈ R+ e n0 ∈ N tal que ∀x ≥ n0, f(x) ≤ α · g(x).
• f é ω(g) se existem α ∈ R+ e n0 ∈ N tal que ∀x > n0, g(x) ≤ α · f(x).
• f é θ(g), f é O(g) e f é ω(g).
(a) f é O(g). (b) f é θ(g).
(c) f é ω(g).
Figura 1.1: Notações Assintóticas.
4
1.2 Grafo
Definição 1.2: Um grafo é uma dupla G = (V, E) de conjuntos, onde V é o
conjunto finito, não vazio, de vértices e E é o conjunto de arestas formado por pares, não
ordenados, de distintos elementos de V. Notamos n = |V | e m = |E|.
Definição 1.3: Se uv ∈ E, então notamos uv = (u, v), e, neste caso, dizemos que
u é Adjacente à v, e que a aresta uv é Incidente em u e em v.
Definição 1.4: A vizinhança N(v) de v, ou vizinhança aberta de v, é o conjunto
N(v) = u:uv ∈ E. A vizinhança fechada de v é N(v) = N(v) ∪ v. Se uv ∈ E dizemos
tambem que u é vizinho de v.
Definição 1.5: O grau d(v) de v é d(v) = |N(v)|.
Representamos um grafo por uma matriz de adjacência M, ondeMij =
0, se ij 6∈ E1, se ij ∈ E .
(a) Exemplo de Grafo.
(b) Matriz Adjacncia do grafo ao lado.
Figura 1.2: Exemplo de Grafo.
Note que a soma de todas as linhas de M totaliza
∑
v∈V d(v). Que em nosso exem-
plo,
∑
v∈V d(v) = 12 = 2 ·m = 2 · 6.
Teorema 1.1: Dado um grafo G = (V, E). Então
∑
v∈V d(v) = 2 ·m.
Prova: Note que em M, a matriz adjacência de G, a linha correspondente ao vértice
v ∈ V soma igual ao grau d(v) de v. Assim, a soma de todas as linhas dá
∑
v∈V d(v).
Agora esta soma pode ser parcelada com a soma de 2 unidades (1 em Mij e 1 em Mji)
para cada aresta ij ∈ E. Assim,
∑
v∈V d(v) = 2 ·m.
5
Corolário 1.1: O número de vértices de grau ı́mpar em G = (V, E) é par.
Prova: Veja que ∑
v∈V
d(v) = 2 ·m
∑
v∈V ,d(v)par
d(v) +
∑
v∈V ,d(v)impar
d(v) = 2 ·m
Assim,
∑
v∈V ,d(v)impar
d(v) = (2 ·m)−
∑
v∈V ,d(v)par
d(v)
Como a soma de ı́mpares é par, o número de parcelas é par. Logo, existe um
número par de vértices de grau ı́mpar.
1.2.1 Grau do Grafo
Notamos o grau mı́nimo de um grafo G, dado por δ(G), é igual ao menor d(v). Já
o grau máximo de um grafo G, dado por ∆(G), é igual ao maior d(v).
1.3 Subgrafo
Definição 1.6: Dizemos que o grafo F é um subgrafo do grafo G = (V, E) se
V(F) ⊂ V(G) e E(F) ⊂ E(G).
Dado um conjunto S ⊂ V (G). O subgrafo G[S] de G induzido por S possui um
conjunto de vértices igual a S e se u, v ∈ S e uv ∈ E(G), então uv ∈ E(G[S]).
Exemplo, Figura 1.3.
6
(a) Grafo A.
(b) Subgrafo B.
(c) Subgrafo C.
Figura 1.3: Grafo e seus subgrafos.
O grafo B e o grafo C são subgrafos de A. Porém, B não é subgrafo de C e C não
é subgrafo de B.
1.4 Tipos de Grafos
Definição 1.7: Dado um grafo G = (V, E). Dada S = (v1, v2, ..., vn) uma
sequência de vértices de V. Dizemos que S é um Passeio se vivi+1 ∈ E para todo
i ∈ (1, 2, ..., n− 1). Dizemos que o passeio S é fechado se v1 = vk.
Definição 1.8: Dizemos que o passeio S é uma Trilha se vivi+1 6= vjvj+1 e i 6= j
(S não repete arestas).
Definição 1.9: Dizemos que o Comprimento de S é k − 1 o número de arestas
(repetidas ou não) de S.
7
Definição 1.10: Dizemos que o passeio é um Caminho se vi 6= vj e i 6= j.
Definição 1.11: Um Ciclo é uma trilha fechada com uma única repetição de
vértices (v1 = vk).
Definição 1.12: Dizemos que um grafo é Aćıclico se não possui ciclos.
Exemplo.
Baseado no grafo G acima, mostre:
1. Um passeio que não é trilha.
(A, B, C, D, E), (A, B, A), (A, B, C, A, B)
2. Uma trilha que não é caminho.
(A, B, C, A, E), (A, B, C, A)
3. Um caminho com seu comprimento máximo.
(A, B, C, D, E) com comprimento igual a 4.
4. Todos os ciclos de G.
(A, B, C, A), (A, B, C, D, E, A), (A, C, D, E, A), com comprimentos iguais a 3,
5 e 4, respectivamente.
1.5 Isomorfismo
Definição 1.13: Dados dois grafos, G e H. Dizemos que G é isomorfo a H se
existe f : V (G)
−→
bijV (H) e uv ∈ E(G) se, somente se, f(u)f(v) ∈ E(H). E, neste caso,
escrevemos G ∼ H.
8
(a) Grafo K5.
(b) Grafo Q3.
Figura 1.4: Grafos não isomorfos.
(a) Grafo K4,4.
(b) Grafo Q3.
Figura 1.5: Grafos isomorfos.
1.6 Classes de Grafos
1.6.1 Grafo Completo
Definição 1.14: Dado n ≥ 1, n ∈ N, um Grafo Completo Kn = (V,E) satisfaz
que para todo u, v ∈ V , uv ∈ E.
9
Tabela 1.1: Número vértices e de arestas do Kn
|V (G)| |E(G)|
1 0
2 1
3 3
4 6
5 10
...
...
n n·(n−1)
2
C(n,p) =
n!
p! · (n− p)!
Como uma aresta é entre dois vértices, a fórmula fica da seguintemaneira.
C(n,2) =
n!
2!·(n−2)! => C(n,2) =
n·(n−1)·(n−2)!
2!·(n−2)! => 2! = 2 => C(n,2) =
n·(n−1)
2
Figura 1.6: Grafo Completo, K5
1.6.2 Grafo Bipartido
Definição 1.15: Um Grafo Bipartido G = (V, E) satisfaz que V = V1 ∪ V2 e
V1 ∩ V2 = 0, e escrevemos V = (V1 ∪ V2), tal que se uv ∈ E, então u ∈ V1 e v ∈ V2. Os
conjuntos V1 e V2 são conjuntos independentes. Um exemplo de Grafo Bipartido é o grafo
da Figura 1.7.
10
Figura 1.7: Grafo Bipartido.
Definição 1.16: Um Grafo Bipartido é dito Completo, Kn1,n2 = G(V,E), se existe
uma partição V = (V1, V2) em conjuntos independentes V1 e V2 tal que se u ∈ V1 e v ∈ V2,
então uv ∈ E e |V1| = n1 e |V2| = n1.
O número de vértices e o número de arestas para um grafo bipartido completo
Kn1,n2 é, respectivamente, |V (G)| = n+m e |E(G)| = n1 · n2.
1.6.3 Clique
Definição 1.17: Dado um grafo G = (V,E) uma Clique S ⊂ V de G, satisfaz que
se u, v ∈ S, então uv ∈ E.
1.6.4 Grafo Complementar
Definição 1.18: Dado um grafo G = (V,E), o Grafo Complementar Ḡ = (V, Ē)
satisfaz que e ∈ E se, somente se, e 6∈ Ē.
(a) Grafo G. (b) Grafo Ḡ.
Figura 1.8: Grafo Complementar.
No exemlo da Figura 1.8, os grafos são chamados de Grafos Auto-complementares.
11
1.6.5 Grafo Caminho
Definição 1.19: Um Grafo Caminho satisfaz que Pn = (V,E), n ∈ N, V =
(v1, v2, ..., vn) e E = (vivi+1 : i ∈ (1, 2, ..., n− 1)). Exemplo de Grafo Caminho na Figura
1.9.
Figura 1.9: Grafo P4
1.6.6 Grafo Ciclo
Definição 1.20: Dado n ∈ N∗, n ≥ 3, o Grafo Ciclo satisfaz que Cn = (V,E),
V = (v1, v2, ..., vn) e E = vivi+1 : i ∈ (1, 2, ..., n− 1) ∪ (v1vn).
Figura 1.10: Cn
1.6.7 Grafo Roda
Definição 1.21: Um Grafo Roda (Wheel)Wn = (V,E) satisfaz que V = (v1, v2, ..., vn, c)
e E = (vivi+1 : i ∈ (1, 2, ..., n− 1)) ∪ (cvi : i ∈ (1, 2, ..., n)).
Figura 1.11: Grafo Roda W5
1.6.8 Grafo n-Cubo
Definição 1.22: Dado n ∈ N, um n-Cubo Qn = (V,E), onde |V | = 2n e |E| =
n · 2n−1, existe f : (0, 1)n
−→
bijV e E = (uv : |diff(u, v)| = 1).
12
Figura 1.12: Grafo Cubo Q3
1.6.9 Grafo R-regular
Definição 1.23: Um grafo G = (V,E) é R-regular se ∀v ∈ V , d(v) = R. Se G é
3-regular, G é cúbico.
Fato:
• Qn é n-regular.
• Kn é (n-1)-regular.
• Cn é 2-regular.
1.6.10 Grafo Trivial
Definição 1.24: Dado um grafo conexo, dizemos que é Trivial se n = 1.
13
Caṕıtulo 2
CONECTIVIDADE
2.1 Componente Conexa
Definição 2.1: Dizemos que dois vértices, u e v, estão na mesma Componente
Conexa de um grafo G = (V,E) se existe um caminho P que liga u até v, em G.
2.2 Grafo Conexo
Definição 2.2: Dizemos que um grafo G = (V,E) é Conexo se o número de
componentes conexas de G é igual a 1.
2.3 Busca em Profundidade
Dado um grafo G = (V,E), o algoritmo DFS (Depth First Search) explora as
arestas do vértice mais recente pesquisado que ainda possui arestas não exploradas. Este
processo continua até termos explorado todos os vértices a partir do vértice fonte. Se
ainda existirem vértices não explorados, o algoritmo inicia a DFS em um deles. Após
a execução, o algoritmo particiona E nos conjuntos Arestas da floresta de DFS, Arestas
Back, Arestas Foward e Arestas Across.
• Arestas da floresta de DFS são arestas uv onde v é explorado imediatamente após
u ser explorado.
• Arestas Back, ou Arestas Retorno, v é ancestral de u e v não é pai de u (aresta −→uv).
14
• Arestas Foward são arestas −→uv tais que u foi explorado antes de v.
• Arestas Across (cruzadas) são as arestas restantes.
Exemplo a Figura 2.1.
(a) Grafo G.
(b) Árvore gerada pelo DFS no grafo G.
Figura 2.1: Grafos e sua árvore da DFS.
2.4 Corte de Vértices
Definição 2.3: Um corte de vértices de G é um conjunto S ⊂ V tal que o grafo
H = (V-S, E’), onde E ′ = (uv : u ∈ S e v ∈ S) é desconexo ou trivial.
Um corte de vértices com 1 vértice é chamado articulação.
A conectividade de vértices cv(G) de G é o tamanho do menor corte de vértices de
G.
2.5 Corte de Arestas
Definição 2.4: Um corte de arestas de G é um conjunto Y ⊂ E tal que o grafo F
= (V, E-Y) é desconexo. Um corte de arestas com 1 arestas é chamado ponte.
A conectividade de arestas ce(G) de G é o tamanho (número de arestas) do menor
corte de arestas de G.
15
Kn Kn1,n2 Cn Pn Wn Qn
cv(G) n-1 min(n1,n2) 2 0, se n = 1 3 n
1, se n > 1
ce(G) n-1 min(n1,n2) 2 0, se n = 1 3 n
1, se n > 1
δ n-1 min(n1,n2) 2 0, se n = 1 3 n
1, se n > 1
Exemplo
G e H na 2.3 são conexos, então cv(G) > 0, cv(H) > 0, ce(G) > 0 e ce(H) > 0.
(a) Grafo G.
(b) Grafo H.
Figura 2.2: Grafos de exemplo para corte de vértice e corte de aresta.
No grafo G, 2.2a, cv(G) = 1, pois existe a articulação b e ce(G) = 2, pois G não
tem ponte ce(G) > 1 e existe o corte bc, bd de tamanho 2.
No grafo H, 2.2b, cv(H) = 1, pois existem as articulações 3 e 4 e ce(H) = 1, pois
H tem uma ponte (3,4) em H.
Teorema 2.1: Dado G = (V,E) um grafo conexo. Se G tem uma ponte uv, então
G tem uma articulação que é u ou v.
Prova
Suponha que G é conexo e que uv é uma ponte de G.
Se G = K2, então u e v são articulações, porque G− u é trivial.
Se G não é K2, então existe w, w 6= u e w 6= v tal que, por exemplo, wu ∈ E e
wv 6∈ E.
16
Vamos olhar para H = G − uv. O grafo H tem 2 coponentes conexas: Cu que
contém vértice u e Cv que contém o vértice v. Note que em G todos os caminhos de w
até v passam por u, caso contrário H não seria desconexo. (existiria um caminho em H
de u até v).
Logo, em G − u temos uma componente conexa contendo v e uma componente
conexa distinta contendo w. Logo u é a articulação procurada.
Teorema 2.2: Dado G = (V,E), então δ ≥ ce(G).
Prova
Se G é desconexo, então ce(G) = 0, como δ ≥ 0, este caso está certo.
Se G é conexo, então seja v o vértice com d(v) = δ e E
′
= (vv1, vv2, ..., vvδ) as
arestas incidentes à v. Veja que G − E ′ é desconexo (com a componente Cv = (v, 6 0)
trivial). Como ce(G) é o tamanho do menor corte de arestas, ce(G) ≤ |E ′ | = δ.
Teorema 2.3: Dado um grafo G = (V,E), cv(G) ≤ ce(G).
Prova:
Indução em ce(G) ≥ 0.
Suponha que ce(G) = 0. Então G é desconexo ou trivial.
Logo, 0 = cv(G) ≤ 0 = ce(G) (Base k = 0).
Suponha (indução forte) que para algum k ≥ 0. Se ce(G) ≤ k, então cv(G) ≤
ce(G) (hipótese de indução forte).
Tome G com ce(G) = k + 1. Sejam e1, e2, ..., ek, ek+1 as arestas tal que G −
(e1, e2, ..., ek, ek+1) é desconexo, com ce(G) ≥ k + 1 ≥ 1, precisamos tirar, pelo menos,
uma aresta. Portanto, G − (e1, e2, ..., ek, ek+1) não é trivial (G − (e1, e2, ..., ek, ek+1) tem,
pelo menos, 2 vértices).
Veja que ce(G− (e1)) = k. Pela hipótese de indução, cv(G− (e1)) ≤ k. Tome um
corte de vértices S de G− (e1) com |S| = cv(G− (e1)).
Vamos olhar para G - S, duas coisas podem acontecer.
1. G - S é desconexo. Isso é ótimo! Porque cv(G) ≤ |S| ≤ k < k + 1 = ce(G).
2. G - S é conexo. Logo, G − S = ((G − e1) − S) ∪ (e1). Onde ((G − e1) − S) é
desconexo.
17
Logo e1 é uma ponte de G - S.
Pelo teorema prévio, existe uma articulação v em G - S.
Logo, G− (s ∪ (v)) é desconexo ou trivial.
Portanto, S ∪ (v) é um corte de vértices de G e cv(G) ≤ |S ∪ (v)| ≤ k+ 1 = ce(G).
Corolário 2.1: Dado G = (V,E), cv(G) ≤ ce(G) ≤ δ.
Prova
A partir dos teoremas prévios.
Teorema 2.4: cv(Qn) = n.
Prova
É válido se n = 0, pois Qn é trivial neste caso e cv(Qn) = 0. (Base)
Suponha que para algum k ≥ 0, se n ≤ k, então cv(Qn) = n.
Considere que o produto de um grafo G por um grafo H é um grafo G x H, onde
V (G · H) = ((u, v) : u ∈ V (G) e v ∈ V (H)) e E = ((u, v), (u,w), (a, b), (t, b)) com
vw ∈ E(H) e at ∈ E(G).
(a) Grafo G.
(b) Grafo H.
(c) Grafo G × H.
Figura 2.3: Produto entre os Grafos G e H
Note que Qn = Qn−1 ×K2, n > 0.
18
Caṕıtulo 3
ÁRVORES E FLORESTAS
3.1 Árvores
Definição 3.1: Dado um grafo G = (V,E) dizemos que G é aćıclico se G não
possui ciclo como subgrafo.
Definição 3.2: Uma floresta é um grafo aćıclico.
Definição 3.3: Uma árvore é um grafoaćıclico e conexo.
Teorema 3.1: Um grafo G = (V,E) é uma árvore se, somente se, para cada par
de vértices u, v ∈ V (G), existe um único caminho que liga u até v.
Prova
Suponha que G é uma árvore.
Logo G é conexo.
Se u, v ∈ V , então, porque G é conexo, existe um caminho P que liga u até v,
P = (u = p1, p2, ..., pk = v).
Vamos provar que P é único.
Suponha por absurdo que existe Q = (u = p1, q2, q3, ..., qr−1, qr = pk = v) com
Q 6= P , onde Q liga u até v. Afirmo que existe menor i ∈ (1, 2, ..., k) tal que qi = pi e
qi+1 6= pi+1, caoso contrário, Q = P . Afirmo tambem que existe um menor a > i + 1 e
um menor b > i+ 1 tais que qa = pb, pois Q e P terminam em v, isto é, se a = r e b = k,
então qr = pk.
19
Figura 3.1: Caminho único.
Note que (qi, qi+1, ..., qa, pb−1, pb−2, ..., pi+1, pi) é um ciclo de G, uma contradição,
porque G é uma árvore e, portanto, aćıclio. Logo, para cada u, v ∈ V existe um único
caminho que liga u até v.
Suponha que para cada par de vértices u, v ∈ V existe um único caminho P que
liga u até v. Logo, G é conexo.
Suponha que G não é aćıclico. Logo existe um ciclo (a1, a2, a3, ..., ak, a1) em G.
Portanto, dados a1 e a2 existem caminhos distintos P = (a1, a2) e Q = (a1, ak, ak−1, ..., a2)
que ligam a1 até a2, uma contradição porque, por hipótese, estes caminhos seriam únicos
(P = Q). Logo, G é aćıclico. E Portanto, G é uma árvore.
Teorema 3.2: Se G = (V,E) é uma árvore, então m = n− 1.
Prova:
Indução em n ≥ 1.
Se n = 1, então m = 0 = 1− 1 = n− 1 (Base de indução).
Suponha que exista k ≥ 1 tal que se n ≤ k, e G é uma árvore, então m = n − 1
(hipótese de indução forte).
Tome uma árvore G = (V,E) com k + 1 = n.
Portanto, n ≥ 2 (porque n = k + 1 ≥ 1 + 1 = 2).
Como G é conexo, existe uma aresta e = uv em G.
Lema 3.1: Se uv ∈ E e G = (V,E) é uma árvore, então uv é uma ponte.
Prova:
Note que (u,v) é um caminho que liga u até v. Pelo teorema prévio, não existe
caminho que ligue u até v em G− (uv).
Colorário 3.1: Todas as arestas de uma árvore são pontes.
20
Pelo lema, G − uv é uma floresta com duas componentes conexas, T1 e T2, cada
uma com número de vértices n1 e n2. Mais ainda, n1 ≤ k e n2 ≤ k.
Figura 3.2: Árvore com mais de 1 componente conexa.
Pela Hipótese de Indução, se |E(T1) = m1, e |E(T2)| = m2 temos que m1 =
n1 − 1 e m2 = n2 − 1. Logo:
m = |E(T1)|+ |E(T2)|+ |uv|
m = (n1 − 1) + (n2 − 1) + 1
m = n1 + n2 − 1
Como n = n1 + n2.
m = n− 1
Definição 3.4: Dado um grafo G = (V,E) e v ∈ V , se d(v) = 1, dizemos que v é
um vértice pendente de G. G é uma árvore, chamamos v de folha.
Teorema 3.3: Se G = (V,E) é uma árvore não trivial, então G tem, pelo menos,
duas folhas.
Prova: Suponha que G é uma árvore não trivial (por absurdo) com zero folhas.
Logo, n ≥ 2 (G não é trivial) e assim, cada v ∈ V tem d(v) = 2 (Pois se d(v) = 0,
v é isolado e como n ≥ 2, G não é conexo. E se d(v) = 1, então v é uma folhaque não
existe pela hipótese de zero folhas).
Agora, 2n− 2 = 2m = Σv∈V d(v) ≥ 2m. E assim, −2 ≥ 0, uma contradição.
Suponha, por absurdo, que G é uma árvore com, exatamente, uma folha v.
Logo, existem n−1 vértices cada grau maior, ou igual, a dois. Dáı, 2n−2 = 2m =
Σv∈V d(v) ≥ 2(n − 1) + 1 = 2n − 1. A contradição (−1 ≥ 0) final. Logo, existem pelo
21
menos 2 folhas na árvore G.
3.2 Geodésia
Definição 3.5: Dado um grafo G = (V,E) e u, v ∈ V . A distância, d(u,v), de u
até v é o númeor de arestas em um menor caminho que liga u até v (o comprimento de
um menor caminho) se u e v pertencem a mesma componente conexa e d(u, v) = ∞, se
u,v pertencem a diferentes componentes conexas. Chamamos tal caminho de Geodésia de
u e v. O diâmetro de G é o comprimento de sua maior Geodésia.
Geodésica de a,b: (a,b)
Geodésica de a,d: (a, c, d), (a, e, d)
d(a,a) = 0
d(a,b) = 1
d(a,c) = 1
d(a,d) = 2
d(a,e) = 1
diâmetro(G) = 2
G Kn Cn Kn1,n2 Wn Qn Pn Sn
diâmetro 0, se n = 0 bn
2
c 1, se n1 = n2 = 1 1, n = 3 n n− 1 1, se n = 1
1, se n > 1 2, caso contrário 2, n > 3 2, se n > 1
Teorema 3.4: G(V,E) é bipartido se, somente se, todos os cilcos de G tem número
par de vértices.
22
Prova: Suponha que G é um grafo bipartido.
Suponha, por absurdo, que Ck = (v1, v2, ..., vk) é um ciclo subgrafo de G, tal que
k = 2q + 1, q ∈ N.
Seja V = (V1, V2) uma partição em conjuntos independentes de G.
Assuma que v1 ∈ V1.
Por causa de
v1v2 ∈ E, v2v3 ∈ E, · · · , v2q+1v2q ∈ E.
E como V1 e V2 são independentes, temos que
v1 ∈ V1, v2 ∈ V2, v3 ∈ V1, · · · , v2q+1 ∈ V1, v1 ∈ V2 (contradição).
Figura 3.3: Exemplo para o teorema 1.2.
Logo, todos os ciclos em G são pares.
Suponha que todos os ciclos de G são pares.
Assumimos que G é conexo.
Considere a receita.
Tome um vértice v ∈ V . Para todo u ∈ V , coloque u ∈ V1, se d(u,v) é ı́mpar. Ou
u ∈ V2, se d(u,v) é par.
Vamos ver se a receita funciona. Com certeza V = (V1, V2) é uma partição. Supo-
nha por absurdo que V1 não é independente. Seja uv ∈ E com u, v ∈ V1.
23
Figura 3.4
Assuma que d(v, u) ≤ d(v, w). Se d(v, u) < d(v, w), então d(v, w) ≤ d(v, w) + 1
considerando a geodésica de v e u mais a aresta uv. Como u, v ∈ V 1, temos que d(u, v) =
d(v, w).
Tome o menor ciclo que contenha u e v com vértices x tal que d(x, v) < d(v, u).
Figura 3.5
Se o vértice t do ciclo com menor distância até v é, tal que
24
(a)
(b)
Figura 3.6
Se t ∈ V1, as seções de t até u e w tem comprimento (númeor de arestas) par. Isto
da um ciclo com uw de comprimento 2k + 2q + 1 = 2p+ 1, uma contradição.
Se t ∈ V2, o ciclo tem número de arestas (2q + 1) + (2p + 1) = 2k + 1, a outra
contradição.
25
Caṕıtulo 4
PLANARIDADE
Definição 4.1: Dizemos que um grafo G = (V,E) é planar se existe um desenho
D(G) no plano de G sem cruzamento de arestas. Neste caso, dizemos que D(G) é um
desenho plano de G.
Exemplos:
(a)
(b)
(a) Desenho de K4 não planar. (b) Desenho de K4 planar.
Figura 4.2
26
Figura 4.3: K2,n é planar.
Teorema 4.1: K5 não é planar.
Prova: Suponha por absurdo que K5 é planar. Seja V (K5) = (a, b, c, d, e). Seja
D(K5) um desenho plano de K5. Como K5 não tem cruzamentos, o cilco (a, b, c, a)
divide o plano em 2 regiões conexas, R1 e R2.
O vértice d está em uma dessas regiões (digamos R1). Como d é adjacente a a, b
e c, temos agora 4 regiões do plano.
R1 = (a, b, c, a)
R2 = (a, d, b, a)
R3 = (b, d, c, b)
R4 = (a, d, c, a)
27
Pergunta: Onde fica o vértice e?
Como cada região tem 3 vértices e o vértice e tem grau 4, não há lugar para o
vértice e, uma contradição. Logo, K5 não é planar.
Teorema 4.2: K3,3 não é planar.
Suponha por absurdo que K3,3 é planar.
Seja V = (V1, V2) = (a, b, c, 1, 2, 3) a partição em conjuntos independentes de V.
Considere que o ciclo (a, 1, b, 2, a) divide o plano nas regiões conexas R1 e R2 em
um desenho plano D(3,3).
O vértice c pertence a R1. Logo temos 3 regiões.
R1 = (a, 1, b, 2, a)
R2 = (a, 1, c, 2, a)
R3 = (b, 1, c, 2, b)
Pergunta: Em qual destas 3 regiões fica vértice 3 ?
Resposta: Não existe lugar para o vértice 3. Pois cada uma das 3 regiões (R1, R2
e R3) tem exatamente 2 vértices em a, b, c, enquanto N(3) = a, b, c. Uma contradição.
Logo k3,3 não é planar.
Definição 4.2: Dizemos que um grafo H é uma subdivisão de um grafo G se
existe uma função f : E(G) −→ N tal que V (G) ⊂ V (H) e para cada e ∈ E(G) existem
adicionais ua1, a1a2, ..., af(e)−1af(e), af(e)v ∈ E(H).
Exemplo:
28
(a) (b)
Teorema 4.3 (KURATOWSKI, 1936):
Um grafo G não é planar se, somente se, G tem uma subdivisão de K5 ou K3,3.
Exemplo:
Q4 não é planar.
(a)
(b)
29
Definição 4.3: Dado um desenho plano D(G) de um grafo planar G = (V, E).
Uma face f de D(G) é um passeio fechado que define uma região conexa R de D(G). O
tamanho |f | de f é o número de suas arestas e notamos |f | = d(f), ou Grau da Face f.
Exemplo:
f1 = (a, b,c, j, k, l, k, a)
f2 = (c, d, i, c)
f3 = (i, d, e, i)
f4 = (f, g, h, f)
f5 = (a, b, c, d, e, f, g, h, f, e, i, c, j, k, a)
d(f1) = 7
d(f2) = 3
d(f3) = 3
d(f4) = 3
d(f5) = 14
∑
d(f) = 2m = 30
Teorema 4.4: Se D(G) é um desenho plano de um grafo conexo planar, então∑
f∈D(G) d(f) = 2m.
Prova:
Arestas em ciclos são contadas uma vez em cada face e pontes são contadas duas
vezes em uma mesma face.
Teorema 4.5: Se G = (V, E) é um grafo planar e conexo, D(G) é um desenho
plano de G, então F + n = m+ 2, onde F é o número de faces de G.
Prova:
30
Por indução em F ≥ 1.
Se F = 1, então G é aćıclico, pois caso contrário F ≥ 2 (uma face dentro do ciclo
e outra face fora do ciclo). Logo, G é aćıclico e conexo. Assim, G é uma árvore.
Em uma árvore, m = n+ 1. Assim:
n = m+ 1
F + n = 1 + (m+ 1)
F + n = 2 +m(Base)
Suponha que ∃k ≥ 1 tal que se F ≤ k, então F +n = m+ 2. (Hipótese de indução
- HI)
Seja um desenho D(G) plano de um grafo planar G com F = k + 1 faces.
Como K ≥ 1 e F ≥ 2. Portanto existe um ciclo em G. Logo, existe uma aresta e
em G que não é ponte (e = uv do ciclo).
Vamos olhar para H = G− e.
Sabemos que H é conexo porque G é conexo, e não é ponte e que F (H) = k.
Pois as duas faces F1 e F2 que e pertencia tornam-se uma única face em D(H) =
D(G− e). Assim, pela HI temos que
k + n = m− 1 + 2
Onde:
F (H) = k
|V (H)| = |V (G)|
|E(H)| = m
Portanto em D(G) temos
31
k + 1 + n = (m− 1) + 1 + 2
Onde:
F = k + 1
m = (m− 1) + 1
Logo:
K + 1 + n = m+ 2
Teorema 4.6: Se G = (V, E) é um grafo planar e n ≥ 3, então m ≤ 3n− 6.
Prova:
Veja que 2m =
∑
d(f). Como G tem n ≥ 3, d(f) ≥ 3.
Logo, 2m =
∑
f∈F d(f) ≥ 3F .
Assim,
2m =≥ 3F = 3(m+ 2− n)
2m ≥ 3(m+ 2− n)
2m ≥ 3m+ 6− 3n
−m ≥ 6− 3n
m ≤ 3n− 6
Teorema 4.6: Se G é um grafo plano conexo sem triângulos com n ≥ 3, então
m ≤ 2n− 4.
Prova:
Análoga, pois d(f) ≥ 4 e temos 2m ≥ 4F = 4(m+ 2− n).
E assim, 2m ≤ 4n− 8 ou m ≤ 2n− 4.
32
Caṕıtulo 5
COLORAÇÃO
Definição 5.1: Dado um grafo G = (V,E) e k ∈ N∗ um inteiro positivo. Uma k-
coloração de G é uma função f : v −→ (1, 2, 3, ..., k) tal que se uv ∈ E, então f(u) 6= f(v).
O número cromático χ(G) é o menor k tal que G tem um χ(G)− coloração.
Exemplo: m ≥ 1 se, somente se, χ(G) ≥ 2.
G Kn Bipartido Cn Wn Qn Pn
χ(G) n 2 2, se n for par 3, se n for par 1, n = 0 1, n = 1
3, se n for ı́mpar 4, se n for ı́mpar 2, n > 0 2, n > 1
33
Caṕıtulo 6
TRILHAS EULERIANAS E
CICLOS HAMILTONIANO
6.1 Trilha Euleriana
Definição 6.1: Dado um grafo G = (V, E). Uma Trilha Euleriana T em G é uma
trilha fechada que contém todas as arestas e todos os vértices de G.
Se existe uma trilha euleriana em G = (V, E), dizemos que G é Euleriano.
(a) Não é Euleriano
(b) É Euleriano. Certificado: (1, 2, 3, 4, 5, 3, 1)
Teorema 6.1 (Teorema de Euler): G é um grafo Euleriano se, somente se, G
é conexo e cada vértice de G tem grau par.
Prova:
Suponha que G é Euleriano. Então existe uma Trilha Euleriana T em G.
Como T contém todos os vértices de G, tem que ser conexo. Como T conta grau
1 para o vértice inicial v e conta grau 2 para um vértice intermediário u, quando entra e
quando sai de u. E, finalmente, conta 1 quando fecha em v. Temos que cada vértice tem
34
grau par.
Suponha que G é conexo e que cada vértice tem grau par.
Logo, cada vértice tem grau 2q com q > 1, se n ≥ 2.
Logo, um caminho aleatório sempre define um ciclo. Seja C
′
esse ciclo.
d(v1) ≥ 2
d(v2) ≥ 2
d(v3) ≥ 2
d(v4) ≥ 2
d(vn) ≥ 2
Olhe que G−E(C ′) = G1 tem todos os vértices com grau par tambem. Assim, se
recorre as componentes conexas de Gi, i ≥ 1, obtendo uma partição em ciclos das arestas
de G : (C1, C2, ..., CK).
Agora defino T uma trilha euleriana de G.
T ←− C1, remova C1 de C = (C1, C2, ..., CK).
Algorithm 1 Algoritmo para verificar se o Grafo é Euleriano
while (C 6= 0) do
tome Ci ∈ C tal que v ∈ T
⋂
Ci;
T ←− Percorra Ci a partir de v e percorra T ;
C ←− C − Ci;
end while
retorne T;
Grafo G usado de exemplo.
C1 = (a, b, j, a)
35
C2 = (d, e, i, d)
C3 = (i, h, e, f, i)
C4 = (b, c, d, b)
C5 = (h, g, f, h)
36
Trilha Ci C
- C1 C = (C1, C2, C3, C4, C5)
C1 C4 C = (C2, C3, C4, C5)
(a, b, j, a)
C1 + C4 C2 C = (C2, C3, C5)
(b, c, d, b, j, a, b)
C1 + C4 + C2 C3 C = (C3, C5)
(d, e, i, d, b, j, a, b, c, d)
C1 + C4 + C2 + C3 C5 C = (C5)
(i, h, e, f, i, d, b, j, a, b, c, d, e, i)
C1 + C4 + C2 + C3 + C5 - -
(h, f, g, h, e, f, i, d, b, j, a, b, c, d, e, i, h)
6.2 Ciclo Hamiltoniano
Definição 6.2: Dado um grafo G = (V,E) dizemos que G é Hamiltoniano se Cn
é um subgrafo de G e dizemos que Cn é um Ciclo Hamiltoniano de G, onde n = |V (G)|.
(a) G é Hamiltoniano com certificado (a, b, c,
d, e, a). (b) H não é Hamiltoniano.
37
Caṕıtulo 7
PROBLEMAS DE DECISÃO
Definição 7.1: Um problema de decisão é formado por uma entrada e uma per-
gunta cuja resposta é sim ou não.
Exemplo
• Ciclo Hamiltoniano
Instância: Grafo G = (V,E)
Pergunta: G é Hamiltoniano?
• Trilha Euleriana
Instância: Grafo G = (V,E)
Pergunta: G é Euleriano?
• Coloração
Instância: Grafo G = (V,E) e inteiro K
Pergunta: G é k-coloŕıvel?
• k-coloração
Instância: Grafo G = (V,E)
Pergunta: G é k-coloŕıvel?
• Conexidade
Instância: Grafo G = (V,E)
Pergunta: G é conexo?
38
Definição 7.2: Dado um algoritmo A. A complexidade de espaço de A corresponde
a uma função f(n), onde f(n) é o espaço em memória ocupado por uma entrada de
tamanho n. A textitcomplexidade de tempo de A corresponde ao tempo de execução g(n)
de uma instância de tamanho n de A.
Exemplo
Dado A, sendo o algoritmo DFS (Depth First Search), possui complexidade de
espaço (.pai + .cor + .f) igual a 3n + n2∗. Complexidade de tempo é de 2n porque para
cada aresta olhamos exatamente duas vezes quando visitamos cada um de seus vértices.
Logo, espaço(n2) = O(n2) e tempo(n2) = O(n2).
∗3n = .pai+ .cor + .f
n2 = matriz adjacência
Definição 7.3: Dado um problema π = (Instância, Pergunta), a complexidade
de espaço f(n) de π é a menor complexidade de espaço entre todos os algoritmos que
resolvem π para uma instância de tamanho n de π. A complexidade de tempo de π é
g(n) a menor complexidade de tempo entre todos os algoritmos que resolvem π para uma
instância de tamanho n de π. O algoritmo que realiza a complexidade (espaço/tempo) é
chamado de ótimo.
Exemplo
Nosso algoritmo que produz a ávore de DFS é ótimo em espaço (precisa armazenar
a entrada) e em tmepo (precisa ler a entrada) pois ambas são lineares.
7.1 Classe P
Definição 7.4: A Classe Polinomial (P ) consite dos problemas de decisão que
possuem um algoritmo com complexidade de tempo polinomial no tamanho da entrada.
Exemplo
DFS com algoritmo de certificado com complexidade linear.
Trilha Euleriana:
Algoritmo:
1o Verifique se é conexo, O(m)
39
2o Verifique se ∀v ∈ V , d(v) é par, O(m)
7.2 Classe NP
Definição 7.5: A Classe Não Deterministica de Tempo Polinomial (NP ) consite
dos problemas de decisão π que o problema de decisão é tempo polinomial no tamanho
da instância.
Entrada: Instância I de π e certificado c de I.
Pergunta: c é um certificado para a resposta sim de I?
Exemplo
Ciclo Hamiltoniano
(a) O certificado conhecido para a resposta Não
tem tamanho ω(n!).
(b) Certificado para a resposta Sim: (1, 2, 3, 4,
5, 1).
Ciclo Hamiltoniano está em NP , porque dado um grafo G = (V,E) (instância de
ciclo hamiltoniano - CH) e uma permutação (v1, v2, ..., vn, v1) de V (certificado) se projeta
um algoritmo que verifica se vivi+1 ∈ E que repsonda sim ou não, caso contrário.
40
O algoritmo roda em tempo O(n), portanto, em tempo polinomial no tamanho n2
da entrada. Logo, CH ∈ NP .
7.3 Satisfabilidade
Instância I = (U,C) onde U é um conjunto de variáveis lógicas e C é uma conjunção
(and) de disjunções (or) chamado de conjunção de cláusulas (or).
Pergunta
Existe uma atribuição de verdadef : U −→ (V, F ) para U que satisfaz C, ou seja,
cada cláusula tem pelo menos um literal (u ou ū) verdadeiro?
Quando a resposta é Sim dizemos que a instância I é satisfat́ıvel e quando a
resposta é Não, a instância I não é satisfat́ıvel.
Exemplo
I1 = (U1, C1) = ({u1, u2}, {(u1
∨
u2), (u1
∨
ū2), (ū1
∨
u2), (ū1
∨
ū2)})
I2 = (U2, C2) = ((u1, u2, u3), {(u1
∨
u2
∨
u3), (u1
∨
ū2
∨
ū3), (ū1
∨
ū2
∨
u3),
(ū1
∨
u2
∨
ū3)})
u2
V F
u1 V F F
F F F
Tabela 7.1: Tabela para I1
I2 é satisfat́ıvel com o certificado (u1, u2, u3) = (V, V, V )
7.4 Transformação Polinomial
Definição 7.6: Dados π1 e π2 dois problemas de decisão. Uma transformação
polinomial T : π1 −→ π2 e I1 −→ T (I1) = I2 de π em π2 leva uma instância qualquer
I1 de |pi1 em uma instância I2 = T (I1) de π2 em tmepo polinomial no tamanho |I1| de
I1 tal que I1 é uma instância sim se, somente se, I2 é uma instância sim. Neste caso,
escrevemos π1 ∝ π2
41
Exemplo
Clique Máxima (π1)
- Instância: Grafo G = (V,E), k ∈ N∗
- Pergunta: ∃ S ⊂ V, |S| ≥ k, S é uma clique de G?
Conjunto Independente (π2)
- Instância: Grafo G = (V,E), k ∈ N
- Pergunta: ∃ S ⊂ V, |S| ≥ k, S é um conjunto independente de G?
Considere T : π1 −→ π2 e (G, k) −→ (G, k).
Note que T roda em tempo polinomial O(n2), linear, no tamanho da entrada de
π1 (Ω(n
2))
Suponha que π1 tem respota sim em I1. Então existe S ⊂ V . Tal que S é uma
clique de G com |S| ≥ k.
Note que em Ḡ, o conjunto S é independente, logo π2 tem resposta sim em I2.
Suponha que π2 tem resposta sim em I2 = T (I1). Logo existe S ⊂ V , |S| ≥ k, tal
que S é um conjunto S é uma clique. Portanto, π1 tem resposta sim em I1. Logo, I1 é
uma instância sim de π1 se, somente se, I2 = T (I1) é uma instância sim de π2.
Teorema 7.1: Se π1 ∝ π2 ∝ π3, então π1 ∝ π3.
Prova
Veja que pela hipótese ∃ T1 : π1 −→ π2 e ∃ T2 : π2 −→ π3 onde dada I1 de π1, I2 =
42
T1(I1) é computada em tempo polinomial no tamanho de I1. Dada I2 de π2, I3 = T3 =
T2(I2) é computada em tempo polinomial de I2. Portanto T2(T1(I1)) = T2 ◦ T1(I1) = I3
é uma instância de I3 computada em tempo polinomial no tamanho de I1, e I1 é uma
instância sim de π1 se, somente se, I3 é uma instância sim de π3. Logo π1 ∝ π3.
7.5 NP-Completo
Definição 7.7: Dizemos que um problema de decisão π é NP-Completo se π ∈ NP ,
e ∀p ∈ NP , p ∝ π.
Teorema 7.2: Teorema de Cook (1971)
Em 1971, Steve Cook provou que SAT é NP-Completo.
Figura 7.2: Tese de Church
Teorema 7.3: Se π1 é NP-Completo, π2 ∈ NP e π1 ∝ π2, então π2 é NP-Completo.
43
Prova
Como π1 é NP-Completo, π1 ∈ NP e dado π ∈ NP existe T1 : π −→ π1, como
π1 ∝ π2 ∃ T2 : π1 −→ π2. Logo, pelo teorema anterior, ∀ π ∈ NP .
∃ T2 ◦ T1 : π1 −→ π2. Como, π ∈ NP , temos que π2 é NP-Completo.
Teorema 7.4: P ⊂ NP
Prova
Suponha que π ∈ P . Mostraremos que dada uma instância Iπ de π e um certificado
CI de Iπ, podemos checar se CI é um certificado para a resposta sim de Iπ em tempo
polinomial de Iπ. Podemos considerar Iπ = CI e o algoritmo A resolve π e se A(Iπ) = sim,
temos a verificação. Logo, π ∈ NP . E temos que P ⊂ NP .
Exemplo
3SAT ∝ Conjuntoindependente
Conjunto Independente
- Instância: Grafo G = (V,E) e inteiro k ∈ N
-Pergunta: ∃ S ⊂ V , |S| ≥ k e S é um conjunto independente de G?
7.6 3 Satisfabilidade (3SAT)
Instância: I = (U,C) de SAT tal que ∀ c ∈ C, |c| = 3.
Pergunta: I é satisfat́ıvel?
7.6.1 SAT ∝ 3SAT
Prova
Seja I = (U,C) uma instância de SAT , vamos construir I
′
= (U
′
, C
′
) uma instância
de 3SAT em tempo polinomial no tamanho de I tal que I é satisfat́ıvel se, somente se,
I
′
é satisfat́ıvel.
Considere T : SAT −→ 3SAT , I = (U,C) 7−→ I ′ = (U ′ , C ′).
Onde U
′ ←− U e C ′ ←− ∅.
Para cada c ∈ C com |c| = 3, C ′ ←− C ′ ∪ {c}
Para cada c ∈ C tal que
44
1- c = (u), adicione novos uc1, u
c
2 para U
′
= {U ′ ←− U ′ ∪ {wc1, wc2}} e (u, uc1, uc2),
(u, uc1, u
c
2), (u, u
c
1, u
c
2), (u, ū
c
1, u
c
2) para C
′
.
2- c = (u, v), adicione novo wc para U
′
e (u, v, wc), (u, v, w̄c) para C
′
.
Para cada c ∈ C com c = (u1, u2, u3, ..., uk) com k ≥ 4 adicione (u1, u2, wc1),
(wc1, u3, w
c
2), (w
c
2, u4, w
c
3), (w
c
3, u5, w
c
4), ..., (w
c
k−3, uk−1, uk) para C
′
e novos w
c
1, w
c
2, ..., w
c
k−3 para
U
′
.
Exemplo
I = (C,U) = ({u1, u2, u3, u4, u5}, {(u1, u2, u3, u4, u5), (u1, u2, u3, u4, u5), (u1),
(u1, u3), (u1, u2, u3)})
c1 = (u1, u2, u3, u4, u5)
c2 = (u1, u2, u3, u4, u5)
c3 = (u1)
c4 = (u1, u3
c5 = (u1, u2, u3)
I
′
= ({u1, u2, u3, u4, u5, w11, w12, w21, w22, w31, w32, w41}, {(u1, u2, w11), (w11, u3, w12),
(w12, u4, u5), (u1, u2, w
2
1), (w
2
1, u3, w
2
2), (w
2
2, u4, u5), (u1, w
3
1, w
3
2), (u1, w
3
1, w
3
2), (u1, w
3
1, w
3
2),
(u1, w31, w
3
2), (u1, u3, w
4
1), (u1, u3, w
4
1), (u1, u2, u3)})
c1 = {(u1, u2, w11), (w11, u3, w12), (w12, u4, u5)}
c2 = {(u1, u2, w21), (w21, u3, w22), (w22, u4, u5)}
c3 = {(u1, w31, w32), (u1, w31, w32), (u1, w31, w32), (u1, w31, w32)}
c4 = {(u1, u3, w41), (u1, u3, w41)}
c5 = {(u1, u2, u3)}
Adotando u1 V (verdadeiro), não é dif́ıcil ver que I é satisfat́ıvel se, somente se, I
′
é satisfat́ıvel.
Veja que I
′
é uma instância de 3SAT e que T consome tempo O(m · n) onde
m = |C| e n = |U |.
Logo, SAT ∝ 3SAT .
45
7.6.2 3SAT ∝ ConjuntoIndependente
Seja I = (U,C) = ({u1, u2, ..., un}, {c1, c2, ..., cn}) uma instância de 3SAT . Vamos
constrir (G = (V,E), k) uma instância de conjunto independente tal que I é satisfat́ıvel
se, somente se, G tem um conjunto independente S ⊂ V de tamanho |S| ≥ k, em tempo
polinomial no tamanho de I(m · n). Para cada u ∈ U vértice, u, ū para V e uū para E.
Para cada cláusla c = (x, y, z) ∈ C adicione cx, cy, cz para V , cxx, cyy, czz, cxcy, cxcz,
cycz para E.
Exemplo
I = (U,C) = ({u1, u2, u3}, {(u1, u2, u3), (u1, u2, u3), (u1, u2, u3), (u1, u2, u3)})
k = 3 + 4 = 7
u1 = u2 = u3 = V , ∃ S ⊂ V , S independente tal que |S| ≥ k, onde S =
{u1, u2, u3, 1u1 , 2u3 , 3u2 , 4u2}
Suponha que I é satisfat́ıvel. Seja ξ(xi) uma atribuição de verdade satisfat́ıvel.
Vamos dar uma receita para construir S com tamanho |S| = n + m. Tome os vértices
x ∈ ξ para S. Para cada cláusula Cj = (x, y, z) com o literal x = V . Tome jx par S.
Note que S é independente pois xjx ∈ E(xjx ∈ E).
Suponha que G tem um conjunto independente S com |S| ≥ n + m. Como
{u, u},u ∈ U é uma clique e {jx, jy, jz}, cj = (x, y, z) é uma clique. Sabemos que S
tem no máximo 1 vértice em cada clique {u, u}, {jx, jy, jz}. Como existe n cliques da
forma {u, u}, existem m cliques da forna {jx, jy, jz} e |S| ≥ n + m. Nossa receita é da
forma, fazendo a literal u = V , se, somente se, u ∈ S. Veja que cada cláusla cj = (x, y, z)
46
de C tem um literal x satisfeito correspondente ao vértice jx ∈ S, pois jxx ∈ E e assim
x ∈ S e x = V .
7.6.3 Conjunto Independente está em NP
Um certificado para o conjunto independente é um conjunto S ⊂ V com tamanho
|S| ≥ k.
Nosso algoritmo checa se S é, de fato, em tempo O(n2).
k = 4
Certificado: {a, f, c, h}
(n− 1) + (n+ 2) + ...+ 2 + 1 = (n−1)(1+(n−1))
2
(n− 1) + (n+ 2) + ...+ 2 + 1 = n(n−1)
2
Dáı, 3SAT (π1) ∝ Conjunto Independente (π2), Conj.Independente ∈ NP e
3SAT é NP-Completo. Pelo teorema anterior, Conj. Independente é NP − Completo.
	GRAFOS E SUBGRAFOS
	Notação O, , 
	Grafo
	Grau do Grafo
	Subgrafo
	Tipos de Grafos
	Isomorfismo
	Classes de Grafos
	Grafo Completo
	Grafo Bipartido
	Clique
	Grafo Complementar
	Grafo Caminho
	Grafo Ciclo
	Grafo Roda
	Grafo n-Cubo
	Grafo R-regular
	Grafo Trivial
	CONECTIVIDADE
	Componente Conexa
	Grafo Conexo
	Busca em Profundidade
	Corte de Vértices
	Corte de Arestas
	ÁRVORES E FLORESTAS
	Árvores
	Geodésia
	PLANARIDADE
	COLORAÇÃO
	TRILHAS EULERIANAS E CICLOS HAMILTONIANO
	Trilha Euleriana
	Ciclo Hamiltoniano
	PROBLEMAS DE DECISÃO
	Classe P
	Classe NP
	Satisfabilidade
	Transformação Polinomial
	NP-Completo
	3 Satisfabilidade (3SAT)
	SAT 3SAT
	3SAT Conjunto Independente
	ConjuntoIndependente está em NP