Introdução à Teoria dos Grafos - Atividade 5

Prévia do material em texto

O planejamento de uma viagem em família, quando feita de carro, passa por observar os quilômetros que cada uma das rodovias possui, o estado de conservação, o número de pedágios, entre outras características que podem mudar conforme a distância ou região do país. Esses planejamentos possuem semelhanças com as teorias encontradas no problema do caixeiro viajante.
 
Nesse sentido, assinale a alternativa que descreve o propósito da análise proposta pelo problema do caixeiro viajante.
O custo.
Um gerente de projetos recebeu o mapa das cidades da região com os seus respectivos custos de deslocamento de 1 para R$ 100,00. Esse mapa pode ser observado na seguinte figura:
 
Fonte: Elaborada pelo autor.
 
Sabe-se que o gerente utilizará o algoritmo de Dijkstra para a tarefa de deslocamento partindo do vértice A. Diante do exposto, qual, dentre as seguintes alternativas, apresenta a matriz aplicada ao algoritmo de Dijkstra?
Alternativa E
As matrizes podem representar um conjunto de dados extraídos de diversas fontes, tornando-se uma ferramenta matemática de extrema importância, principalmente quando existe a necessidade de se organizar grandes quantidades de valores. A sua estrutura pode ser observada a seguir.
Fonte: Elaborado pelo autor.
Assinale a alternativa que apresenta a afirmação correta.
Existe um laço no vértice CCC.
Um entregador de comidas por aplicativo recebeu seis entregas de uma única vez. Preocupado em não atrasar as entregas e gerar insatisfação aos clientes, ele foi até o mapa do bairro e marcou cada um dos pontos de entrega.
 
Figura 3.2 - Pontos de entrega
Fonte: Elaborada pelo autor.
 
 
Esse grafo deve orientar as entregas, para que se tenha a otimização do trajeto. Nesse sentido, assinale a alternativa que indica corretamente suas características.
Trata-se de um grafo de Hamilton, pois é possível fazer o trajeto visitando todos os pontos, sem repetência e, ainda, inicia-lo e finalizá-lo no mesmo ponto.
Os grafos podem ser representados por matrizes, nas quais é possível demonstrar a relação entre os vértices, conforme pode ser observado a seguir:
Fonte: Elaborado pelo autor.
 
A matriz representa as estradas que ligam uma cidade à outra; o “0” indica que não possui estrada que liga as duas cidades diretamente e o “1” indica que a rodovia possui uma via de ligação entre as duas cidades.
 
Com base no contexto apresentado, observe as afirmativas a seguir:
 
I. Os vértices podem ser representados pelos nomes das cidades.
II. As arestas são representadas pelos valores 0 e 1.
III. Seria possível representar esse grafo em matriz por um diagrama.
IV. Não é possível representar o grafo, devido aos vértices terem sido representados por nomes.
 
Está correto o que se afirma em:
I e III, apenas.
Os grafos quando representados por diagrama podem ter diversos formatos. O conjunto V = {A, B, C, D} e A = {(A, B), (A, C), (A, D), (B, C), (B, D), (C, D)}. A representação pelo meio de diagramas auxilia na compreensão do tipo de grafo que determinado G(V, A) pode demonstrar.
 
Com base no apresentado, assinale a alternativa que descreva o tipo de grafo corretamente.
Regular.
Muitas vezes no encontro de duas ou mais rodovias, ocorre o cruzamento de pontes, viadutos e túneis, isso para se garantir a fluidez do trânsito e permitir que as pessoas possam alcançar os seus destinos. O estudo dos grafos planares pode utilizar-se de tais analogias - como o exemplo das rodovias - para explicar o seu objeto.
 
Nesse sentido, assinale a alternativa que indica o que os grafos planares se propõem a discutir.
O cruzamento das arestas.
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.
O grafo correto possui arestas entre os vértices de A para D, de E para A, de A para B, de B para C e, finalmente, de B para F.
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:
II e IV, apenas.
Hamilton era considerado um menino prodígio, pois, desde pequeno, já mostrava que era diferente de grande parte da população. Com apenas 14 anos, já falava diversos idiomas, porém a sua principal contribuição é o Circuito de Hamilton, que proporcionou novas discussões acerca da Teoria dos Grafos.
 
Considerando o excerto apresentado, sobre o Circuito de Hamilton, analise as afirmativas a seguir.
 
I. Os grafos de Hamilton possuem um circuito circular e contínuo.
II. O trajeto deve garantir que se visite apenas uma única vez cada vértice do grafo.
III. O trajeto pode ser iniciado em um vértice e ser finalizado em outro.
IV. Apenas grafos com quatro vértices ou mais são possíveis de desenvolver um grafo de Hamilton.
 
Está correto o que se afirma em:
I e II, apenas.