Please enable JavaScript.

Coggle requires JavaScript to display documents.

MM8 - Coggle Diagram

- - - - Arestas de ida (i→j): capacidade residual diminui em f
      - Arestas de volta (j→i): capacidade residual aumenta em f (permite “desfazer” uso incorreto)
    - - Via DFS: pode cair no pior caso O(|f|·E) (|f| = valor do fluxo máximo)
      - Exemplo de armadilha: alternar por caminhos mais longos reduzindo 1 por iteração
  - - - Matriz residual res de tamanho V×V
      - Custo com matriz: O(V·E) BFS × O(V^2) por BFS = O(V^3·E) (suficiente para instâncias pequenas)
  - - - s → app: capacidade = número de usuários do app (1..9)
      - app → PC: capacidade = ∞ (ou valor grande)
      - PC → t: capacidade = 1 (cada PC usado uma vez)
    - - Roda Edmonds–Karp; se mf = total de apps trazidos, há alocação
      - Reconstrução da atribuição:
        
        Arestas de retorno PC→app no residual com valor 1 (indica app→PC escolhido)
  - - - Corte C = (S, T): s ∈ S, t ∈ T; cut-set = arestas de S→T
      - Custo do corte = soma das capacidades das arestas no cut-set
      - Max-Flow Min-Cut: valor do min cut = fluxo máximo
      - Como obter após rodar mf:
        
        BFS/DFS em arestas com capacidade residual > 0 a partir de s
        
        Alcançáveis = S; não alcançáveis = T
        
        Arestas S→T saturadas formam o cut-set mínimo
    - - Criar super-fonte ss e super-sorvedouro st
      - ss → todas as fontes com capacidade ∞; todos os sorvedouros → st com capacidade ∞
      - Roda Edmonds–Karp normalmente
    - - Técnica de divisão de vértice (vertex splitting)
        
        Substitui v por vin e vout
        
        Entradas vão para vin; saídas saem de vout
        
        Aresta vin→vout com capacidade = cap(v)
  - - - Conectar células não ‘~’ entre vizinhas com capacidade grande (ex.: 1000)
      - Capacidades de vértice:
        
        ‘*’ e ‘.’: 1 (usadas uma vez)
        
        ‘’ e ‘#’: grande (ex.: 1000)
      - Criar s e t:
        
        s → todas as ‘*’ com capacidade 1 (cada pessoa)
        
        Todas as ‘#’ → t com capacidade P (capacidade de uso do tronco)
      - Resposta = fluxo máximo entre s e t
      - Usa divisão de vértice para modelar capacidades em vértices
- - - - Bottom-Up: Propaga do(s) início(s) usando ordem topológica
      - Top-Down (memoização): Define recorrência e evita recomputar
      - Exemplos de aplicação
        
        Agendamento de projetos (caminho crítico = maior caminho) — UVa 452
        
        Contagem de possibilidades — UVa 988
        
        Problemas clássicos de PD vistos como caminhos em DAG (ex.: Coin Change)
        
        Converter Grafo Geral em DAG