Grátis: Um mapa rodoviário é modelado como um grafo em que os vértices representam interseções. As arestas representam segmentos de estrada entre interseçõ... – Questões Respondidas

Matemática Discreta

Outros

Um mapa rodoviário é modelado como um grafo em que os vértices representam interseções. As arestas representam segmentos de estrada entre interseções. O peso de cada aresta representa a distância entre interseções. Agora, considere que um motorista deseja obter o caminho mais curto entre duas cidades. Dado um mapa contendo as distâncias entre cada par de interseções adjacentes, como obter o caminho mais curto entre duas cidades?
A) Caminho mais curto com destino único.
B) Caminho gerador mínimo de origem única.
C) Caminho mais curto com origem única.
D) Caminho mais curto entre todos os pares de vértices.
E) Caminho gerador mínimo de origem múltipla.

Questões Para o Saber

há 10 meses

Questões Para o Saber

há 10 meses

PosComp 2017 2018 2019 gabaritada

PosComp 2017 2018 2019 gabaritada

UNINASSAU VITÓRIA DA CONQUISTA

Respostas

Ed

há 9 meses

Para encontrar o caminho mais curto entre duas cidades em um grafo, onde os vértices representam interseções e as arestas representam segmentos de estrada com pesos (distâncias), a abordagem correta é utilizar um algoritmo que se concentre em um único par de vértices: a origem (cidade de partida) e o destino (cidade de chegada). Vamos analisar as alternativas: A) Caminho mais curto com destino único - Essa opção não é a mais precisa, pois não especifica que se trata de um único par de vértices. B) Caminho gerador mínimo de origem única - Esta opção se refere a um conceito diferente, que é o de encontrar uma árvore geradora mínima, não o caminho mais curto entre duas cidades. C) Caminho mais curto com origem única - Esta opção é a mais adequada, pois se refere a encontrar o caminho mais curto a partir de uma origem específica para um destino específico. D) Caminho mais curto entre todos os pares de vértices - Esta opção se refere a um problema mais amplo, que não é necessário se o objetivo é apenas encontrar o caminho entre duas cidades. E) Caminho gerador mínimo de origem múltipla - Assim como a opção B, esta também se refere a um conceito diferente e não é aplicável ao problema. Portanto, a alternativa correta é: C) Caminho mais curto com origem única.

Essa resposta te ajudou?

0

0

left-side-bubbles-background

right-side-bubbles-background

Crie sua conta grátis para liberar essa resposta. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

PosComp 2017 2018 2019 gabaritada

PosComp 2017 2018 2019 gabaritada

UNINASSAU VITÓRIA DA CONQUISTA

Mais perguntas desse material

Considerando-se os conceitos básicos de grafos e algoritmos em grafos, assinale a alternativa INCORRETA.
b) Grafo: conjunto de vértices e arestas.
c) Vértice: objeto simples que pode ter nome e outros atributos.
d) Grafo completo: grafo não direcionado, no qual todos os pares de vértices são adjacentes.
e) Aresta: conexão entre dois grafos.

Um grafo consiste num conjunto de nós (ou vértices) e num conjunto de arcos (ou arestas). É correto afirmar que o grau de um nó é
A) o número de arcos incidentes nesse nó.
B) um número associado ao arco, também chamado de peso.
C) a distância entre este nó e um outro nó qualquer do grafo.
D) a posição deste nó em relação ao nó raiz do grafo.
E) o número de pares ordenados que formam o arco.

A árvore geradora mínima de um grafo conexo não direcionado construída com o algoritmo de Kruskal é única. Nessa árvore geradora mínima, a substituição de arestas de mesmo peso não afetará o custo total da árvore.
( ) CERTO
( ) ERRADO

Na teoria dos Grafos, dois nós ligados por um arco são chamados de nós
a) Parciais
b) Conexos
c) Adjacentes
d) Acíclicos
e) Fortemente conexos

A estrutura de dados chamada grafo consiste num conjunto de nós (ou vértices) e num conjunto de arcos (ou arestas). Cada arco em um grafo é especificado por um par de nós. Se os pares de nós que formam o arco forem pares ordenados, diz-se que o grafo é
a) incidente.
b) Ponderado
c) Adjacente
d) Orientado
e) Sucessor

Considere a matriz de adjacência abaixo correspondente a um grafo direcionado ponderado. Avalie as afirmacoes referentes ao menor caminho tendo como origem o vértice 1.
I. O menor caminho do vértice 1 até o vértice 7 passa pelos vértices 3 e 8.
II. O menor caminho do vértice 1 até o vértice 5 passa pelo vértice 2.
III. O menor caminho do vértice 1 até o vértice 9 passa pelos vértices 2 e 6.
IV. O menor caminho do vértice 1 até o vértice 8 passa pelos vértices 3 e 6.
V. O menor caminho do vértice 1 até o vértice 6 passa pelo vértice 4.
a) I, II e IV.
b) I, II e V.
c) II, III e IV.
d) I e IV.
e) I e V.

Sobre percurso em grafos, é correto afirmar que um percurso:
A) É uma família de ligações sucessivas incidentes, cada uma tendo uma extremidade incidente à anterior e à outra subsequente.
B) É fechado, se a última ligação da sucessão for adjacente à primeira.
C) Aberto não pode conter subpercursos fechados.
D) É elementar, se não repetir ligações.
E) É simples, se não repetir vértices.

Sobre grafos, assinale a alternativa correta: A Se existir um caminho c de x a y, então, x é alcançável a partir de c via y. B Um caminho em um grafo é complexo se todos os vértices do caminho são distintos. C Todo grafo completo tem pesos associados às suas arestas. D O grau de um vértice em um grafo não direcionado é o número de arestas que incidem nele. E Um grafo ponderado é um grafo não direcionado, em que todos os pares de vértices são adjacentes, isto é, há arestas ligando todos os vértices entre si.

Considere o grafo G abaixo e as afirmações feitas sobre G:
I. O grafo é planar.
II. O menor caminho direcionado medido em número de arcos entre os nós D e F tem comprimento 2.
III. DABCEF representa uma ordenação topológica válida dos nós do grafo.
IV. Existe algum caminho direcionado entre D e todos os outros nós do grafo.
V. O maior componente fortemente conexo de G é composto por um único nó, ou seja, não existe em G um par de nós distintos x e y que tenha um caminho direcionado entre x e y e um caminho direcionado entre y e x.
A) Apenas II e III.
B) Apenas I, II e IV.
C) Apenas I, III e V.
D) Apenas I, II, III e V.
E) I, II, III, IV e V.