Teoria do Grafos 1

Prévia do material em texto

UNIVERSIDADE ESTADUAL DO NORTE DO PARANÁ
UENP - CAMPUS LUIZ MENEGHEL
CENTRO CIÊNCIAS TECNOLOGICAS
CURSO SISTEMAS DE INFORMAÇÃO
MÁRCIA CRISTINA LEMES 401042
TEORIA DO GRAFOS
BANDEIRANTES–PR 
OUTUBRO/2018
UNIVERSIDADE ESTADUAL DO NORTE DO PARANÁ
UENP - CAMPUS LUIZ MENEGHEL
CENTRO CIÊNCIAS TECNOLOGICAS
CURSO SISTEMAS DE INFORMAÇÃO
MÁRCIA CRISTINA LEMES 401042
TEORIA DO GRAFOS
Trabalho apresentado à disciplina de Matemática Discreta, do curso Sistemas de Informação, da Universidade Estadual do Norte do Paraná, Campus Luiz Meneghel, como requisito parcial para obtenção de notas.
Professor: Luiz Fernando L. Nascimento
BANDEIRANTES–PR 
OUTUBRO/2018
Exercícios 1. Demostre através de grafos que se V(G) possui Δ(G) ímpar o grafo é sempre par.
 
V(G)= 4
E(G)= 5
Δ(G)= 3
Vetor de Graus= {3,3,2,2}
Exercícios 2. Mostre que em um grafo com δ(G) > 0 e |E(G)| < |V(G)| existem pelo menos dois vértices de grau 1.
V(G)= 4
E(G)= 3
Δ(G)= 2
Vetor de Graus= {2,2,1,1}
δ(G) > 0 e |E(G)| < |V(G)|
 3 < 4
Exercícios 3. Mostre que todo grafo com dois ou mais vértices tem pelo menos dois vértices de mesmo grau.
V(G)= 3
E(G)= 3
Δ(G)= 2
Vetor de Graus= {2,2,2}
Exercício 4 Construa a matriz de adjacência dos seguintes grafos e verifique se G e H são grafos isomorfos.
G H 
V(G)= 6
E(G)= 8
Δ(G)= 4
Vetor de Graus= {4,3,3,3,2,1}
V(G)= 6
E(G)= 8
Δ(G)= 4
Vetor de Graus= {4,3,3,3,2,1}
 
Matriz (G) 
Matriz (H)
Função Bijetora
	
	a
	b
	c
	d
	e
	f
	
	a
	0
	1
	0
	0
	0
	1
	2
	b
	1
	0
	1
	0
	0
	1
	3
	c
	0
	1
	0
	0
	1
	1
	3
	d
	0
	0
	0
	0
	1
	0
	1
	e
	0
	0
	1
	1
	0
	1
	3
	f
	1
	1
	1
	0
	1
	0
	4
	
	1
	2
	3
	4
	5
	6
	
	1
	0
	1
	1
	0
	1
	0
	3
	2
	1
	0
	0
	0
	1
	0
	2
	3
	1
	0
	0
	0
	1
	1
	3
	4
	0
	0
	0
	0
	0
	1
	1
	5
	1
	1
	1
	0
	0
	1
	4
	6
	0
	0
	1
	1
	1
	0
	3
 
	G
	→
	H
	a
	→
	2
	b
	→
	1
	c
	→
	3
	d
	→
	4
	e
	→
	6
	f
	→
	5
Exercício 5. Construa a matriz de adjacência dos seguintes grafos e verifique se G e H são grafos isomorfos.
G H
V(G)= 8
E(G)= 10
Δ(G)= 3
Vetor de Graus= {3,3,3,3,2,2,2,2}
Matriz (G)
V(G)= 8
E(G)= 10
Δ(G)= 3
Vetor de Graus= {3,3,3,3,2,2,2,2}
Matriz (H)
	
	a
	b
	c
	d
	e
	f
	g
	h
	
	a
	0
	1
	0
	1
	0
	0
	0
	0
	2
	b
	1
	0
	1
	0
	0
	1
	0
	0
	3
	c
	0
	1
	0
	1
	0
	0
	0
	0
	2
	d
	1
	0
	1
	0
	0
	0
	0
	1
	3
	e
	0
	0
	0
	0
	0
	1
	0
	1
	2
	f
	0
	1
	0
	0
	1
	0
	1
	0
	3
	g
	0
	0
	0
	0
	0
	1
	0
	1
	2
	h
	0
	0
	0
	1
	1
	0
	1
	0
	3
	
	s
	t
	u
	v
	w
	x
	y
	z
	
	s
	0
	1
	0
	1
	1
	0
	0
	0
	3
	t
	1
	0
	1
	0
	0
	0
	0
	0
	2
	u
	0
	1
	0
	1
	0
	0
	0
	0
	2
	v
	1
	0
	1
	0
	0
	0
	0
	1
	3
	w
	1
	0
	0
	0
	0
	1
	0
	1
	3
	x
	0
	0
	0
	0
	1
	0
	1
	0
	2
	y
	0
	0
	0
	0
	0
	1
	0
	1
	2
	z
	0
	0
	0
	1
	1
	0
	1
	0
	3
R: Os grafos (G) e (H) não são isomorfos mesmo apresentando na matriz de adjacência o mesmo vetor de grau, não podendo apresentar a função bijetora. 
Exercício 6. Verifique se os grafos G e H e K são isomorfos entre si.
G H K
V(G)= 6
E(G)= 7
Δ(G)= 3
Vetor de Graus= {3,3,3,2,2,1}
V(H)= 6
E(H)= 7
Δ(H)= 4
Vetor de Graus= {4,3,2,2,2,1}
V(K)= 6
E(K)= 7
Δ(K)= 3
Vetor de Graus= {3,3,3,2,2,1}
Matriz (G)
Matriz (H)
Matriz (K) 
	
	1
	2
	3
	4
	5
	6
	
	1
	0
	1
	0
	0
	0
	0
	1
	2
	1
	0
	1
	0
	1
	0
	3
	3
	0
	1
	0
	1
	1
	0
	3
	4
	0
	0
	1
	0
	0
	1
	2
	5
	0
	1
	1
	0
	0
	1
	3
	6
	0
	0
	0
	1
	1
	0
	2
	
	1
	2
	3
	4
	5
	6
	
	1
	0
	1
	0
	0
	1
	0
	2
	2
	1
	0
	1
	0
	1
	0
	3
	3
	0
	1
	0
	0
	0
	1
	2
	4
	0
	0
	0
	0
	1
	0
	1
	5
	1
	1
	0
	1
	0
	1
	4
	6
	0
	0
	1
	0
	1
	0
	2
	
	1
	2
	3
	4
	5
	6
	
	1
	0
	1
	0
	0
	1
	0
	2
	2
	1
	0
	1
	0
	1
	0
	3
	3
	0
	1
	0
	1
	0
	1
	3
	4
	0
	0
	1
	0
	0
	0
	1
	5
	1
	1
	0
	0
	0
	1
	3
	6
	0
	0
	1
	0
	1
	0
	2
R: Os grafos G, H e K não são isomorfos entre si pois apresentam diferentes vetores de grau. 
Exercício 7. Um químico deseja embarcar os produtos A, B, C, D, E, F, X usando o menor número de caixas. Alguns produtos não podem ser colocados numa mesma caixa porque reagem. Os produtos A, B, C, X reagem dois-a-dois; A reage com F e com D e vice-versa; E também reage com F e com D e vice-versa. 
Descreva o grafo que modela essa situação, mostre um diagrama desse grafo e use esse grafo para descobrir o menor número de caixas necessárias para embarcar os produtos com segurança.
Caixa 1= {A}
Caixa 2= {B, E}
Caixa 3= {D, X}
Caixa 4= {C, F}
R: O menor número de caixas necessárias para embarcar os produtos com segurança é 4 caixas segundo o grafo.
Exercício 8. Apresente o maior número de representações gráficas possíveis, utilizando 6 diferentes vértices e 5 arestas, tal que |V(G)=6| e |E(G)=5|. Descreva o vetor de graus de cada um deles.
Vetor de Graus= {2,2,2,2,1,1}
Vetor de Graus= {3,2,2,1,1,1}
Vetor de Graus= {3,2,2,1,1,1}
Vetor de Graus= {4,2,1,1,1,1}
Vetor de Graus= {5,1,1,1,1,1}
Exercício 9. Analise a matriz M1, apresente:
	
	A
	B
	C
	D
	E
	F
	G
	H
	A
	0
	1
	1
	0
	0
	0
	0
	0
	B
	1
	0
	1
	1
	0
	0
	0
	0
	C
	1
	1
	0
	1
	0
	0
	0
	0
	D
	0
	1
	1
	0
	1
	1
	0
	0
	E
	0
	0
	0
	1
	0
	1
	1
	1
	F
	0
	0
	0
	1
	1
	0
	1
	1
	G
	0
	0
	0
	0
	1
	1
	0
	1
	H
	0
	0
	0
	0
	1
	1
	1
	0
M1 = 
a) uma clique máxima.
b) O Vértice de Articulação, além disso e caso exista, informe a quantidade de componentes conexas que M1 terá se esse ponto de articulação for removido.
R: O vértice de articulação é o D, e se esse ponto de articulação for removido 2 será a quantidade de componentes conexas.
c) Denotado como dg(u) o grau de um vértice, apresente o vetor de graus (vet)= dg(u) ∴𝑢∈𝑉(𝐺)
R: Vetor de Graus da Matriz M1= {2, 3, 3, 4, 4,4,3,3}
Exercício 10. Analise a matriz M2 abaixo apresentado e responda as seguintes questões:
	
	A
	B
	C
	D
	E
	F
	G
	H
	A
	0
	1
	1
	0
	0
	0
	0
	0
	B
	1
	0
	1
	1
	0
	0
	0
	0
	C
	1
	1
	0
	1
	0
	0
	0
	0
	D
	0
	1
	1
	0
	1
	0
	0
	0
	E
	0
	0
	0
	1
	0
	1
	1
	1
	F
	0
	0
	0
	0
	1
	0
	1
	0
	G
	0
	0
	0
	0
	1
	1
	0
	1
	H
	0
	0
	0
	0
	1
	0
	1
	0
M2 = 
a) Construa o grafo de M2;
b) Em M2 aresta E(G) é dado por:
R: ?????
c) Denotado como dg(u) o grau de um vértice, apresente Δ(G) max{dg(u) ∴𝑢∈𝑉(𝐺)}
R: Grau Máximo é igual a 4 e está apresentando no Vértice E.
Exercício 11. Adaltina esperava 4 amigas Brandelina, Clodina, Dejaina e Edina para um lanche em sua casa. 
Enquanto esperava preparou os lanches: Bauru, Misto quente, Misto frio e X-salada. Brandelina gosta de Misto frio e de X-salada; Clodina de Bauru e X-salada; Dejaina gosta de Misto quente e Misto frio; Edina gosta de Bauru e Misto quente. 
Descreva o grafo que modela essa situação, mostre um diagrama desse grafo e use esse grafo para descobrir se é possível que cada amiga de Adaltina tenha o lanche que gosta.
	
	Bauru 
(E)
	Misto Quente (F)
	Misto Frio 
(G)
	X-Salada
(H)
	Brandelina (A)
	0
	0
	1
	1
	Clodina
(B)
	1
	00
	1
	Dejaina
(C)
	0
	1
	1
	0
	Edina
(D)
	1
	1
	0
	0