Atividade 4 UAM 2022 - GRA0808 INTRODUÇÃO À TEORIA DOS GRAFOS

Prévia do material em texto

Atividade 4 
Introdução à Teoria dos Grafos 
UAM 
2022 
nota 8 de 10 
 
1.O algoritmo de Bellman-Ford pode tratar de custos negativos em valores 
expressos nas arestas que ligam os vértices direcionados. A seguinte figura 
demonstra o custo de 1 para R$ 1.000,00 ao transporte de valores, com uma 
equipe composta por um motorista, um encarregado e dois seguranças: 
 
 
Fonte: Elaborada pelo autor. 
 
A respeito do algoritmo de Bellman-Ford, analise as afirmativas a seguir e 
assinale V 
para a(s) Verdadeira(s) e F para a(s) Falsa(s). 
 
I. ( ) Não é possível ter um ciclo negativo no grafo apresentado. 
II. ( ) No vetor inicial de um trajeto de A para D, teriam os valores: 0, 
Infinito, -2, Infinito, 3. 
III. ( ) Seria possível apenas ter um ciclo negativo no grafo. 
IV. ( ) No vetor inicial de um trajeto de C para D, teriam os valores: 
Infinito, 2, 0, Infinito, 3. 
 
Assinale a alternativa que apresenta a sequência correta. 
 
2. O algoritmo de Bellman-Ford possibilita que se encontre o menor custo 
de deslocamento entre dois vértices. Ao ter uma aplicação prática muito 
interessante, por exemplo, pode-se estimar os custos operacionais de 
determinada atividade, bem como o valor pago pelo serviço, a fim de 
estimar se o equilíbrio é orçamentário. Com base no exposto, assinale a 
alternativa que apresenta corretamente o funcionamento do algoritmo de 
Bellman-Ford. 
 
3. 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. 
 
4. Os algoritmos são sequências organizadas de execuções que são 
utilizadas para se garantir que determinados problemas sejam resolvidos. 
No algoritmo de Dijkstra, isso não é diferente, pois o objetivo é ter uma 
entrada de dados que permita fazer o processamento e, finalmente, que gere 
uma saída na qual foi programada. 
 
Considerando o exposto, sobre o algoritmo de Dijkstra, analise as 
afirmativas a seguir. 
 
I. O ponto inicial é utilizado na letra “P” com o valor 1. 
II. É atribuído o valor infinito para todos os vértices no início do algoritmo. 
III. Nas interações do algoritmo, o infinito deve ser substituído pelos custos 
negativos encontrados nos trajetos. 
IV. Se existir um valor de menor custo no cruzamento de determinado 
vértice e se o algoritmo encontrar um trajeto de menor custo entre dois 
vértices, então se sobrescreve o valor. 
 
Está correto o que se afirma em: 
 
5. O algoritmo de Kruskal foi desenvolvido pelo PhD Joseph Bernard 
Kruskal Júnior (1928 - 2010) para efetuar algumas análises em grafos. A 
forma de atuação desse algoritmo foi inovadora, pois, além de encontrar 
caminhos mínimos, ele propôs uma transformação no formato do grafo. A 
respeito do exposto, assinale a alternativa que apresenta corretamente o 
funcionamento do algoritmo de Kruskal. 
 
6. A estrutura organizada no algoritmo de Bellman-Ford possui três 
elementos que o compõem. Tal algoritmo determina como é organizado o 
fluxo de suas rotinas e isso permite um referencial teórico, possibilitando, 
assim, que uma pessoa com conhecimentos e habilidades possa fazer uma 
implementação por meio de uma linguagem de programação. 
 
Considerando o exposto, sobre o algoritmo de Bellman-Ford, analise as 
afirmativas a seguir. 
 
I. No processo de inicialização, ocorre a padronização dos valores que não 
possuem relacionamento. 
II. O relaxamento faz o cálculo do menor custo entre os vértices. 
III. O processo de ajuste faz a transformação dos valores negativos em 
positivos, quando se multiplica o valor negativo por - 1. 
IV. Na verificação, o algoritmo se certifica de que não esteja ocorrendo 
ciclos negativos. 
 
Está correto o que se afirma em: 
 
7. 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 algoritmo de Floyd busca fazer a eliminação de vértices para se obter 
uma estrutura mínima. 
 
Está correto o que se afirma em: 
 
 
8. 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. 
 
9. 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. 
 
 
10. Considere este caso hipotético:uma transportadora localizada na cidade 
“A” recebeu o mapa com os municípios nos quais deverá fazer as entregas 
diariamente. Para otimizar as rotas, o gerente operacional solicitou que, 
com base no algoritmo de Bellman-Ford, fosse desenvolvido um vetor com 
os custos de deslocamento da cidade “A” para a cidade “E”, conforme pode 
ser observado na seguinte figura: 
 
 
 
Fonte: Elaboradapelo autor. 
 
Referente ao exposto, assinale a alternativa com o vetor otimizado, 
correspondente ao grafo apresentado nessa figura.