MO417 - Prova I2

Criada: 2003-07-06

Data da prova: 2003-06-27

Enunciado: aqui

Soluções e Critérios de Nota:

1. Solução:

   Conforme o que foi visto no curso, temos que a melhor estrutura de dados para o algoritmo de Prim são os heaps de Fibonacci, e com eles a complexidade é O(E + V lg V); a melhor estrutura de dados para o algoritmo de Kruskal é a estrutura de conjuntos disjuntos (union-find), e com ela a complexidade é O(E lg V). Alguns alunos observaram que ela pode chegar a O(E + V) se os pesos das arestas permitirem ordenação em tempo linear, mas não vamos considerar esta nem nenhuma restrição dos dados de entrada nesta questão.

   Estas complexidades "empatam" assintoticamente quando E = O(V) (grafos esparsos), ficando ambas em O(V lg V). Por outro lado, se E = omega(V) então o algoritmo de Prim ganha.

   Critério:

   • se não mencionou alguma das estruturas de dados necessárias, perde 0,5
   • se alguma das complexidades foi dada errada, por exemplo O(V lg V) para Prim, perde 0,5
   • não perdeu ponto quem apenas analisou os casos E = O(V) e E = O(V²)
   • se a comparação não foi bem feita, perde 0,5

2. Solução:

   É possível reduzir a complexidade de tempo usando |V| vezes o cálculo de caminhos mínimos em grafos orientados acíclicos com ordenação topológica, usando cada vértice como origem. Cada vez gastaria O(V + E), produzindo uma complexidade total de O(V² + VE).

   Quanto ao espaço, é necessário continuar com O(V²), pois dependendo do vértice inicial a distância a um certo vértice pode variar.

   Critério:

3. Solução:

   Critério:

4. Solução:

   Critério: