A4 - Introdução à Teoria dos Grafos

Prévia do material em texto

Questão 1 
Incorreto 
Atingiu 0,00 de 1,00 
Marcar questão 
Texto da questão 
Uma equipe de desenvolvimento utiliza aplicações computacionais para o desenvolvimento e a 
análise de grafos. O seu último desenvolvimento foi feito em uma aplicação com o algoritmo de 
Kruskal. Para a validação dos resultados obtidos, utilizou-se o grafo apresentado na seguinte figura: 
 
 
 
Fonte: Elaborada pelo autor. 
 
Nesse sentido, assinale a alternativa que apresenta o grafo com a árvore mínima geradora correta 
quando for aplicado o algoritmo de Kruskal. 
 
a. 
O grafo correto possui arestas entre os vértices de A para B, de B para F, de F para C, de C para D, 
de D para E e, finalmente, de E para A. 
Sua resposta está incorreta. A alternativa está incorreta. O simples fato da eliminação de arestas 
internas de um grafo não elimina o circuito formado. Embora o grafo não forme um ciclo, mas a 
aresta de menor custo entre B para F, com custo 1 foi eliminada, o grafo está incorreto, porque 
foi eliminado o menor custo. Dessa forma, o grafo não apresenta circuito, porém foram utilizados 
os vértices de maior custo. Assim, o grafo está incorreto, uma vez que fecha um ciclo com o 
trajeto A - B - C - D - A. 
 
b. 
O grafo correto possui arestas entre os vértice de E para D, de D para A, de A para B, de D para C 
e, finalmente, de C para F. 
 
c. 
O grafo correto possui arestas entre os vértice de A para D, de E para A, de A para B, de B para C 
e, finalmente, de B para F. 
 
d. 
O grafo correto possui arestas entre os vértice de E para A, de A para B, de A para D, de B para C, 
de C para D e, finalmente, de B para F. 
 
e. 
O grafo correto possui arestas entre os vértice de E para D, de D para A, de A para B, de B para C 
e, finalmente, de C para F. 
Feedback 
A resposta correta é: O grafo correto possui arestas entre os vértice de A para D, de E para A, de 
A para B, de B para C e, finalmente, de B para F. 
Questão 2 
Correto 
Atingiu 1,00 de 1,00 
Marcar questão 
Texto da questão 
Os algoritmos são rotinas organizadas de algumas execuções que obedecem a alguns padrões da 
lógica para a resolução de alguns problemas. Esses algoritmos podem possuir implementações 
computacionais quando necessário ou apenas organizar os processos de determinadas atividades. 
 
A respeito do algoritmo de Kruskal, analise as afirmativas a seguir e assinale V para a(s) 
Verdadeira(s) e F para a(s) Falsa(s). 
 
I. O primeiro passo do algoritmo de Kruskal visa selecionar a aresta externa de menor custo. 
II. O segundo passo do algoritmo de Kruskal visa determinar a aresta selecionada com o custo 
menor. 
III. O terceiro passo do algoritmo de Kruskal visa considerar a árvore mínima geradora como A. 
IV. O quarto passo do algoritmo de Kruskal visa acrescentar α em A se for formado um ciclo. 
 
Assinale a alternativa que apresenta a sequência correta. 
 
a. 
V, V, F, F. 
 
b. 
F, F, V, V. 
 
c. 
V, F, F, F. 
Resposta correta. A alternativa está correta, pois a afirmativa I é verdadeira, já que, na segunda 
etapa, ocorre a seleção das arestas de menor custo, considerando que já encontrou, 
anteriormente, o vértice inicial e atribuiu o valor zero. Assim, na etapa posterior, o algoritmo visa 
encontrar o vértice não processado que possui o valor infinito. 
 
d. 
F, F, F, F. 
 
e. 
F, V, F, V. 
Feedback 
A resposta correta é: V, F, F, F. 
Questão 3 
Correto 
Atingiu 1,00 de 1,00 
Marcar questão 
Texto da questão 
Um grupo de arqueólogos encontrou um mapa no qual é possível indicar uma grande construção 
subterrânea. Porém, após diversas análises, foi cogitada a possibilidade de desvendar o trajeto, caso 
seja aplicado o algoritmo de Kruskal. Esse mapa é demonstrado na seguinte figura: 
 
 
 
Fonte: Elaborada pelo autor. 
 
A partir do exposto, analise as asserções a seguir e a relação proposta entre elas. 
 
I. Não é possível aplicar o algoritmo de Kruskal no grafo. 
Pois: 
II. A quantidade de vértices no grafo é par, por isso, sempre será fechado um ciclo. 
 
A seguir, assinale a alternativa correta. 
 
 
a. 
A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa. 
 
b. 
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
 
c. 
As asserções I e II são proposições falsas. 
 
Resposta correta. A alternativa está correta, poisa asserção I é uma proposição falsa, já que é 
possível aplicar o algoritmo de Kruskal no grafo. A asserção II também é uma proposição falsa, 
pois o fato de o grafo ter quantidade par ou ímpar não impede de se utilizar o algoritmo de 
Kruskal para se ter uma árvore geradora mínima. 
 
d. 
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. 
 
e. 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. 
Feedback 
A resposta correta é: As asserções I e II são proposições falsas. 
 
Questão 4 
Correto 
Atingiu 1,00 de 1,00 
Marcar questão 
Texto da questão 
Uma das etapas encontradas no algoritmo de Bellman-Ford está no processo de verificação de ciclos 
negativos, importante para se garantir que os resultados gerados sejam condizentes com as análises 
proporcionadas pelos algoritmos implementáveis na teoria dos grafos. 
 
A partir do exposto, analise as asserções a seguir e a relação proposta entre elas. 
 
I. O primeiro processo do algoritmo de Bellman-Ford faz a padronização dos valores de vértices não 
relacionados. 
Pois: 
II. O processo que precede a verificação é o relaxamento, o qual é responsável por buscar o menor 
caminho de menor custo entre os vértices. 
 
A seguir, assinale a alternativa correta. 
 
 
a. 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. 
Resposta correta. A alternativa está correta, poisa asserção I é uma proposição verdadeira, já que 
a primeira etapa dos processos do algoritmo visa à padronização dos vértices não relacionados. 
A asserção II também é uma proposição verdadeira e não justifica a I, pois se expõe que o 
processo de relaxamento busca o menor custo e isso está correto, porém, em cada asserção, é 
explicado o funcionamento, mas ambas não se justificam. 
 
b. 
A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa. 
 
c. 
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. 
 
d. 
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
 
e. 
As asserções I e II são proposições falsas. 
Feedback 
A resposta correta é: As asserções I e II são proposições verdadeiras, mas a II não é uma 
justificativa correta da I. 
Questão 5 
Correto 
Atingiu 1,00 de 1,00 
Marcar questão 
Texto da questão 
O mapeamento dos custos de deslocamento é uma variável de extrema importância, principalmente 
quando estamos falando a respeito do planejamento da otimização de rotas. O grafo representado na 
seguinte figura demonstra o custo de deslocamento entre algumas cidades: 
 
 
Fonte: Elaborada pelo autor. 
 
Com base no algoritmo de Floyd-Warshall, os valores foram expressos na matriz evidenciada no 
seguinte quadro: 
 A B C D 
A 0 4 2 6 
B ∞ 0 3 4 
C ∞ ∞ 0 ∞ 
D ∞ ∞ 5 0 
 
Fonte: Elaborado pelo autor. 
 
A partir do exposto, analise as asserções a seguir e a relação proposta entre elas. 
 
I. A matriz utilizou seis símbolos de ∞. 
Pois: 
II. São utilizados para expressar que não existe uma aresta que liga um vértice ao outro naquela 
direção. 
 
A seguir, assinale a alternativa correta. 
 
 
a. 
As asserções I e II são proposições falsas. 
 
b. 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. 
 
c. 
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
 
d. 
A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa. 
 
e. 
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. 
Respostacorreta. A alternativa está correta, poisa asserção I é uma proposição verdadeira, uma 
vez que o grafo não possui ligação com o direcionamento entre os vértices: B para A, C para A, C 
para B, C para D, D para A e D para B, totalizando seis. A asserção II também é uma proposição 
verdadeira e justifica a I, pois expressa que não existe um relacionamento naquela direção. 
Feedback 
A resposta correta é: As asserções I e II são proposições verdadeiras, e a II é uma justificativa 
correta da I. 
Questão 6 
Correto 
Atingiu 1,00 de 1,00 
Marcar questão 
Texto da questão 
O algoritmo de Dijkstra é semelhante ao algoritmo de Bellman-Ford, pois, entre outras coisas, pode 
calcular o trajeto mínimo entre dois vértices de determinado grafo valorado. Porém, em Dijkstra, 
possui diferenças em relação ao algoritmo de Bellman-Ford. Nesse sentido, assinale a alternativa que 
apresenta corretamente outra diferença nos algoritmos de Dijkstra e de Bellman-Ford. 
 
 
a. 
O algoritmo de Dijkstra não utiliza arestas direcionadas. 
 
b. 
O algoritmo de Dijkstra não utiliza vértices impares. 
 
c. 
O algoritmo de Dijkstra não utiliza uma sequência para a execução de sua rotina. 
 
d. 
O algoritmo de Dijkstra não efetua cálculos com valores negativos. 
Resposta correta. A alternativa está correta, pois o algoritmo de Dijkstra não consegue efetuar 
uma tratativa quando, no relacionamento entre os vértices por meio das arestas, são 
encontrados valores negativos. Para esse tipo de grafo com valores negativos, o indicado é 
utilizar o algoritmo de Bellman-Ford. 
 
e. 
O algoritmo de Dijkstra não utiliza vértices pares. 
Feedback 
A resposta correta é: O algoritmo de Dijkstra não efetua cálculos com valores negativos. 
Questão 7 
Correto 
Atingiu 1,00 de 1,00 
Marcar questão 
Texto da questão 
O mapeamento dos custos de deslocamento entre algumas cidades foi representado na seguinte 
figura: 
 
 
Fonte: Elaborada pelo autor. 
 
 
Considerando um trajeto de A para E e com base no algoritmo de Dijkstra, os valores foram 
expressos na matriz evidenciada no seguinte quadro: 
 
 Passo 1 Passo 2 Passo 3 Passo 4 Passo 5 
A (0, A) (0, A) *** *** *** 
B (1, A) (1, A) *** *** *** 
C (4, A) (4, A) 
D ∞ (5, B) 
E ∞ (3, B) 
 
Fonte: Elaborado pelo autor. 
 
A partir do exposto, analise as asserções a seguir e a relação proposta entre elas. 
 
I. Foram fixados os valores na linha A (0, A) e na linha B (1, A). 
Pois: 
II. Não haverá custo de A para A pela ausência de laço, não sendo encontrado um custo menor de B 
para C. 
 
A seguir, assinale a alternativa correta. 
 
 
a. 
A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa. 
Resposta correta. A alternativa está correta, poisa asserção I é uma proposição verdadeira, 
porque foram fixados os valores encontrados nos trajetos de A para A como 0 (zero), uma vez 
que não existe laço no vértice A. Já o custo entre os vértices A para B foi fixado em 1, pois, se for 
feito qualquer outro trajeto entre os dois pontos, o custo será maior. 
 
b. 
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. 
 
c. 
As asserções I e II são proposições falsas. 
 
 
d. 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. 
 
e. 
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
Feedback 
A resposta correta é: A asserção I é uma proposição verdadeira, e a asserção II é uma proposição 
falsa. 
Questão 8 
Correto 
Atingiu 1,00 de 1,00 
Marcar questão 
Texto da questão 
Uma viagem em família requer planejamento e estratégias, a fim de se ter um deslocamento com 
segurança, com o menor custo e, se possível, evitar longos congestionamentos que acabam por 
aumentar o tempo gasto entre dois pontos, os quais, muitas vezes, não são tão distantes. Todas 
essas análises estão diretamente ligadas à teoria dos grafos e, intuitivamente, busca-se o caminho 
com menor custo entre dois pontos. O algoritmo de Floyd é uma das técnicas responsáveis por 
encontrar tais informações. 
 
A respeito do algoritmo de Floyd-Warshall, analise as afirmativas a seguir e assinale V 
para a(s) Verdadeira(s) e F para a(s) Falsa(s). 
 
I. Se o vértice inicial do grafo é dado por “i” e o vértice final é dado por “n”, então os vértices 
intermediários são compreendidos entre “i” e “n -1”. 
II. Os vértices intermediários são um conjunto de um grafo G. 
III. Na matriz utilizada pelo algoritmo de Floyd, apresenta-se i = j, então o valor será 0 (zero). 
IV. Se i for diferente de j e apresentar a aresta, então o menor custo deverá substituir o valor na 
matriz, no algoritmo de Floyd. 
 
Assinale a alternativa que apresenta a sequência correta. 
 
a. 
F, F, V, V. 
Resposta correta. A alternativa está correta. A afirmativa III é verdadeira, pois, se não fosse 
atribuído o valor 0 (zero), seria possível ter laços no grafo, não sendo o objetivo de análise do 
algoritmo de Floyd. A afirmativa IV também é verdadeira, pois, basicamente, o algoritmo de Floyd 
busca trajetos entre os vértices de menor custo e, quando encontrado, esse valor é substituído 
pelo atual valor da matriz. 
 
b. 
V, V, V, V. 
 
 
 
c. 
F, V, F, V. 
 
d. 
V, V, F, F. 
 
e. 
F, F, F, F. 
Feedback 
A resposta correta é: F, F, V, V. 
Questão 9 
Correto 
Atingiu 1,00 de 1,00 
Marcar questão 
Texto da questão 
Os algoritmos são ferramentas da lógica computacional que permitem organizar rotinas, a fim de se 
planejar o sequenciamento de ações sobre determinado conjunto de valores. Quanto à sua aplicação 
na teoria dos grafos, é essencial saber identificar as características do grafo, para, após isso, ser 
utilizada a análise algorítmica. Um exemplo de grafo, passível de análise, pode ser observado na 
seguinte figura: 
 
 
 
Fonte: Elaborada pelo autor. 
 
A respeito do algoritmo de Dijkstra, analise as afirmativas a seguir e assinale V para a(s) 
Verdadeira(s) e F para a(s) Falsa(s). 
 
I. São necessários 8 passos para se obter um trajeto otimizado de S para qualquer outro vértice. 
II. Não é possível utilizar o algoritmo de Dijkstra na análise do grafo, pois ele está desenvolvido 
em árvore. 
III. É preciso fazer todos os trajetos nas subárvores e seus respectivos custos. Somente após 
isso, deve-se passar para as subárvores adjacentes. 
IV. Não é possível utilizar o algoritmo de Dijkstra na análise do grafo, pois existem custos 
negativos entre os vértices. 
 
Assinale a alternativa que apresenta a sequência correta. 
 
a. 
V, V, V, V. 
 
b. 
F, F, V, V. 
 
c. 
V, V, F, F. 
 
d. 
F, V, F, V. 
Resposta correta. A alternativa está correta, pois a afirmativa II é verdadeira, já que o algoritmo 
de Dijkstra faz análise em grafos com circuito, mas não em grafos em árvore. O algoritmo de 
Dijkstra não efetua cálculos quando são utilizados pesos negativos nas arestas entre os vértices 
do grafo, o que torna a afirmativa IV verdadeira. 
 
e. 
F, F, F, F. 
Feedback 
A resposta correta é: F, V, F, V. 
Questão 10 
Correto 
Atingiu 1,00 de 1,00 
Marcar questão 
Texto da questão 
Leia o excerto a seguir. 
 
“[...] um exemplo clássico do uso de algoritmos é a tabela que se consulta atlas e guias rodoviários, 
que dão as distâncias de várias cidades. Atualmente, fazemos esse tipo de consulta, porém com a 
utilização de programas computacionais que efetuam os cálculos.” 
 
 
CORMEN, J. Desmistificando Algoritmos. Rio de Janeiro: Elsevier, 2017. p. 93. 
 
Considerando o exposto, sobre o algoritmo de Floyd-Warshall, analise as afirmativas a seguir. 
 
I. O algoritmo de Floyd utiliza a recursividade para determinar o menor custo, porém não poderia ser 
utilizado para a consulta de guias rodoviários. 
II. O algoritmo de Floyd resolve os problemas menores e, gradativamente, vai resolvendo problemas 
mais complexos. 
III. O algoritmo de Floyd utiliza valores negativos nas arestas entre os vértices. 
IV. O algoritmode Floyd busca fazer a eliminação de vértices para se obter uma estrutura mínima. 
 
Está correto o que se afirma em: 
 
a. 
II, apenas. 
Resposta correta. A alternativa está correta. A afirmativa I está incorreta, pois o algoritmo de 
Floyd não utiliza recursividade, ainda que poderia ser utilizado para a consulta de guias 
rodoviários. A afirmativa II está correta, visto que o algoritmo de Floyd é modular, ou seja, resolve 
os problemas menores inicialmente e vai aumentando aos poucos. A afirmativa III está incorreta, 
pois o algoritmo de Floyd não utiliza valores negativos para cálculo. A afirmativa IV está incorreta, 
porque não minimiza os grafos, tratando-se de outras técnicas. 
 
b. 
II e III, apenas. 
 
c. 
II, III e IV, apenas. 
 
d. 
I, II e IV, apenas. 
 
 
e. 
III, apenas. 
Feedback 
A resposta correta é: II, apenas.