3 ATIVIDADE - Resolução [ Grafos ]

Prévia do material em texto

LISTA DE EXERCÍCIOS – A3 – Introdução à Teoria dos Grafos 
Aluno(a):___________________Wilson_Vitor________________________________
01. Represente os grafos abaixo utilizando matrizes de adjacências :
	
a) b)
		
c) d)
02. 
	
	a
	b
	c
	d
	e
	f
	a
	0
	1
	0
	0
	0
	1
	b
	1
	0
	1
	1
	0
	1
	c
	0
	1
	0
	1
	0
	1
	d
	0
	1
	1
	0
	1
	1
	e
	0
	0
	0
	1
	0
	1
	f
	1
	1
	1
	1
	1
	0
01. (a)
(b) 
	
	1
	2
	3
	4
	5
	1
	0
	1
	1
	1
	1
	2
	x
	0
	x
	x
	x
	3
	x
	1
	0
	1
	1
	4
	x
	x
	x
	0
	x
	5
	x
	x
	x
	x
	0
(c) 
	
	1
	2
	3
	4
	5
	1
	0
	10
	50
	65
	x
	2
	x
	0
	30
	x
	4
	3
	x
	x
	0
	20
	44
	4
	x
	70
	x
	0
	23
	5
	6
	x
	x
	x
	0
 
(d)
	
	1
	2
	3
	4
	5
	1
	0
	100
	4
	x
	30
	2
	x
	0
	x
	65
	x
	3
	x
	6
	0
	x
	9
	4
	25
	x
	23
	0
	x
	5
	x
	x
	x
	20
	0
02. (a) O joguinho pode ser formulado assim, abaixo. Cada quadrado tem sua posição correspondente.
(b) 
A solução mínima pro jogo descrito no enunciado é 21, e equivale à distância mínima entre o nó 1 e o 12. A andada representa assim: