Simulado 2

Prévia do material em texto

Disc.: ALGORITMOS EM GRAFOS Turma: 1001
Aluno: DÉBORA CRISTINA FIGUEIREDO DE ALMEIDA Matr.: 202202798398
Prof.: SIMONE INGRID MONTEIRO GAMA Nota:  0,70 pts.
7023879957 04/06/2024 16:09:51
 1. Ref.: 7692865
Os problemas resolvidos com uma solução computacional, de alguma forma, faz uso da matemática para chegar até a solução. A
exemplo disso temos a teoria dos grafos que é uma área de conhecimento da matemática que aplicada a computação consegue
resolver problemas de natureza complexa, até então, não resolvidos. Quanto a teoria dos grafos é correto a�rmar. EXCETO.
 
Leonhard Euler é considerado o pai da Teoria dos grafos, o matemático nasceu na Basileia-Suíça no ano de 1707.
 O modelo foi introduzido na computação pela primeira vez nos anos 90. 
Muito usados para modelar problemas em computação -> ênfase em aspectos computacionais
Grafos: conceito introduzido por Euler, em 1736 ¿ Problema da Ponte de Könisberg
Modelos matemáticos para resolver problemas práticos do dia a dia. 
Respondido em 04/06/2024 16:36:37
 2. 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.
Gera uma matriz N x N
 A matriz resultante é heterogênia
O número de colunas é igual ao numero de linhas
Numa matriz booleana a diagonal principal é sempre composta por zero.
Pode retornar uma matriz boleana;
Respondido em 04/06/2024 16:12:10
 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 é de�nido 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 de�nição.
 
Ciclo Hamiltoneano
 
Caminho conexo
Caminho Euleriano
 
Caminho em ciclo
 
Ciclo euleriano
 
Respondido em 04/06/2024 16:19:03
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7692865.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7692865.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7692963.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7692963.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7740275.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7740275.');
 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.
0,1,0,0,0
 
 
0,0,0,0,0
 
0,1,0,0,1
 
1,1,0,0,1
 
 0,1,1,0,0
Respondido em 04/06/2024 16:20:30
 5. Ref.: 7740138
A representação de grafos se apresentam de diversas formas, quanto ao tipo conexo ou desconexo, regulares, simudouro e fonte.
Essas classi�cações são com base em características e regras. Observe a de�nição a seguir e assinale a alternativa correta
quanto a classi�cação do grafo. 
"Diz-se que um grafo é ______________________, se e somente se, todos os seus vértices tiverem o mesmo grau."
Desconexo
Sumidouro
 
 Regular
Conexo
 
Fonte
 
Respondido em 04/06/2024 16:12:41
 6. Ref.: 7696339
Observe o conjunto de arestas a seguir e assinale a alternativa que representa na matriz de adjacência NÃO booleana, a soma
dos elementos da diagonal.
V= (1,2,3,4)
A = {(1,1)=2,(1,2)=0,(1,3)=1,(1,4)=3,(2,1)=0,(2,2)=4,(2,3)=3,(2,4)=1,(3,1)=0,(3,2)=0,(3,3)=0,(3,4)=1,(4,1)=1,(4,2)=1,(4,3)=0,
(4,4)=1}
 7
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7740276.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7740276.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7740138.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7740138.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7696339.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7696339.');
 6
5
4
2
Respondido em 04/06/2024 16:16:07
 7. Ref.: 6119792
Analise as a�rmativas abaixo:
I - O problema de determinar o ciclo hamiltoniano de um grafo é NP-completo.
 
Isto quer dizer que:
 
II - Não se conhece algoritmo que resolva o problema em tempo polinomial.
I é falsa e II é verdadeira.
I e II são verdadeiras, porém II não justi�ca I.
Ambas são falsas.
I é verdadeira e II é falsa.
 I e II são verdadeiras e II justi�ca I.
Respondido em 04/06/2024 16:34:56
 8. Ref.: 7598690
O percurso em largura é caracterizado por de�nir um critério na seleção das arestas não visitadas. O critério é:
Organizar as arestas em uma pilha.
Organizar as arestas em um conjunto.
Organizar as arestas em uma árvore.
 Organizar as arestas em uma �la.
Organizar as arestas em um deque.
Respondido em 04/06/2024 16:32:39
 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
5 faces 10 arestas
 7 vértices e 13 arestas
13 arestas e 9 faces
 6 vértices e 8 faces
6 vértices e 14 arestas
Respondido em 04/06/2024 16:24:18
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6119792.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6119792.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7598690.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7598690.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7739967.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7739967.');
 10. Ref.: 7700664
Suponha que um grafo simples, planar, conectado possui 24 vértices, todos os vértice de grau 3. Em quantas regiões podemos
fazer a representação planar deste grafo?
12
24
10
36
 14
Respondido em 04/06/2024 16:23:12
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7700664.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 7700664.');