Teoria dos Grafos

Prévia do material em texto

PROVA AV1 
	Curso: Ciências da computação
	
	Disciplina:
	Teoria dos Grafos
	Peso da Prova:
	8.0
	
	Código da Turma:
	ITA0790105NNA
	Data da Prova:
	28/04/2020
	Nome: ERICK SANTOS BARBOSA
	Matrícula: 28270670
	Nota:
	
	Conteúdos Aplicados na Prova
	Introdução a teoria dos grafos
Definição e notação. Subgrafos, grafos completos e bipartidos. Isomorfismo de grafos. Complemento de um grafo. Grafos rotulados. Matriz de adjacência. Caminhos e ciclos de grafos Hamiltonianos. Grafos conexos e desconexos.
	Questão 1–Objetiva(1,0)
	Observe o grafo direcionado abaixo:
e responda as seguintes perguntas:
I- Existe um caminho de comprimento 5 do nó 1 para o nó 4?
II- É possível acessar o nó 1 de algum outro nó?
III- Quais são os ciclos deste grafo?
Assinale a alternativa correta:
	
	a)I- Sim 1-a7-2-a2-2-a2-2-a3-3-a5-4. II – Não. III – O laço a2 e o caminho 3-a5-4-a6-3.
	
	b)I- Sim 1-a1-2-a2-2-a2-2-a3-3-a5-4. II – Sim. III – O laço a2 e o caminho 3-a5-4-a6-3.
	
	c) I- Sim 1-a1-2-a2-2-a2-2-a3-3-a5-4. II – Não. III – O laço a2 e o caminho 3-a5-4-a6-3.
	
	d) I- Sim 1-a7-4-a5-3-a3-2-a2-2-a2-4. II – Não. III – O laço a2 e o caminho 3-a5-4-a6-3.
	
	e) I- Não.II– Sim. III – O laço a6 e a2.
	
	Questão 2– Objetiva (1,0)
	Analise os grafos a seguir e verifique se são isomorfos:
Assinale a alternativa correta.
	
	a)São todos isomorfos: G, H e K.
	
	b)Os grafos apresentados não são isomorfos.
	
	c)Os grafos G e K são isomorfos.
	
	d)Os grafos G e H são isomorfos.
	
	e)Os grafos G e K são isomorfos.
	
	Questão 3 - Objetiva (1,0)
	3- A representação por conjuntos pode ser de grande utilidade para transpor o problema para um computador, a fim de criar algoritmos para sua solução. Nessa representação, a preocupação constitui em fazer um conjunto para cada série de vértice, em que os elementos desse conjunto são os vértices adjacentes.
´
Assinale a alternativa que representa conjuntos das séries de vértices: 
	
	a)A= {B, C, E, G}; C= {A, F, G}; B = {A, D}; D = {C, E}; E = {A, D, G}; F = {B, G} e G = {A, B, E, F}.
	
	b)A= {B, C, E, G}; B= {A, G}; C = {A, D}; D = {C, E}; E = {A, D, G}; F = {B, G} e G = {A, B, E, F}.
	
	c) A= {B, C, E, G}; B= {A, F, G}; C = {A, D}; D = {C, E}; E = {A, D}; F = {B, G} e G = {A, B, E, F}.
	
	d) A= {B, C, E, G}; B= {A, F, G}; C = {A, D}; D = {C, E}; E = {A, D, G}; F = {B, G} e G = {A, B, F}.
	
	e) G = {A, B, E, F}; A= {B, C, E, G}; E = {A, D, G}; B= {A, F, G}; C = {A, D}; D = {C, E} e F = {B, G}.
	
	Questão 4 - Objetiva (1,0)
	Sete pessoas (A, B, C, D, E, F e G) moram numa mesma cidade. Cada uma delas conhece as outras seis. São pares de pessoas que se gostam: AB, BC, CD, DE, EF, DG e DF. Qualquer outro par, que não estes, refere-se a duas pessoas que não se gostam. Há dentre essas sete pessoas, alguma que seja mais (menos) popular do que todas as outras? Quem? Monte a matriz de adjacência do grafo a seguir, que representa esta situação.
	
	
	Vertices
	A
	B
	C
	D
	E
	F
	G
	A
	0
	1
	0
	0
	0
	1
	0
	B
	1
	0
	1
	0
	0
	0
	0
	C
	0
	1
	0
	1
	0
	0
	0
	D
	0
	0
	1
	0
	1
	1
	1
	E
	0
	0
	0
	1
	0
	1
	0
	F
	1
	0
	0
	1
	1
	0
	0
	G
	0
	0
	0
	1
	0
	0
	0
	
	Questão 5– Objetiva(1,0)
	Qual dentre os grafos a seguir é eureliano e qual é semi-euleriano:
	
	
R: 
A - Semi-euleriano, porque e Um grafo que não contém um circuito euleriano mas contém um caminho eulerian.
B – Eureliano, Pois grafo que visita toda aresta exatamente uma vez.
	
	Questão 6– Objetiva(valor)
	Associe os grafos da primeira coluna com a informação da segunda coluna, classificando-os quanto a conectividade.
	
		
(a)
	(B) Fracamente conexa
	
(b)
	( A) GRAFO FORTEMENTE CONEXO
	
(c)
	( D ) GRAFO DESCONEXO
	
(d)
	(C ) GRAFO CONEXO
	
	Questão 7– Objetiva(2 pontos)
	Os grafos a seguir são bipartidos? Justifique
 (a) (b) 
	
	
A – Não e Bipartido, Porque o vértice f está conectado no vértices b e no vértices c sendo que cada um faz parte de um grupo diferente.
B - E BIRPARTIDO, Pois formam grupos independentes onde os vértices de cada grupos não se conectar diretamente.
	Questão 8– Objetiva (1 ponto)
	Classifique se os grafos a seguir são planares ou não planares. Justifique
	
	
	
	(a)
	(b)
	(c)
	
	
	
	(d)
	(e)
	
	
	
R: Os grafos não planares são A,B e C pois suas arestas se cruzam 
A- Não e planar 
B- Não e planar 
C- Não e planar 
R: Os grafos planares são os grafos D e E, pois suas arestas não se cruzam.
 D - E Planar 
 E - E Planar
	
Página 1 de 5
Página 5 de 5