Algoritmos de Kruskal e Prim Teoria dos Grafos e Análise de Algoritmos - Exercícios

Prévia do material em texto

Algoritmos de Kruskal e Prim – Teoria dos Grafos e Análise de
Algoritmos 
Exercícios
1. O algoritmo de Prim é um dos algoritmos mais tradicionais aplicados ao
problema da árvore geradora mínima de um grafo. Diversas estruturas de dados
podem ser utilizadas tanto na modelagem do grafo como na representação da fila
de prioridades usada por ele. Apesar disso, o seu caráter iterativo e incremental na
condução das expansões sobre uma subárvore inicial não é alterado.
Considerando que o algoritmo de Prim foi executado sobre o grafo a seguir e que o
vértice a foi tomado como inicial, avalie as afirmativas a respeito:
I. O maior tamanho alcançado pela fronteira é de 3 vértices.
II. O último vértice a ser inserido na solução é o d.
III. Após a terceira iteração, o vértice e se torna parte da solução.
IV. A soma dos pesos da árvore final tem valor 18.
Quais estão corretas?
Resposta correta.
A. I e II.
A árvore geradora mínima obtida pela execução do algoritmo é apresentada a
seguir:
Logo:
I. O maior tamanho alcançado pela fronteira é de 3 vértices.
Afirmativa   verdadeira,   porque,   como   a   fronteira   é   composta   de   vértices   cuja
distância   não   seja   "infinita",   ao  alcançar   o   vértice c,   ela   será   composta  pelos
vértices d, e e f. Em todas as demais iterações, o número de vértices na fronteira
não ultrapassa o valor 3.
II. O último vértice a ser inserido na solução é o d.
Afirmativa verdadeira, uma vez que a sequência de vértices inseridos na solução
é: a - b - c - f - e - d.
III. Após a terceira iteração, o vértice e se torna parte da solução.
Afirmativa falsa, porque o vértice e se torna parte da solução apenas na quarta
iteração.
IV. A soma dos pesos da árvore final tem valor 18.
Afirmativa falsa, pois a soma dos pesos gera o valor 15.
2. Embora seja um algoritmo tradicional para o problema da árvore geradora 
mínima de grafos, o algoritmo de Prim tem o seu funcionamento condicionado ao 
atendimento de certos pré-requisitos. Tanto as características do grafo como as 
estruturas de dados empregadas em sua implementação podem afetar o seu 
desempenho ou, até mesmo, inviabilizar a busca por uma solução ótima.
Nesse contexto, considere que o grafo a seguir foi passado como parâmetro para o
algoritmo de Prim.
Julgue V (verdadeiro) ou F (falso) as afirmativas a respeito do comportamento do
algoritmo:
( ) A alteração do peso w(e) de cada aresta e por w(e) * w(e) compromete a
obtenção da árvore geradora mínima.
( ) A solução obtida pelo algoritmo depende da escolha do vértice inicial usado
para iniciar a construção da árvore.
( ) A remoção de 3 arestas de qualquer vértice inviabiliza a obtenção da árvore pelo
algoritmo.
( ) O cuso total da árvore geradora mínima do grafo é inferior à soma dos pesos
das arestas do vértice de maior grau.
Assinale a alternativa que apresenta a sequência correta.
Você acertou!
B. F - F - F – V.
As escolhas feitas pelo algoritmo de Prim dependem apenas da ordenação dos
custos de fronteira. A mudança proposta nos pesos das arestas não altera a ordem
dos custos das arestas.
Qualquer que seja a escolha do vértice inicial, a árvore geradora mínima obtida
será a mesma.
A remoção de 3 arestas dos vértices a, b, c e d ocasiona que esses vértices se
desconectem   do   grafo.   Nesse   caso,   o   algoritmo   de   Prim   não   funciona
corretamente. Porém, se 3 arestas forem removidas do vértice, este permanece
conectado   ao   grafo   e,   portanto,   o   funcionamento   do   algoritmo   não   é
comprometido.
De fato, o custo total da árvore geradora mínima do grafo é inferior à soma dos
pesos das arestas do vértice de maior grau.
O custo total da árvore geradora mínima é: w(a-e) + w(e-b) + w(e-c) + w(c-d) = 2 +
3 + 4 + 4 = 13. Já a soma dos pesos das arestas do vértice e (vértice de maior
grau) é: 5 + 3 + 2 + 4 = 14.
3. Os algoritmos de Prim e Kruskal constituem estratégias clássicas para a
obtenção da árvore geradora mínima de grafos. Ambos podem alcançar bom
desempenho computacional desde que suas particularidades sejam levadas em
consideração durante a implementação. Apesar disso, os dois algoritmos diferem
significativamente quanto ao processo de obtenção da solução ótima.
Nesse contexto, considere os grafos (a) e (b) apresentados a seguir e as seguintes
condições:
Considere o seguinte:
- Apesar de as arestas ainda não adicionadas à solução não estarem explicitamente
representadas, ambos os grafos são conexos e não direcionados.
- Cada grafo representa a árvore geradora mínima que está sendo construída por
um dos algoritmos.
- As 4 arestas representadas por linhas sólidas indicam a parte da árvore geradora
mínima que já foi construída.
- O próximo passo a ser executado por um dos algoritmos é representado por uma
linha tracejada.
Assinale a alternativa que apresenta a análise correta das seguintes afirmativas:
I. Os grafos (a) e (b) indicam o processo de geração da árvore geradora mínima dos
algoritmos de Kruskal e de Prim, respectivamente.
PORQUE
II. A distância geométrica entre os vértices está sendo usada como medida de peso
associada às arestas do grafo.
Você acertou!
D. A afirmação I é uma proposição falsa e a II, verdadeira.
Considerando que as linhas sólidas representam as arestas que já compõem a
árvore geradora mínima e que a aresta tracejada corresponde ao próximo passo
de um dos algoritmos, é possível observar que a distância geométrica está sendo
usada como critério de peso na seleção das arestas. 
Porém, analisando o próximo passo executado sobre o grafo (a),   temos que a
aresta d-e é inserida na solução. Essa aresta corresponde à aresta de menor peso
(distância geométrica) em relação à parte da árvore que já foi construída. Essa
abordagem de avaliar  a   fronteira   (ou  as  arestas  com apenas  um dos  vértices
pertencentes  à   árvore  em construção)   corresponde  à  estratégia   implementada
pelo   algoritmo  de  Prim.  No  grafo   (b),   uma  abordagem diferente  é   observada.
Dentre   todas  as  arestas  disponíveis  para  seleção,  a  aresta  e-f  é  a  de  menor
distância   geométrica   (peso)   e,   por   isso,   ela   foi   selecionada.   Essa   estratégia
corresponde ao funcionamento do algoritmo de Kruskal. 
4. Várias são as estruturas de dados que podem ser empregadas na implementação
do algoritmo de Kruskal para o problema da árvore geradora mínima de um grafo.
Cada estrutura usada, no entanto, vai impactar de maneira diferente no
desempenho computacional do algoritmo. Uma das estruturas de dados mais
reconhecidas pela sua eficiência quando usada no algoritmo de Kruskal é a União-
Busca. Ela é composta de duas operações básicas:
1. Busca: Dada uma lista de conjuntos e um elemento x a ser buscado, ela retorna o
conjunto da qual x é um elemento. Esse retorno pode ser denotado por Conjunto(x).
2. União: Dados dois conjuntos disjuntos, ela realiza a união desses dois conjuntos
gerando um terceiro a partir da remoção dos dois conjuntos originais.
Tendo como base o uso da estrutura de dados União-Busca, assinale a alternativa
que preenche corretamente as lacunas do algoritmo de Kruskal a seguir:
Você acertou!
C. 
Ordenar as arestas de G em ordem não decrescente de peso
Conjunto(u) é diferente de Conjunto(v)
Adicionar (u, v) a A
Uma das premissas do algoritmo de Kruskal é que as arestas sejam previamente
ordenadas de forma não decrescente com base no peso associado. Além disso, a
adição de uma nova aresta à arvore geradora mínima em construção deve ser
precedida de um teste para detectar se essa nova inserção acarretaria a criação
de um ciclo.  Com o uso da operação de Busca da estrutura  de dados União-
Busca,   os   conjuntos   onde   os   vértices u e v podem   ser   encontrados   serão
recuperados. Caso esses conjuntos sejam diferentes, então a inserção da aresta
não provocará  a criação de um ciclo  na árvore.  Finalmente,  se os vértices da
aresta em análise pertencerem a conjuntos distintos, então essa aresta pode serincluída na solução. Isso é feito adicionando-se a aresta (u, v) na variável A que
armazena a solução.
5. Algumas características do algoritmo de Kruskal para o problema da árvore
geradora mínima possibilitam que ele seja aplicado em uma grande variedade de
cenários. Dentre as mais destacadas, a estratégia de explorar múltiplas árvores em
paralelo faz com que o algoritmo apresente uma eficiência computacional superior
em relação a outros algoritmos para o mesmo problema.
Nesse contexto, considere a aplicação do algoritmo de Kruskal no grafo a seguir e
avalie as afirmativas a respeito:
I - A aresta de maior peso que compõe a árvore geradora mínima final tem valor 6.
II - O número de árvores intermediárias geradas e compostas por mais de 1 vértice
é, no máximo, 2.
III - Para as primeiras i iterações, com i = 1, 2 e 3, as arestas de peso i são inseridas
na solução nessa ordem.
IV - O valor do custo total da árvore geradora mínima (soma dos pesos das arestas)
é 15.
Quais estão corretas?
Você acertou!
E. II e III.
A árvore  geradora  mínima  construída  pelo  algoritmo  é  obtida   com a  seguinte
sequência de inserções de arestas na solução:
1.   Inserção   da   aresta   (b,   c): peso   1
2.   Inserção   da   aresta   (d,   e): peso   2
3.   Inserção   da   aresta   (b,   d): peso   3
4. Inserção da aresta (b, a): peso 5
I. A aresta de maior peso é (b, a) com valor 5.
II.  As duas primeiras arestas inseridas na solução, (b, c) e (d, e),  formam dois
conjuntos disjuntos. As próximas inserções ocasionam a união desses conjuntos.
III. Na  iteração 1,  a  aresta   inserida  (b,  c)   tem peso 1;  na  iteração 2,  a  aresta
inserida (d, e) tem peso 2; na iteração 3, a aresta inserida (b, d) tem peso 3.
IV. A soma dos pesos das arestas que compõem a árvore geradora mínima totaliza
11.
	Algoritmos de Kruskal e Prim – Teoria dos Grafos e Análise de Algoritmos
	Exercícios