Grátis: 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 substitu... – Questões Respondidas

Matemática Discreta

Outros

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

Questões para o Sucesso

há 10 meses

Questões para o Sucesso

há 10 meses

PosComp 2017 2018 2019 gabaritada

PosComp 2017 2018 2019 gabaritada

UNINASSAU VITÓRIA DA CONQUISTA

Respostas

Ed

há 9 meses

A afirmação está CERTA. Em uma árvore geradora mínima (AGM) de um grafo conexo não direcionado, se houver arestas de mesmo peso, a substituição dessas arestas por outras de mesmo peso não afetará o custo total da árvore. Isso ocorre porque o custo total da AGM é determinado pela soma dos pesos das arestas, e a troca de arestas de mesmo peso não altera essa soma. Portanto, a AGM pode não ser única se houver arestas de mesmo peso, mas o custo total permanecerá o mesmo.

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.

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.

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.

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.