Atividade 4 INTRODUÇÃO A TEORIA DOS GRAFOS

Prévia do material em texto

Atividade 4
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.
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:
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:
Considere este caso hipotético: um desenvolvedor está buscando uma solução de deslocamento para o transporte de alimentos por uma determinada região. Porém, ao buscar os arquivos, foi encontrada apenas a matriz evidenciada no seguinte quadro:
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:
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.
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.
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:
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: 
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.