23.2-3 A implementação de heap de Fibonacci do algoritmo de Prim é assintoticamente mais rápida que a implementação de heap binário para um grafo esparso G = (V, E), onde |E| = THETA(V)? E no caso de um grafo denso, onde |E| = THETA(V2)? De que modo |E| e |V| devem estar relacionados para que a implementação de heap de Fibonacci seja assintoticamente mais rápida que a implementação de heap binário?
Tempos:
Binário: O (E lg V)
Fibonacci: O (E + V lg V)
Caso 1: grafo exparso ( |E| = THETA(V) )
Binário: O (V lg V)
Fibonacci: O (V + V lg V) = O (V lg V), não é
assintoticamente mais rápido
Caso 2: grafo denso ( |E| = THETA(V2) )
Binário: O (V2 lg V)
Fibonacci: O (V2 + V lg V) = O (V2),
é assintoticamente mais rápido
Relação entre |E| e |V|:
Hipótese: E = omega(V) torna Fibonacci mais rápido
- Testando para E = THETA ( alpha(V) )
Binário: O (V alpha(V) lg V)
Fibonacci: O (V alpha(V) + V lg V) = O (V lg V)
(OK, Finonacci mais rápido)
para provar que basta E = omega (V) para a implementação com Fibonacci ser
melhor assintotaticamente que Binário, utilizamos a complexidade com heap
Binário como THETA (E lg V) e não O (E lg V), sem perda de generalidade:
Binário = THETA ( E lg V ) = omega (E)
Binário = THETA ( E lg V ) = omega (V lg V)
(somando essas duas complexidades
fica:)
Binário = THETA ( E lg V ) = omega (E + V lg V),
ou seja, Binário = omega (Fibonacci), desta forma, provamos que Fibonacci vai
ser sempre melhor assintotaticamante que Binário quando E = omega (V)
23.2-4 Suponha que todos os pesos de arestas em um grafo sejam inteiros no intervalo de 1 a |V|. Com que rapidez é possível executar o algoritmo de Kruskal? E se os pesos de arestas forem inteiros no intervalo de 1 a W para alguma constante W?
Algoritmo de Kruskal, apresentado no capítulo 23, seção 23.2 de [1]
MST-KRUSKAL(G, w)
1 A <- 0
2 for cada vértice v pertencente a V[G] do
3 MAKE-SET(v)
4 ordenar as arestas de E por peso w não decrescente
5 for cada aresta (u, v) pertencente a E, em ordem de peso
não decrescente do
6 if FIND-SET(u) != FIND-SET(v)
7 A <- A
união {(u, v)}
8 UNIOUN(u,
v)
9 return A
Complexidade: O ( (V + E) alpha(V) )
Sabendo o intervalo dos pesos, é possível introduzir uma ordenação linear,
no caso RADIX SORT, para ordenar os vértices por ordem crescente dos
pesos realizada na linha 4. Assim, a complexidade deste algoritmo fica:
O (V + E alpha(V) ) = O ( E alpha(V)
), pois V = O(E alpha(V))
No caso do intervalo ser de 1 a W, onde W é uma constante qualquer, a
rapidez do algoritmo é a mesma que a anterior, O ( E alpha(V) ), pois:
O ( lg W + E alpha(V) ) = O (E alpha(V) ), pois W =
constante, e pode ser removida da análise assintótica
Foi utilizado (lg W) na equação pois números de 1 a W são representados
por (lg W) bits.
23.2-8 O professor Toole propõe um novo algoritmo de dividir e
conquistar para calcular árvores de amplitude mínima, que apresentamos a
seguir. Dado um grafo G = (V, E), particione o conjunto V de vértices em dois
conjuntos V1 e V2, tais que |V1| e |V2
| sejam diferentes por no máximo 1. Seja E1 o conjunto de arestas
incidentes apenas em vértices de V1, e seja E2 o
conjunto de arestas incidentes em vértices de V2. Resolva
recursivamente um problema de árvore de amplitude mínima sobre cada um dos
dois subgrafos G1 = (V1, E1) e G2
= (V2, E2). Finalmente, selecione a aresta de peso
mínimo em E que cruze o corte (V1, V2) e use essa
aresta para unir as duas árvores de amplitude mínima resultantes em uma
única árvore de amplitude.
Demonstre que o algoritmo calcula corretamente uma árvore
de amplitude mínima de G, ou forneça um exemplo para o qual o algoritmo não
funciona.
Se um dos conjuntos V1 e V2 não for conexo, não existirá uma árvore de amplitude mínima nele, portanto o algoritmo falha. Caso eles sejam conexos, o contra-exemplo abaixo prova que o algoritmo falha:
Como o algoritmo reparte o grafo "de qualquer forma", a repartição da figura poderia ser feita, e ela levaria ao algoritmo a escolher as arestas sombreadas para formarem a árvore de amplitude, que, porém, não seria mínima.