1. Considere o problema de Fluxo Máximo do vértice s ao vértice t em um grafo orientado G=(V,E) com a restrição de que as capacidades de todos os arcos no grafo é 1.
   1. Proponha um algoritmo com complexidade O(nm) para encontrar o fluxo máximo destes grafos e discuta a sua implementação. (Descreva o algoritmo informalmente, apresente as estruturas que devem ser utilizadas e as operações necessárias, reescreva o algoritmo em função destas operações e analise cuidadosamente sua complexidade).
   2. Hoje, o algoritmo de complexidade mais baixa para este problema tem complexidade O( min { n^2/3m, m^3/2 } ) (ver Ahuja seção 8.2). Qual o gargalo do seu algoritmo ? Onde o seu algoritmo pode ser melhorado ?
   3. Considere agora que os arcos da rede possuem capacidades quaisquer. Explique como este algoritmo pode ser utilizado para se obter um algoritmo para o problema genérico de Fluxo Máximo de complexidade polinomial dada por O(n.m.log U), onde U é a capacidade do arco com maior capacidade.
   
   
2. Considere uma árvore binária de busca onde a sub-árvore com raiz em um nó x possui size[x] elementos. Seja a uma constante tal que 1/2 £ a < 1. Um nó x da árvore é dito balanceado se size[left[x]] £ a . size[x] e size[rigth[x]] £ a . size[x] onde left[x] e right[x] são os nós filhos à esquera e à direita do nó x, respectivamente. A árvore de busca é a-balanceada se todos os seus nós são a-balanceados.
   
   
   1. Dado um nó x, arbitrário, mostre como reconstruir sua sub-árvore de modo que fique 1/2-balanceada. O algoritmo deve executar em O(size[x]) (que é Q ( size[x] )). Lembre que a sub-árvore de x já é uma sub-árvore de busca e size[v] diz quantos elementos estão na sub-árvore de v.
      
      
   2. Mostre que a operação de busca em uma árvore a-balanceada com n elementos é feita em O(log n). (Fácil !!)
      
      
   3. A partir deste item assuma que a > 1/2 (ou seja é estritamente maior que 1/2). Seponha que as operações de Insert e Delete são implementadas da forma habitual, sem rotações, exceto que quando algum nó não está mais a-balanceado, a operação do item a) (reconstrução para deixar 1/2-balanceada) é feita no nó desbalanceado de maior nível.
      
      A idéia é analisar este esquema de reconstrução utilizando o método do pontencial para análize amortizada. Para um nó x na árvore binária T define-se:
      D (x) = | size[left[x]] - size[right[x]] |
      Define-se também o potencial na ávore T, F (T) como:

      F (T) = c

      å x Î T | D(x) ³ 2

      D(x)

      onde c é uma constante sufucientemente grande que depende de a.
      
      
   4. Argumente que qualquer árvore binária de busca tem potencial não-negativo e que uma árvore 1/2-balanceada tem potencial 0.
      
      
   5. Suponha que m unidades de potencial podem pagar pela reconstrução de uma sub-árvore com m nós. Que valor, em função de a, deve ter c para que a operação de reconstrução tome tempo amortizado constante (O(1)), quando é aplicada sobre uma sub-árvore que não está a-balanceada ?
      
      
   6. Mostre que as operações de Insert e Delete tomam tempo amortizado O(log n).

This document was translated from L^AT_EX by H^EV^EA.