Aula01_ 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 1
Introdução, Con
eitos Ini
iais, Isomorfismo
Preparado a partir do texto:
Rangel, So
orro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.
Introdução
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
O que é um Grafo?
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 3
Um grafo G é 
onstituído de um 
onjunto V não-vazio de objetos,
hamados vérti
es (ou nós), e um 
onjunto A de pares não ordenados de
elementos de V , 
hamados de arestas. Denotamos o grafo por G(V,A)
ou simplesmente G.
Exemplo 1.
a) V = {v1, v2, v3, v4, v5} e
A = {(v1, v2), (v1, v3), (v2, v4), (v3, v4), (v4, v5), (v1, v2), (v2, v2)}.
b) V = {1, 2, 3, 4, 5} e A = {(1, 2), (2, 3), (1, 4), (1, 3)}.
) V = {a, b, c} e A = { }.
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 4
Os grafos podem ser representados através de um diagrama onde os
vérti
es são representados por pontos e 
ada aresta é representada por
uma linha ligando os pares de vérti
es que a de�nem. A representação
grá�
a dos grafos dados no Exemplo 1 são dadas na �gura a seguir.
v
1
v
2
v
3 v4
v
5
1
2
3
4
5
a
b c
Em algumas apli
ações, as arestas são de�nidas 
omo pares ordenados
de vérti
es. Neste 
aso dizemos que o grafo é orientado ou dire
ionado e
o 
hamamos de Digrafo.
O que é um Digrafo?
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 5
Um grafo orientado (ou dire
ionado) G(V,A) é 
onstituído p�r um
onjunto V não-vazio de objetos, 
hamados vérti
es (ou nós), e um
onjunto A de pares ordenados de elementos de V , 
hamados de arestas
ou ar
os.
Os digrafos podem ser desenhados através de um diagrama onde os
vérti
es são representados por pontos e 
ada aresta (vi, vj) é
representada por uma linha ligando vi a vj 
om uma seta apontando
para vj.
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 6
Exemplo 2. V = {v1, v2, v3, v4, v5} e
A = {(v1, v2), (v1, v3), (v2, v4), (v3, v4), (v4, v5), (v1, v2), (v2, v2)}.
v
1
v
2
v
3
v
4
v
5
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 7
Um mesmo grafo, ou um mesmo digrafo, pode ter diferentes
representações grá�
as. Ver �gura abaixo:
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
Figura 1: Um mesmo grafo 
om diferentes representações grá�
as.
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 8
O que é que 
ara
teriza um grafo? O 
onjunto de vérti
es e de arestas,
ou seja, um 
onjunto de objetos (vérti
es) e a relação entre estes objetos
(arestas). Durante o 
urso, a distinção entre grafos e digrafos será feita
de a
ordo 
om o tópi
o estudado.
Assim, podemos dizer que a Teoria de Grafos é um ramo da
matemáti
a que estuda as relações entre os objetos de um
determinado 
onjunto.
Objetivos do 
urso:
■ Desenvolver a Teoria dos Grafos
■ Modelar problemas de forma a serem resolvidos utilizando 
on
eitos
e resultados de Teoria dos Grafos.
Apli
ações
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
O problema das pontes de Königsberg
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 10
Na 
idade de Konigsberg (Hoje Kaliningrado - Rússia) sete pontes
ruzam o rio Pregel estabele
endo ligações entre uma ilha e o 
ontinente
onforme a �gura abaixo:
Será que é possível fazer um passeio pela 
idade, 
omeçando e
terminando no mesmo lugar e passando p�r 
ada uma das pontes apenas
uma vez?
Problema do Carteiro Chinês
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 11
Determinar a rota de menor 
usto que saia da agên
ia 
entral dos
orreios, passe p�r todas as ruas de um determinado bairro, e volte a
origem.
O Problema de ligações de eletri
idade, gás e água
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 12
Considerem que existam 3 
asas e que 
ada uma delas pre
isa ser ligada
ao sistema de eletri
idade, gás e água. Por questões de segurança,
deseja-se saber se é possível fazer as ligações sem que haja 
ruzamento
das tubulações. Represente este problema através de um grafo.
O problema do 
aixeiro viajante
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 13
Um viajante ne
essita visitar um 
erto número de 
idades. É possível
determinar um roteiro de viagem tal que 
ada 
idade seja visitada apenas
uma vez?
Considere, por exemplo, um tre
ho do mapa rodoviário que in
lui a
idade de São José do Rio Preto (SJRP). Suponha que o viajante tenha
que sair de SJRP e visitar as 
idades de Marilia, Araçatuba, Bauru e São
Carlos. Represente este problema através de um grafo.
É possível en
ontrar uma rota que passe p�r todas as 
idades apenas
uma vez e retorne a 
idade SJRP? Caso existam mais de uma rota, qual
é a rota que minimiza o tre
ho viajado?
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 14
Exer
í
ios
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 15
1. Considere o problema de ligações de eletri
idade, gás e água.
Desenhe grafos representando as seguintes situações:
(a) 2 
asas e 3 serviços;
(b) 4 
asas e 4 serviços (água, eletri
idade, gás e telefone).
2. Des
reva 10 situações (jogos, atividades, problemas, et
.) que
podem ser representadas através de grafos ou digrafos. Explique o
que os vérti
es e as arestas estão representando. Sugestão de leitura:
Capitulo 1, seção 1.3 de [2℄ e Capítulo3 e 5 de [3℄.
3. O Problema da de
antação - Considere três vasos, A, B, e C 
om
apa
idades de 8, 5 e 3 litros respe
tivamente. O vaso A está 
heio e
os vasos B e C estão vazios. Divida o líquido que está no vaso A em
duas quantidades iguais. Represente o problema usando um grafo.
Bibliogra�a
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 16
1. N. Deo, Graph Theory with appli
ations to engineering and
omputer s
ien
e, 1974.
2. R.K. Ahuja, T. Magnanti e J.B. Orlin, Network Flows, Prenti
e Hall,
1993.
3. R.J.Wilson, Introdu
tion to graph theory, 3rd ed. The pitman Press
Ltda, Bath, 1985.
Con
eitos Ini
iais
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 18
De�nição 3. Seja G(V,A) um grafo. Dada uma aresta
a = (vi, vj) ∈ A dizemos que:
a) vi e vj são os extremos da aresta a.
b) A aresta a é dita ser in
idente nos vérti
es vi e vj.
) vi e vj são 
hamados de vérti
es adja
entes.
d) Se vi = vj a aresta a é 
hamada de loop ou laço.
e) Se existir uma aresta f = (vk, vl) tal que vk = vi e vj = vl, as
arestas a e f são 
hamadas de arestas paralelas. Grafos que 
ontém
arestas paralelas são 
hamados de Multi-grafos.
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 19
Exer
í
io Analise o grafo da �gura abaixo e exiba exemplos dos termos
itados na De�nição 3.
v
1v
2
v
3 v4
v
5
Figura 2:
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 20
De�nição 4. Um grafo é simples se não possui loops e/ou arestas
paralelas.
De�nição 5. Duas arestas são ditas adja
entes se elas in
idem no
mesmo vérti
e.
De�nição 6. O grau de um vérti
e v, d(v), em um grafo sem loops é
determinado pelo número de arestas in
identes em v. Caso haja loops,
estas arestas 
ontribuem 
om grau 2.
Exemplo 7. Determine os graus dos vérti
es do grafo dado na �gura
a
ima.
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 21
De�nição 8. Dizemos que:
a) Um vérti
e v é isolado se d(v) = 0.
b) Um vérti
e v é pendente se d(v) = 1.
) Um grafo G(V,A) é dito nulo se o 
onjunto de arestas é vazio.
d) Um grafo G(V,A) é dito regular se todos os seus vérti
es tem o
mesmo grau.
e) Um grafo G(V,A) é dito 
ompleto se existe uma aresta entre 
ada
par vérti
es. É representado por Kn, onde n é o número de vérti
es do
grafo.
f) Um grafo G(V,A) é dito valorado (ou rede) se são atribuídos
valores para os vérti
es e/ou arestas.
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 22
Figura 3: Grafos regular e nulo.
Figura 4: Grafos 
ompletos K4 e K5.
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 23
Proposição 9. Dado um grafo G 
om n vérti
es, v1, v2, . . . , vn e m
arestas, temos que:
n∑
i=1
d(vi) = 2m. (1)
Porque este resultado é válido? Observe que 
ada aresta 
ontribui 
om 2
graus para 
ada vérti
e. Assim a soma dos graus de todos os vérti
es é
igual a duas vezes o número de arestas.
Teorema 10. O número de vérti
es de grau ímpar em um grafo é
sempre par.
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 24
Demonstração. Vamos dividir a soma em (1) em duas par
elas. Os
vérti
es 
om grau par e os vérti
es 
om grau ímpar:
n∑
i=1
d(vi) =
∑
grau par
d(vi) +
∑
grau ímpar
d(vi). (2)
O lado esquerdo da equação (2) é par (pela Proposição 9). A primeira
par
ela do lado direito também é par, pois é a soma de números pares.
Para que a igualdade seja válida, a segunda par
ela em (2) também deve
ser par: ∑
grau ímpar
d(vi) é par. (3)
Como 
ada par
ela d(vi) em (3) é ímpar temos que ter um número par
de elementos para que a soma seja um número par (lembre-se que um
número ímpar é da forma 2k + 1).
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 25
Exer
í
ios:
1. Desenhe todos os grafos simples 
om 1,2, 3 e 4 vérti
es.
2. Represente os seguintes 
ompostos orgâni
os através de grafos: (a)
CH4; (b) C2H2; (
) N2O3.
3. Convença a vo
ê mesmo que o grau máximo de um vérti
e em um
grafo simples 
om n vérti
es é n− 1.
Isomor�smo
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 27
Nós já vimos que é possível representar um mesmo grafo de várias
maneiras. Como determinar se dois grafos são equivalentes, ou seja se
possuem as mesmas propriedades? Isto é 
omo determinar se dois grafos
são isomorfos? A palavra isomor�smo vem do grego iso (mesmo) e
morfo (mesma forma).
De�nição 11. Dizemos que dois grafos G e H são isomorfos se existir
uma 
orrespondên
ia biunívo
a entre os vérti
es de G e os vérti
es de H
que preserve a relação de adja
ên
ia entre vérti
es e arestas. Em outras
palavras, é possível obter o grafo H a partir de uma nova rotulação dos
vérti
es de G.
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 28
Exemplo 12. Considere os grafos da Figura 5. Construir a
orrespondên
ia biunívo
a.
a
b
c
d e
1 2
3 4
5
Figura 5:
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 29
Apli
ações: O estudo de isomor�smo pode ser apli
ado na des
oberta
de novos 
ompostos orgâni
os. Os quími
os mantém uma tabela de
ompostos orgâni
os. Cada vez que um novo 
omposto é des
oberto é
ne
essário determinar se ele é isomorfo a algum 
omposto já existente.
Determinar se dois grafos são isomorfos não é uma tarefa muito simples.
De fato a determinação de isomor�smos é uma área de intensa pesquisa
em teoria de grafos. Condições ne
essárias para que dois grafos sejam
isomorfos são fa
ilmente determinadas através da De�nição 11:
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 29
Apli
ações: O estudo de isomor�smo pode ser apli
ado na des
oberta
de novos 
ompostos orgâni
os. Os quími
os mantém uma tabela de
ompostos orgâni
os. Cada vez que um novo 
omposto é des
oberto é
ne
essário determinar se ele é isomorfo a algum 
omposto já existente.
Determinar se dois grafos são isomorfos não é uma tarefa muito simples.
De fato a determinação de isomor�smos é uma área de intensa pesquisa
em teoria de grafos. Condições ne
essárias para que dois grafos sejam
isomorfos são fa
ilmente determinadas através da De�nição 11:
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 30
Condições ne
essárias para Isomor�smos entre os dois grafos G
e H:
1. G e H devem possuir o mesmo número de vérti
es;
2. G e H devem possuir o mesmo número de arestas;
3. G e H devem possuir o mesmo número de vérti
es 
om um
determinado grau.
As 
ondições 1,2 e 3 a
ima são su�
ientes?
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 31
Vamos veri�
ar este fato através do seguinte exemplo:
G: H:
x
u
v
y
w
Observe que G e H:
a) possuem mesmo número de vérti
es;
b) possuem mesmo números de arestas;
) possuem: 3 vérti
es 
om grau 1; 2 vérti
es 
om grau 
om grau 2; 1
vérti
e 
om grau 3. Porém...
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 32
Porém estes dois grafos não são isomorfos! Não é possível fazer uma
orrespondên
ia biunívo
a entre os vérti
es que preserve a relação de
adja
ên
ia entre vérti
es e arestas. Observe que é ne
essário asso
iar o
vérti
e x do grafo G ao vérti
e y do grafo H, pois não existe nenhum
outro vérti
e 
om grau 3 em H. Mas o vérti
e y é adja
ente a apenas
um vérti
e de grau 1, enquanto que x em G é adja
ente a dois vérti
es
de grau 1. Portanto, não é possível fazer uma 
orrespondên
ia biunívo
a
entre os vérti
es de G e H que preserve a relação de adja
ên
ia entre
vérti
es e arestas.
No 
apítulo 11, seção 11.7 de [N. Deo, Graph Theory with appli
ations
to engineering and 
omputer s
ien
e, 1974℄ é feita uma dis
ussão a
respeito de algoritmos para se determinar isomor�smos entre grafos.
Introdução Apli
ações Con
eitos Ini
iais Isomor�smo
Teoria dos Grafos (Antunes Rangel&Araujo) � 33
Exer
í
ios:
1. Desenhe todos os grafos simples, não isomorfos 
om 1,2, 3 e 4
vérti
es.
2. Veri�que se os grafos abaixo são isomorfos:
(a)
G: H:
(b)
G: H:
	Introdução
	O que é um Grafo?
	
	O que é um Digrafo?
	
	
	
	Aplicações
	O problema das pontes de Königsberg
	Problema do Carteiro Chinês
	O Problema de ligações de eletricidade, gás e água
	O problema do caixeiro viajante
	
	Exercícios
	Bibliografia
	Conceitos Iniciais
	
	
	
	
	
	
	
	
	Isomorfismo