Please enable JavaScript.
Coggle requires JavaScript to display documents.
Capítulo 4: Graphs Parte 4 - Coggle Diagram
Capítulo 4: Graphs Parte 4
4.6 NETWORK FLOW
4.6.1 Overview and Motivation
Problema: determinar o fluxo máximo de s → t
Grafo direcionado e ponderado:
• Arestas = canos (com capacidade)
• Vértices = junções
• s = source, t = sink
Conceitos:
• Fluxo: quantidade que percorre cada aresta
• Rede residual: mostra capacidades restantes
• Arestas forward/backward ajustam capacidades
Objetivo: encontrar o fluxo máximo possível sem exceder capacidades
4.6.2 Ford–Fulkerson’s Method
Ideia:
Encontrar um caminho aumentante s → t
Calcular o fluxo mínimo no caminho
Atualizar capacidades (↓ forward, ↑ backward)
Repetir até não existir mais caminho
Base do algoritmo de fluxo máximo
Pode usar DFS (mas pode ser lento)
Complexidade: O(E × |f*|) (depende do fluxo máximo)
Pontos-chave:
• Fluxo iterativo
• Usa grafo residual
• Pode ter muitas iterações pequenas
4.6.3 Edmonds–Karp Algorithm
Melhoria de Ford–Fulkerson (usa BFS)
Busca o caminho aumentante mais curto (em nº de arestas)
Complexidade: O(V × E²)
Passos:
BFS → caminho aumentante
Encontra gargalo (mínimo residual)
Atualiza capacidades
Soma fluxo e repete
Vantagens:
• Determinístico
• Tempo garantido polinomial
4.6.4 Flow Graph Modeling – Part 1
Etapas:
Reconhecer o problema de Network Flow
Construir grafo de fluxo (arestas + capacidades)
Rodar Edmonds–Karp
Observações:
• Direcionamento é essencial
• Possível modelar com MCBM (Matching Bipartido)
4.6.5 Other Applications
Minimum Cut (Min-Cut)
• Após Max Flow, arestas saturadas → formam o corte mínimo
• Custo mínimo = capacidade total das arestas cortadas
• Exemplo: UVA 10480 – Sabotage
Conceito: Min-Cut ≡ Max-Flow (teorema da dualidade)
4.6.6 Flow Graph Modeling – Part 2
Técnica: Vertex Splitting
• Divide vértice v em vin e vout
• Conecta vin → vout com capacidade = peso original
• Resolve casos de “limite por vértice”
Complexidade permanece O(VE²)
4.6.7 Remarks and Practice
Network Flow é base para:
• Bipartite Matching (MCBM)
• Min Cut
• Circulation Problems
• Edge-Disjoint Paths
• Min Cost Max Flow
4.7 SPECIAL GRAPHS
Introdução
Alguns grafos permitem soluções mais simples/polinomiais
Tipos principais:
Directed Acyclic Graph (DAG)
Tree
Eulerian Graph
Bipartite Graph
Ideia: aproveitar propriedades estruturais específicas
4.7.1 Directed Acyclic Graph (DAG)
Características:
• Direcionado e sem ciclos
• Permite ordenação topológica
Aplicações:
• SSSP e Longest Path (topological order)
• Counting Paths
• Dynamic Programming em grafos acíclicos
Contagem de Caminhos:
• numPaths(i) = Σ numPaths(j), j adjacente
• Duas abordagens: Bottom-Up e Top-Down
Conversão de grafo geral → DAG:
• Aplicando restrições/parametrizações (ex: tempo, custo)
4.7.2 Tree
Características:
• Conectado, acíclico, E = V−1
• Caminho único entre dois vértices
Percursos:
• Pre-order, In-order, Post-order
Aplicações:
• Pontos de articulação e pontes (simples)
• Caminho mais curto ponderado (SSSP simplificado)
• APSP → O(V²)
• Diâmetro → 2 DFS/BFS consecutivos
Observações:
• Árvore enraizada → simplifica DP em árvore
4.7.3 Eulerian Graph
Definição:
• Euler Path → percorre todas as arestas uma vez
• Euler Tour → começa e termina no mesmo vértice
Condições:
• Grafo não direcionado → 0 ou 2 vértices de grau ímpar
• Direcionado → 1 vértice indeg−outdeg = ±1
Checagem: O(V + E)
Aplicações:
• Problemas de percurso completo (ex: roteiros, DNA)
4.7.4 Bipartite Graph
Definição:
• V dividido em dois conjuntos disjuntos (V1, V2)
• Nenhuma aresta conecta vértices do mesmo conjunto
Propriedade: sem ciclos de comprimento ímpar
Problemas Clássicos:
• MCBM – Max Cardinality Bipartite Matching
• MVC – Minimum Vertex Cover
• MIS – Maximum Independent Set
Relações:
• MCBM = MVC
• MIS + MCBM = V
Métodos:
• Modelagem via Max Flow
• Algoritmo de Caminhos Aumentantes (DFS-like)
• Complexidade: O(V × E)
Aplicações:
• Alocação, emparelhamento, equipes, compatibilidade