Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM6, Grafos: Bipartição, Propriedades via DFS, AP/Pontes, SCC, MST e…
MM6
Grafos: Bipartição, Propriedades via DFS, AP/Pontes, SCC, MST e Aplicações
4.2.6 Verificação de Grafo Bipartido
Aplicações importantes (ver Seção 4.7.4); problemas como UVa 10004 - Bicoloring
Podemos usar BFS ou DFS; BFS é mais natural
Ideia: colorir por camadas alternando 0 e 1
Fonte (1ª camada): cor 0
Vizinhos diretos (2ª camada): cor 1
Vizinhos dos vizinhos (3ª camada): cor 0, e assim por diante
Violação: se existir aresta com dois endpoints de mesma cor → não é bipartido
4.2.7 Verificação de Propriedades de Arestas via Árvore de DFS
DFS em grafo conectado gera árvore geradora de DFS (ou floresta se desconectado)
Estados de vértice: UNVISITED, EXPLORED = 2 (visitado mas não concluído), VISITED (concluído)
Classificação de arestas:
Aresta de árvore: EXPLORED → UNVISITED (aresta percorrida pela DFS)
Aresta de retorno (back edge): EXPLORED → EXPLORED (parte de um ciclo)
Não contar arestas bidirecionais como ‘ciclo’; usar dfs_parent para distinguir
Arestas de avanço/cruzamento: EXPLORED → VISITED (tipicamente não testadas em concursos)
4.2.8 Encontrando Pontos de Articulação e Pontes (Grafo Não-Direcionado)
Problema motivador: sabotagem mínima (custo) em interseção (vértice) ou estrada (aresta) para desconectar rede
Definições:
Ponto de Articulação: remover vértice (e arestas incidentes) desconecta G; grafo sem AP é ‘Biconectado’
Ponte: aresta cuja remoção desconecta G
Algoritmo ingênuo:
Rodar O(V + E) DFS/BFS para contar componentes conexos (CCs) do grafo original (geralmente 1)
Para cada vértice v ∈ V:
a) Remover v e suas arestas incidentes
b) Rodar O(V + E) DFS/BFS e verificar aumento no número de CCs
c) Se sim, v é ponto de articulação; restaurar v e incidentes
Complexidade: O(V × (V + E)) = O(V^2 + V E)
Algoritmo DFS (Hopcroft–Tarjan):
Manter dfs_num(u) (ordem de visita) e dfs_low(u) (menor dfs_num alcançável da subárvore de u)
Inicialmente, dfs_low(u) = dfs_num(u) ao visitar u pela 1ª vez
Atualizar dfs_low(u) se houver ciclo (aresta de retorno); não atualizar com aresta (u, v) se v é pai direto de u
Exemplo: sequência 0(0) → 1(1) → 2(2) → backtrack 1 → 3(3) → backtrack 1 → 4(4) → 5(5)
Aresta 5-1 forma ciclo 1-4-5-1 → dfs_low de {1, 4, 5} = 1
Ponto de articulação: se em u com vizinho v, dfs_low(v) ≥ dfs_num(u)
Intuição: não há back edge de v alcançando ancestral de u → remover u desconecta
Caso especial: raiz da DFS é AP somente se tiver > 1 filhos na árvore de DFS
Ponte: quando dfs_low(v) > dfs_num(u) para aresta u-v
Ex.: na Figura 4.8, quase todas arestas são pontes; 1-4, 4-5, 5-1 não são (formam ciclo)
4.2.9 Encontrando Componentes Fortemente Conexos (SCC) (Grafo Direcionado)
Diferente de CCs em grafo não-direcionado
Definição de SCC: para qualquer par u, v no SCC, há caminho u→v e v→u
Exemplo (Figura 4.9): três SCCs {0}, {1, 3, 2}, {4, 5, 7, 6}; contrair SCCs forma um DAG (ver Seção 8.4.3)
Algoritmos: Kosaraju; Tarjan (adotado aqui)
Ideia: SCCs formam subárvores na árvore de DFS
Além de dfs_num/dfs_low:
Empilhar u em S ao visitar; marcar visitado (vi)
Atualização de dfs_low(u): apenas por vértices atualmente na pilha/visitados (parte do SCC atual)
Se dfs_low(u) = dfs_num(u): u é raiz de um SCC
Reportar membros desempilhando S até u
Exemplo de pilha S:
Quando 4 é raiz (dfs_low(4) = dfs_num(4) = 4): S = {0, 1, 3, 2, 4, 5, 7, 6} → SCC {6, 7, 5, 4}
Depois, 1 é raiz: S = {0, 1, 3, 2} → SCC {2, 3, 1}
Último SCC: {0}
Complexidade total: O(V + E)
4.3 Árvore Geradora Mínima (MST)
4.3.1 Visão Geral e Motivação
Problema: dado grafo conectado, não-direcionado e ponderado G, escolher E′ tal que G permaneça conectado e o peso total seja mínimo
Necessitamos V−1 arestas formando uma árvore que cubra todos os V (spanning tree)
Há várias árvores geradoras possíveis; algumas têm peso mínimo
Algoritmos: Prim e Kruskal (ambos Greedy)
Peso do MST é único; podem existir múltiplas árvores com mesmo peso
4.3.4 Outras Aplicações
‘Maximum’ Spanning Tree
Variante: maximizar em vez de minimizar (ex.: UVa 1234 - RACING)
Solução: ordenar arestas por peso não crescente
‘Minimum’ Spanning Subgraph
Algumas arestas já fixas e devem ser usadas (ex.: UVa 10147 - Highways)
Subgrafo resultante pode não ser árvore nem MST (‘Minimum’ entre aspas)
Solução: considerar arestas fixas e custos; continuar Kruskal nas arestas livres até conectar
Minimum ‘Spanning Forest’
Objetivo: formar floresta com K componentes conectados no menor custo (ex.: UVa 10369 - Arctic Networks)
Solução: rodar Kruskal e parar quando número de componentes = K
Segunda melhor Árvore Geradora
Quer também a segunda melhor (ex.: UVa 10600 - ACM contest and blackout)
Observação: segunda melhor = MST com duas arestas diferentes (remove uma do MST e adiciona uma corda)
Algoritmo:
Ordenar arestas (O(E log V)); achar MST (O(E))
Para cada aresta do MST, bloqueá-la e recomputar MST (O(E)) sem reordenar
Melhor resultado após esse processo é a segunda melhor
Complexidade: O(E log V + E + V E) = O(V E)
Minimax (e Maximin)
Problema: minimizar o máximo peso de aresta ao longo de caminhos entre i e j (maximin é análogo)
Solução via MST:
Construir MST (Kruskal/Prim), que é conectado
Caminho único no MST entre i e j; custo minimax = maior peso de aresta nesse caminho
Complexidade: O(E log V + V) = O(E log V)
Observações sobre MST em Competições
Kruskal geralmente basta; problemas pedem o custo único do MST, não a árvore
Variantes (‘Minimum’ SS, Spanning Forest, Segunda melhor, Minimax/Maximin) são raras
Tendência: problemas disfarçam que são MST; ao perceber, ficam ‘fáceis’
Existem variantes mais difíceis: arborescência, Steiner, MST com grau limitado, k-MST
4.3.2 Algoritmo de Kruskal
Ideia central:
Armazenar as arestas em uma EdgeList e ordenar por peso não decrescente
Tentar adicionar cada aresta ao MST se a adição não formar ciclo
A verificação de ciclo é feita com Union-Find Disjoint Sets (UFDS) (Seção 2.4.2)
Passos (fluxo):
Ordenar todas as arestas por peso (não decrescente)
Para cada aresta (em ordem):
Se a aresta não formar ciclo (cheque com UFDS), adicioná-la ao MST
Caso contrário, ignora
Observações:
O código é curto pois a implementação de Union-Find fica separada
Complexidade:
O(sorting + tentativas de adicionar arestas × custo UFDS)
O(E log E + E × (≈ 1)) = O(E log E) = O(E log V^2) = O(2 × E log V) = O(E log V)
4.3.3 Algoritmo de Prim
Ideia central:
Começar de um vértice (por simplicidade, 0), marcá-lo como ‘tomado’
Usar uma fila de prioridade (min-heap) com pares (w, u) para as arestas que saem do conjunto tomado
Escolher sempre a aresta de menor peso que liga um vértice ainda não tomado
Estrutura da fila de prioridade:
Ordenada por peso crescente w
Em caso de empate, por número do vértice crescente
Passos (fluxo):
Marcar o vértice inicial 0 como ‘tomado’
Enfileirar na PQ todos os pares (w, u) das arestas 0 → u cujos u ainda não foram tomados
Enquanto a PQ não estiver vazia:
Extrair o par (w, u) de menor w
Se u ainda não foi tomado:
Somar w ao custo do MST
Marcar u como ‘tomado’
Para cada aresta u → v com peso w′:
Se v não foi tomado, enfileirar (w′, v) na PQ