Algoritmos para Grafos, via Sedgewick | Índice remissivo
Esta página trata de grafos que deixam de ser conexos quando perdem uma de suas arestas. Ela se restringe a grafos pois os conceitos discutidos não fazem sentido em digrafos não simétricos.
(A página é um resumo da primeira parte da seção 18.6 (Separability and Biconnectivity), p.106-114, do capítulo 18 (Graph Search) do livro de Sedgewick.)
Uma aresta de um grafo é uma ponte (= bridge = separation edge) se ela é a única aresta que atravessa algum corte do grafo. [Pontes são também conhecidas com arestas de corte, mas nós não vamos usar essa terminologia.]
Em outras palavras, uma ponte é uma aresta cuja remoção aumenta o número de componentes do grafo.
Problema: Encontrar as pontes de um grafo dado.
Poderíamos aplicar cegamente a definição de ponte para resolver o problema, mas é possível fazer coisa melhor.
É possível encontrar as pontes de um grafo de maneira muito eficiente. O ponto de partida é o seguinte fato básico: em qualquer grafo, uma aresta é uma ponte se e somente se não faz parte de um ciclo não trivial. (Em outras palavras, toda aresta é de um e apenas um de dois tipos: ou ela é uma ponte ou pertence a um ciclo não trivial.)
Se fizermos uma busca em profundidade no grafo, um dos dois arcos que constituem qualquer ponte será necessariamente um arco de arborescência (por que?). Agora observe a seguinte
Propriedade (Property 18.5, p.107, Sedgewick): Em qualquer busca em profundidade, um arco v-w da floresta DFS faz parte (juntamente com w-v) de uma ponte se e somente se não existe arco de retorno que ligue um descendente de w a um ancestral de v.
(Os descendentes e ancestrais de que trata a propriedade não são necessariamente próprios.) Para tirar proveito dessa propriedade, vamos calcular, para cada vértice v, o menor número de preordem (= lowest preorder number) que pode ser alcançado a partir de v. Esse número será denotado por
low[v].
Explico melhor: Digamos, só para efeito desta explicação, que um caminho é interessante se
(Por exemplo, todo caminho de comprimento 0 que começa em v é interessante. Outro exemplo: um caminho de comprimento 1 que começa em v e percorre um só arco de retorno é interessante.) Digamos que o valor de um caminho interessante é lbl[z], sendo z o último vértice do caminho. Então low[v] é, por definição, o valor de um caminho interessante de valor mínimo.
É claro que low[v] ≤ lbl[v] para todo vértice v. Digo mais: para todo arco v-w do grafo,
0-1 1-2 1-4 2-3 2-4 2-9 3-4 4-5 4-6 4-7 5-6 7-8 7-9
Exiba o vetor lbl definido pela busca (ou seja, diga em que ordem os vértices são visitados). Exiba o vetor low associado à arborescência de busca.
A propriedade acima pode ser reformulada assim: em qualquer floresta de busca em profundidade de um grafo, um arco de arborescência v-w faz parte de uma ponte se e somente se low[w] == lbl[w].
/* Nosso grafos terão no máximo maxV vértices. */
static int conta, lbl[maxV], bconta, low[maxV]; static int parent[maxV];/* A função abaixo calcula o número bconta de pontes do grafo G e imprime todas as pontes. (O código foi inspirado no programa 18.7, p.108, de Sedgewick.) */
void all_bridges (Graph G) { Vertex v; conta = bconta = 0; for (v = 0; v < G->V; v++) lbl[v] = -1; for (v = 0; v < G->V; v++) if (lbl[v] == -1) { parent[v] = v; bridgeR(G, v); }void bridgeR (Graph G, Vertex v) { link p; Vertex w; lbl[v] = conta++; low[v] = lbl[v]; for (p = G->adj[v]; p != NULL; p = p->next) if (lbl[w = p->w] == -1) { parent[w] = v; bridgeR(G, w); if (low[v] > low[w]) low[v] = low[w]; if (low[w] == lbl[w]) { bconta++; printf("%d-%d\n", v, w); } } else if (w != parent[v] && low[v] > lbl[w]) low[v] = lbl[w]; }
O teste "if (w != parent[v])" garante que v-w é um arco de retorno (e não um arco-pai).
A função all_bridges é linear: ela consome tempo proporcional a V+E. A variante dessa função para matrizes de adjacência consome tempo proporcional a V².
0-1 1-2 1-4 2-3 2-4 2-9 3-4 4-5 4-6 4-7 5-6 7-8 7-9
Exiba o vetor lbl definido pela busca (ou seja, diga em que ordem os vértices são visitados). Exiba o vetor low associado à arborescência de busca.
0-6 0-1 0-5 1-2 2-6 6-7 7-8 7-10 10-8 5-3 5-4 4-11 4-9 4-3 9-11 11-12
(Adote a representação por listas de adjacência e insira as arestas, na ordem dada, num grafo inicialmente vazio.) Faça um desenho da arborescência de busca em profundidade do grafo.
void bridgeR (Graph G, Vertex v) {
link p; Vertex w;
lbl[v] = conta++;
low[v] = lbl[v];
for (p = G->adj[v]; p != NULL; p = p->next) {
if (lbl[w = p->w] == -1) {
parent[w] = v;
bridgeR(G, w);
if (low[v] > low[w]) low[v] = low[w];
}
else if (w != parent[v])
if (low[v] > lbl[w])
low[v] = lbl[w];
}
if (low[v] == lbl[v]) {
bconta++;
printf("%d-%d\n", parent[v], v);
}
}
Um grafo é aresta-biconexo (= edge-connected) ou 2-aresta-conexo se for conexo e não tiver pontes. Portanto, é preciso remover pelo menos duas arestas de um grafo aresta-biconexo para que ele deixe de ser conexo.
Fato básico importante: Um grafo é aresta-biconexo se e somente se, para cada par (s,t) de seus vértices, existem (pelo menos) dois caminhos de s a t sem arestas em comum.
Uma componente aresta-biconexa (= edge-connected component) de um grafo é qualquer componente do grafo que se obtém depois que todas as pontes são removidas.
8-9 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4 .
(Adote a representação por listas de adjacência e insira as arestas, na ordem dada, num grafo inicialmente vazio.) Execute a função all_bridges para encontrar todas as pontes do grafo. Encontre todos as componentes aresta-biconexas.