AVA2 - Algoritmos em Grafos

Prévia do material em texto

Disc.: ALGORITMOS EM GRAFOS
	Turma: 3001
	
	Gabarito após: 16/11/2023
	
	 1.
	Ref.: 7692963
	
	
	A teoria dos grafos apresenta diversas formas de representa-los e a matriz de adjacência é uma delas, outra forma é a lista de Adjacência, que também podem ser implementadas a partir de uma Grafo simples ou direcionado (orientado). Assinale a alternativa correta em relação a Matriz de Adjacência, EXCETO.
OBS: A correta seria “A matriz resultante é heterogenia”
		
	
	Gera uma matriz N x N
	
	Numa matriz booleana a diagonal principal é sempre composta por zero.
	
	O número de colunas é igual ao numero de linhas
	
	A matriz resultante é heterogênia
	
	Pode retornar uma matriz boleana;
	Respondido em 04/11/2023 18:09:40
	
	
	 2.
	Ref.: 7746723
	
	
	Um grafo é uma estrutura de dados consistida em um conjunto de nós (ou vértices) e um conjunto de arcos (ou arestas). O grafo em que os arcos possuem um número ou peso associados a eles, é chamado de grafo:
 
		
	
	Adjacente.
	
	Incidente.
	
	Ponderado.
	
	Predecessor.
	
	Orientado.
	Respondido em 04/11/2023 18:21:35
	
	
	 3.
	Ref.: 7740275
	
	
	Analise o grafo abaixo e relacione com conceito a seguir:
Grafo G = v6,v5,v4,v3,v2,v1,v6
Um _________________ em um grafo conexo G é definido com um caminho simples fechado em que cada vértice de G é visitado uma única vez,com 
exceção do nó inicial. Assinale a alternativa que corresponde a definição.
		
	
	Caminho em ciclo
 
	
	Ciclo Hamiltoneano
 
	
	Ciclo euleriano
 
	
	Caminho Euleriano
 
	
	Caminho conexo
	
OBS: A resposta correta Seria “Ciclo Hamiltoneano”
Respondido em 04/11/2023 21:29:04
	
	
	 4.
	Ref.: 7740276
	
	
	Observe o grafo a seguir e com base na matriz de adjacência assinale a alternativa que representa os elementos da diagonal principal.
		
	
	1,1,0,0,1
 
	
	0,1,0,0,0
 
	
	0,1,0,0,1
 
	
	0,1,1,0,0
	
	0,0,0,0,0
 
	Respondido em 04/11/2023 18:13:04
	
	
	 5.
	Ref.: 7740138
	
	
	A representação de grafos se apresentam de diversas formas, quanto ao tipo conexo ou desconexo, regulares, simudouro e fonte. Essas classificações são com base em características e regras. Observe a definição a seguir e assinale a alternativa correta quanto a classificação do grafo. 
"Diz-se que um grafo é ______________________, se e somente se, todos os seus vértices tiverem o mesmo grau."
		
	
	Conexo
 
	
	Regular
	
	Sumidouro
 
	
	Desconexo
	
	Fonte
 
	Respondido em 04/11/2023 18:35:36
	
	
	 6.
	Ref.: 7746430
	
	
	Sobre o conceito de percorrer grafo em busca de caminhos mínimos, um dos grafos mais aplicado neste processo é o algoritmo Dijkstra, que soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido. Após a execução deste algoritmo, qual o peso final do vértice C?
		
	
	7
	
	6
	
	5
	
	10
	
	9
	Respondido em 04/11/2023 18:12:52
	
	
	 7.
	Ref.: 7598864
	
	
	O algoritmo de Prim e Kruskal tem uma característica que é sempre buscar o passo mais promissor a cada iteração. Este tipo de algoritmo é chamado:
		
	
	Adaptativo.
	
	Faminto.
	
	Bulímico.
	
	Dietético.
	
	Guloso.
	Respondido em 04/11/2023 21:54:48
	
	
	 8.
	Ref.: 6119867
	
	
	Analise as afirmativas abaixo quanto ao valor verdade.
I - A complexidade computacional do algoritmo que calcula o ciclo Euleriano é Om.
II - No ciclo euleriano temos que visitar todas as arestas uma única vez, consequentemente todos os nós também, por isso, pode-se afirmar que todo grafo Euleriano é Hamiltoniano.
III - No grafo Hamiltoniano temos que visitar todos os nós uma única vez, por esta razão, pode-se afirmar que, em consequência, temos que visitar todas as arestas do grafo. Assim, todo grafo Hamiltoniano é Euleriano.
		
	
	Todas são verdadeiras.
	
	Somente I e II são verdadeiras.
	
	Somente II e III são verdadeiras.
	
	Somente I é verdadeira.
	
	Somente I e III são verdadeiras.
	Respondido em 04/11/2023 21:36:49
	
	
	 9.
	Ref.: 7739967
	
	
	Determine os valores de n (número de vertices), m (número de arestas), e f (número de faces) considerando que o grafo seja planar. Desenhe, se possível, um grafo simples, conexo e planar que satisfaça a propriedade
		
	
	6 vértices e 14 arestas
	
	5 faces 10 arestas
	
	13 arestas e 9 faces
	
	7 vértices e 13 arestas
	
	6 vértices e 8 faces
	Respondido em 04/11/2023 21:39:49
	
	
	 10.
	Ref.: 7746633
	
	
	Quantas faces existem em um grafo planar com 10 vértices e grau 3?
		
	
	10
	
	14
	
	7
	
	8
	
	15
	Respondido em 04/11/2023 18:14:46