AV1 Grafos 8 de 10 pontos

Prévia do material em texto

1. 
 
 
Um grafo G=(V,E) é uma entidade matemática abstrata. Analise as afirmativas abaixo e marque a 
opção correta. 
I - O conjunto V é o conjunto de nós do grafo e E o conjunto de arestas que 
são compostas por pares de nós de V . 
Esta característica faz do grafo 
II - Um modelo perfeito para redes de qualquer tipo. 
 (Ref.: 202009442189) 
 
 
I e II são verdadeiros, porém não há relação entre I e II. 
 
 
I é verdadeiro e II é falsa. 
 
 
I é falsa e II é verdadeira. 
 
 
Ambas são falsas. 
 
 
I e II são verdadeiros e II justifica I. 
 
 
 
 
1 ponto 
 
2. 
 
 
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} 
 (Ref.: 202011018592) 
 
 
7 
 
 
6 
 
 
2 
 
 
4 
 
 
5 
 
 
 
 
1 ponto 
 
3. 
 
 
O percurso em largura é caracterizado por definir um critério na seleção das arestas não visitadas. 
O critério é: 
 (Ref.: 202010920943) 
 
 
Organizar as arestas em um conjunto. 
 
 
Organizar as arestas em uma fila. 
 
 
Organizar as arestas em uma pilha. 
 
 
Organizar as arestas em uma árvore. 
 
 
Organizar as arestas em um deque. 
 
 
 
 
1 ponto 
 
4. 
 
 
O algoritmo genérico de percurso divide o conjunto de V de vértices e E de arestas em 
dois subconjuntos disjuntos V' e V'' ; E' e E'' , correspondendo aos vértices ou arestas 
marcados e não marcados respectivamente. No passo geral, o algoritmo seleciona uma aresta não 
marcada, marca esta aresta, isto é, insere em E'' e, caso um dos vértices ao qual a aresta é incidente 
não for marcado, marca este vértice V''. Com base nisso, podemos afirmar: 
 (Ref.: 202010920976) 
 
 
O percurso pode não existir. 
 
 
Podem existir diversos percursos diferentes. 
 
 
O percurso fica indefinido. 
 
 
O percurso só existe se o grafo for conexo. 
 
 
O percurso é único. 
 
 
 
 
1 ponto 
 
5. 
 
 
Acerca da teoria dos grafos e seus conceitos básicos, qual a principal diferença entre um grafo e 
um digrafo? 
 (Ref.: 202009442190) 
 
 
Não há diferença, os termos são sinônimos. 
 
 
Os grafos são obrigatoriamente conexos e os digrafos não. 
 
 
Os digrafos permitem multiplicidade de arestas, isto é, várias arestas interligando os mesmos 
nós. 
 
 
Os digrafos não possuem ciclos. 
 
 
A diferença reside no conjunto E, isto é, de arestas. Nos grafos os elementos de E são pares de 
vértices e nos digrafos são pares ordenados de vértices. 
 
 
 
 
1 ponto 
 
6. 
 
Em relação ao percurso Euleriano, analise as afirmativas abaixo: 
I - Deve visitar obrigatoriamente todas as arestas do grafo uma única vez. 
 
II - Deve visitar obrigatoriamente todos os nós do grafo uma única vez. 
III - Pode ser determinado em tempo polinomial. 
 (Ref.: 202009442044) 
 
 
Somente III é verdadeira. 
 
 
Somente II é verdadeira. 
 
 
Somente I é verdadeira. 
 
 
Somente I e III são verdadeiras. 
 
 
Somente II e III são verdadeiras. 
 
 
 
 
1 ponto 
 
7. 
 
 
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 afirmar. EXCETO. 
 
 (Ref.: 202011015118) 
 
 
Leonhard Euler é considerado o pai da Teoria dos grafos, o matemático nasceu na Basileia-
Suíça no ano de 1707. 
 
 
Muito usados para modelar problemas em computação -> ênfase em aspectos computacionais 
 
 
Modelos matemáticos para resolver problemas práticos do dia a dia. 
 
 
Grafos: conceito introduzido por Euler, em 1736 ¿ Problema da Ponte de Könisberg 
 
 
O modelo foi introduzido na computação pela primeira vez nos anos 90. 
 
 
 
 
1 ponto 
 
8. 
 
 
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. 
 (Ref.: 202011015216) 
 
 
O número de colunas é igual ao numero de linhas 
 
 
Pode retornar uma matriz boleana; 
 
 
A matriz resultante é heterogênia 
 
 
Numa matriz booleana a diagonal principal é sempre composta por zero. 
 
 
Gera uma matriz N x N 
 
 
 
 
1 ponto 
 
9. 
 
 
Muitas vezes nos referimos a um grafo e exibimos um diagrama. É muito comum isto acontecer. 
Dizemos que o diagrama é uma representação plana do grafo quando as arestas, que são 
representadas por linhas, não se cruzam em nenhum ponto. Analise as afirmativas abaixo: 
Todo grafo admite uma representação plana. 
A representação plana de um grafo pode não ser única. 
É fácil desenhar a representação plana de K5, isto é, o grafo completo com 5 vértices. 
 (Ref.: 202009442042) 
 
 
Somente II é verdadeira. 
 
 
Todas são verdadeiras. 
 
 
Somente III é verdadeira. 
 
 
Somente I é verdadeira. 
 
 
Todas são falsas. 
 
 
 
 
1 ponto 
 
10. 
 
 
A teoria dos grafos apresenta diversas formas de representa-los desde grafos simples, orientados, 
conexo ou desconexos, direcionados ou não direcionados. Em relação ao tipo de grafo, o grafo em 
que existe um caminho entre qualquer par de vértices é dito? 
 
 (Ref.: 202011018515) 
 
 
Biparido 
 
 
Completo 
 
 
Desconexo 
 
 
Conexo 
 
 
Simples 
 
 
 
VERIFICAR E ENCAMINHAR 
 
 
https://simulado.estacio.br/provas_pni_em_casa_linear.asp