Aula13_grafos

Prévia do material em texto

Teoria dos Grafos
Valeriano A. de Oliveira
So
orro Rangel
Silvio A. de Araujo
Departamento de Matemáti
a Apli
ada
antunes�ibil
e.unesp.br, so
orro�ibil
e.unesp.br, saraujo�ibil
e.unesp.br
AULA 13
Grafos Planares
Preparado a partir do texto:
Rangel, So
orro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.
Grafos Planares
Grafos Planares
De�nição e Exemplos
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 3
Nesta aula queremos responder à seguinte questão: Dado um grafo G, é
possível en
ontrar uma representação grá�
a para o grafo tal que não
haja 
ruzamento de arestas?
Exemplo:
Considere por exemplo o grafo K4 representado gra�
amente nas �guras
�g1, �g2 e �g3.:
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 4
De�nição 1. Um grafo G é dito planar se puder ser representado
gra�
amente no plano de tal forma que não haja 
ruzamento de suas
arestas. Caso 
ontrário o grafo é dito não-planar. Usaremos o termo
grafo plano para uma representação planar de um grafo planar.
Exemplo: o grafo da �g 1 é um grafo planar, e o grafo das �g. 2 e �g.
3 são grafos planos.
Observação: Se existir uma representação do grafo em uma superfí
ie
sem que haja 
ruzamento de arestas, dizemos que existe uma imersão do
grafo na superfí
ie.
Como determinar então se um dado grafo é planar?
Grafos de Kuratowski
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 5
Existem dois grafos não planares que são muito importantes no estudo
de planaridade. Estes dois grafos são 
hamados Grafos de Kuratowski e
serão apresentados a seguir.
Teorema 2. O grafo K5 é um grafo não planar.
Prova - para mostrar este teorema usaremos uma metodologia que pode
ser bastante útil na obtenção de uma representação planar de um grafo
planar ou na prova de que tal representação não pode ser en
ontrada.
Vamos 
onsiderar o grafo K5. Sejam {v1, v2, v3, v4, v5} os 
in
o vérti
es
deste grafo. Como o grafo é 
ompleto, podemos en
ontrar um 
ir
uito
hamiltoniano em G. Seja por exemplo o seguinte 
ir
uito:
Grafos de Kuratowski
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
a) Vamos a
res
entar aresta (v2, v3)
b) A
res
entando a aresta (v2, v5)
) A
res
entando as arestas (v4, v1) e (v4, v3) observamos que não temos
es
olha e que é ne
essário in
lui-las externamente.
d) Ao tentarmos in
luir a última aresta do grafo (v5, v1) veri�
amos que
não é possível in
lui-la sem que haja 
ruzamento de arestas. Portanto o
grafo K5 é não planar.
Grafos de Kuratowski
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 7
Para apresentar o próximo grafo de Kuratowski vamos relembrar a
de�nição de grafo bipartido.
De�nição 3. Um grafo G(V,A) é bipartido quando o seu 
onjunto de
vérti
es, V, puder ser parti
ionado em dois 
onjuntos V1 e V2 tais que
toda aresta de G tem uma extremidade em V1 e outra em V2. Um grafo
bipartido 
ompleto possui uma aresta para 
ada par de vérti
es vi ∈ V 1
e vj ∈ V 2. Se n1 é o número de vérti
es em V1 e n2 é o número de
vérti
es em V2, o grafo bipartido 
ompleto é denotado por Kn1,n2.
Exemplos:
Grafos de Kuratowski
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 8
Teorema 4. O grafo K3,3 é um grafo não planar.
Prova: É possível demonstrar este teorema usando o mesmo argumento
da prova do teorema anterior.
Observação: O que estes dois grafos possuem em 
omum?
1. São grafos regulares
2. Os dois são não planares
3. A remoção de uma aresta ou um vérti
e torna o grafo planar
4. K5 é não planar 
om o menor número de vérti
es
5. K3,3 é não planar 
om o menor número de arestas
Fórmula de Euler
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 9
Observe que um grafo plano divide o plano em diversas regiões,
hamadas de fa
es.
Exemplo:
1. O grau de uma fa
e fi (d(fi)) é igual ao número de arestas 
ontida
na trilha fe
hada que a de�ne.
2. O número de fa
es (f) de um grafo planar é sempre o mesmo e
independe da representação planar obtida.
3. Como 
ada aresta de G perten
e a no máximo duas fa
es distintas,
ou esta in
luída duas vezes na trilha fe
hada que de�ne uma fa
e,
temos o seguinte resultado:
∑f
i=1 d(fi) = 2m
Fórmula de Euler
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 10
Exemplo:
O número de fa
es de um grafo também esta rela
ionado 
om o número
de arestas e vérti
es do grafo através do teorema abaixo.
Teorema 5. Se G é um grafo 
onexo planar 
om m arestas e n vérti
es,
então qualquer representação planar de G possui f = m− n+ 2 fa
es.
Fórmula de Euler
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 11
Exemplo: Quantas fa
es existem em grafo planar 
om 10 vérti
es, 
ada
um dos vérti
es 
om grau 3?
Ini
ialmente pre
isamos de�nir quantas arestas o grafo possui.∑
10
i=1 d(vi) = 2m⇒ m =
10∗3
2
= 15
Apli
ando a fórmula de Euler: f = m− n+ 2 = 15− 10 + 2 = 7,
sabemos que o grafo terá 7 fa
es.
Fórmula de Euler
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 12
Corolário1 - Seja G um grafo simples 
onexo planar 
om m arestas e n
vérti
es, então:m ≤ 3n− 6,m > 1
Prova: Observamos anteriormente que o grau de 
ada fa
e é de�nido
pelo número de arestas em uma trilha fe
hada. Em um grafo simples G
uma trilha fe
hada é 
omposta por pelo menos três arestas. Além disso,
ada aresta perten
e à no máximo duas fa
es de um grafo. Assim
podemos estabele
er a seguinte relação:
2m =
∑f
i=1 d(fi) ≥
∑f
i=1 3 = 3f
Logo 2m ≥ 3f ⇒ f ≤ 2m/3
Usando esta relação na fórmula de Euler temos:
m− n+ 2 ≤ 2m/3⇒ m ≤ 3n− 6
Fórmula de Euler
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 13
Observação: Observe que o grafo K5 não satisfaz o 
orolário 1 e
portanto não é planar. O grafo K3,3 satisfaz o 
orolário porém não é
planar. Assim temos uma 
ondição ne
essária mas não su�
iente.
Como fazer então para determinar se um dado grafo é planar? O
algoritmo de redução a seguir pode auxiliar nesta tarefa.
De�nição 6. Duas arestas estão em série se elas possuem exatamente
um vérti
e em 
omum e este vérti
e tem grau dois.
De�nição 7. A fusão de duas arestas in
identes em um vérti
e vj ,
(vi, vj) e (vj, vk), é feita eliminando as duas arestas e 
riando a aresta
(vi, vk).
Pro
edimento 1 - Pro
edimento
de redução
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 14
1. Passo 1 - Determine as 
omponentes do grafo. G = G1, G2, ..., Gk.
Teste 
ada 
omponente Gi do grafo.
2. Passo 2 - Remova todos os loops
3. Passo 3 - Elimine as arestas paralelas, deixando apenas uma aresta
entre 
ada par de vérti
es.
4. Passo 4 - Elimine os vérti
es de grau dois através da fusão de duas
arestas. (Arestas em série não afetam a planaridade).
5. Repita os passos 3 e 4 enquanto for possível.
Exemplo - Vamos apli
ar o pro
edimento de redução ao seguinte grafo:
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 15
De uma maneira geral, após apli
ar o pro
edimento 1 a 
ada uma das
omponentes Gi, qual será o grafo reduzido, Hi?
Teorema 8. O grafo reduzido Hi é:
a) uma aresta; ou
b) um grafo 
ompleto 
om 4 vérti
es; ou
) um grafo simples 
om n ≥ 5 e m ≥ 7.
Se todos os grafos reduzidos Hi satis�zerem os itens a) ou b), o grafo G
é planar. Caso 
ontrário é ne
essário veri�
ar se m ≤ 3n− 6. Se o grafo
reduzido não satisfaz esta inequação então o grafo G é não planar. Se a
inequação for satisfeita, é ne
essário fazer testes adi
ionais.
Observação: Usando o Pro
edimento 1 e o Teorema anterior podemosidenti�
ar 
laramente a planaridade de um grafo para 
asos onde o grafo
tem menos que 5 vérti
es e menos que 7 arestas.
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 16
Para grafos 
om n ≥ 5 e m ≥ 7 e que satisfaçam a 
ondição do
Corolário 1 pre
isamos de outros resultados.
De�nição 9. A subdivisão de aresta (v, w) de um grafo G é uma
operação que transforma a aresta (v, w) em um 
aminho através da
adição de vérti
es de grau 2.
Exemplo:
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 17
De�nição 10. Subdivisão de um grafo - Um grafo G2 é uma subdivisão
de um grafo G1 quando G2 puder ser obtido de G1 através de uma
sequên
ia de divisões das arestas de G1.
Exemplo:
Dizemos que G2 é uma 
on�guração de G1.
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 18
O Teorema a seguir foi demonstrado pela primeira vez pelo matemáti
o
polonês Kuratowski em 1930.
Teorema 11. Um grafo G é planar se e somente se não 
ontém um
subgrafo que é uma 
on�guração do grafo K5 ou do grafo K3,3.
Exemplo: Vamos veri�
ar se o grafo abaixo é planar.
Podemos apli
ar o pro
edimento de redução pois o grafo 
ontém vérti
es
de grau 2. Vamos então eliminar o vérti
e h através da fusão das arestas
(a, h) e (h, g). O grafo resultante é:
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 19
Vamos veri�
ar o Corolário 1 (m ≤ 3n− 6⇒ 12 ≤ 3(7)− 6 = 15).
Como o grafo satisfaz o 
orolário não podemos a�rmar nada. Vamos
então apli
ar o pro
edimento de 
onstrução de 
ir
uitos e tentar obter
um representação planar para este grafo.
Vamos determinar o 
ir
uito mais longo neste grafo:
Seja o 
ir
uito: {a, b, c, d, e, f, g, a}:
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 20
1- Vamos ini
iar o pro
edimento inserindo, por exemplo, a aresta (a, d).
2- Para inserir a aresta (b, e) temos apenas uma opção, inserir fora do
ir
uito.
3- Observe agora que a aresta (
,g) não pode ser desenhada fora, ou
dentro do 
ir
uito. Assim podemos dizer que o grafo dado não é planar.
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 21
Vamos agora en
ontrar uma 
on�guração do K3,3 ou do K5 no grafo G.
De a
ordo 
om o teorema se o grafo é não planar devemos en
ontrar
uma. Como fazer?
Para identi�
ar a 
on�guração do K3,3 vamos eliminar do subgrafo G
′
os
vérti
es de grau 2, através da fusão das arestas (g, f) e (f, e).
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 22
O grafo reduzido G′′ é o K3,3. Basta tomar V 1 = {a, c, e} e
V 2 = {b, d, g}. O subgrafo de G que é uma 
on�guração do K3,3 é
então:
Grafos Planares
Teoria dos Grafos (Antunes Rangel&Araujo) � 23
Algoritmos para veri�
ar se uma dado grafo é planar e em 
aso positivo
exibir uma representação planar do grafo:
1) Algoritmo de Hop
roft e Tarjan em 'Teoria do grafos - Algoritmos',
Antonio Luiz Furtado, Livros Té
ni
os e 
ientí�
os editora, 1973.
2) Algoritmo de Demou
ron et al. em: 'Algorithmi
 Graph Theory', J.A.
Ma
hugh, Prenti
e Hall, 1990.
3) Algoritmos Lineares para Teste de Planaridade em Gra-
fos, Edna Ayako Hoshino. Dissertação de Mestrado, UFMS, disponível em:
http://www.fa
om.ufms.br/gestor/titan.php?target=openFile&�leId=537
(última visita: 08/01/2015).
4) Teste de planaridade e seus prin
ipais algoritmos, José Coelho de Pina,
IME-USP. disponível em: http://www.ime.usp.br/ 
oelho/sh/introp.html
(ultima visita: 08/01/2015).
	Grafos Planares
	Definição e Exemplos
	
	Grafos de Kuratowski
	Grafos de Kuratowski
	Grafos de Kuratowski
	Grafos de Kuratowski
	Fórmula de Euler
	Fórmula de Euler
	Fórmula de Euler
	Fórmula de Euler
	Fórmula de Euler
	Procedimento 1 - Procedimento de redução