Scribd
Carregar
9 visualizações1 página

Lista 11

O documento apresenta uma lista de exercícios sobre algoritmos de grafos, incluindo a execução dos algoritmos de Dijkstra, Prim e Kruskal em um grafo específico. Além disso, discute a propriedade de árvores geradoras de custo mínimo em grafos não direcionados com custos de arestas não negativos e a influência de alterações nos pesos das arestas em caminhos de custo mínimo em grafos direcionados. O texto solicita provas ou contra-exemplos para as questões propostas.

Enviado por

rdmartins2077
Direitos autorais
© © All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato PDF, TXT ou leia on-line no Scribd
9 visualizações1 página

Lista 11

O documento apresenta uma lista de exercícios sobre algoritmos de grafos, incluindo a execução dos algoritmos de Dijkstra, Prim e Kruskal em um grafo específico. Além disso, discute a propriedade de árvores geradoras de custo mínimo em grafos não direcionados com custos de arestas não negativos e a influência de alterações nos pesos das arestas em caminhos de custo mínimo em grafos direcionados. O texto solicita provas ou contra-exemplos para as questões propostas.

Enviado por

rdmartins2077
Direitos autorais
© © All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato PDF, TXT ou leia on-line no Scribd

Universidade Federal Rural do Rio de Janeiro

Curso: Ciência da Computação


Disciplina: Grafos e Algoritmos
Professora: Fernanda Couto
Lista 11 – Grafos e Algoritmos: Algoritmos caminhos mínimos e
MST

1. Considerando o grafo ilustrado na Figura 1. Execute:


(a) O algoritmo de Dijkstra, tomando o vértice A como ponto de partida.
(b) O algoritmo de Prim, tomando o vértice A como ponto de partida.
(c) O algoritmo de Kruskal.

2
7 9
2 3 6
2
1
6 1
1 2
5

Figura 1: Grafo do Exercício 1

2. Considere um MST em um grafo não direcionado G(V, E) onde cada aresta e ∈ E


possui custo não negativo e que tais custos não são necessariamente diferentes. Em
geral, quando os custos não são todos distintos, o grafo G pode possuir várias árvores
geradoras de custo mínimo.
Suponha que você conheça uma árvore geradora T ⊂ E com a garantia de que para
aresta e ∈ T , a aresta e pertence a alguma árvore geradora de custo mínimo de G.
Podemos concluir que T é uma árvore geradora de custo mínimo de G? Prove este
resultado ou dê um contra-exemplo.
3. Considere o problema do caminho de custo mínimo em um grafo G direcionado. Assuma
que todos os pesos das arestas de G são positivos e distintos. Seja P um caminho de
custo mínimo entre os vértices s e t de G. Agora suponha que todos os pesos das arestas
de G sejam trocados pelo quadrado do seu valor, dando origem a uma nova instância
do problema no mesmo grafo, mas com pesos diferentes. O caminho P irá continuar a
ser um caminho de custo mínimo entre s e t nesta nova instância? Caso negativo, dê
um contra-exemplo.

Você também pode gostar