Algoritmos para Grafos, via Sedgewick | Índice remissivo
Esta página trata de grafos (ou seja, digrafos simétricos) que deixam de ser conexos quando perdem uma de suas arestas. Vamos nos restringir 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.
Para resolver o problema, pode-se aplicar cegamente a definição de ponte. Mas é possível fazer coisa mais eficiente. O primeiro passo nessa direção é o seguinte fato básico: em qualquer grafo,
uma aresta é uma ponte se e somente se ela não pertence a 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.
0-1 1-2 2-0 1-3 1-4 4-5 5-6 6-4
Cada aresta de um grafo é um par de arcos antiparalelos. Se o par de arcos v-w e w-v é uma ponte, diremos que cada arco do par faz parte da ponte. Se fizermos uma busca em profundidade no grafo, um dos dois arcos que fazem parte de uma ponte será necessariamente um arco de arborescência (por que?). Portanto, basta conferir os arcos da floresta DFS. 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 de uma ponte se e somente se o único arco de retorno que liga um descendente de w a um ancestral de v é o arco w-v.
Essa propriedade permite determinar todas as pontes do grafo com uma única busca DFS. Para fazer isso, é preciso introduzir a ideia de menor número de pré-ordem acessível a partir de um vértice.
Vermelho: floresta DFS.
Roxo: arcos descendentes.
Verde: arcos de retorno.
[Copiado dos slides de José Coelho de Pina, 2011.]
Tome uma floresta DFS no grafo e considere a numeração dos vértices em pré-ordem. Para tirar proveito da propriedade acima, vamos calcular, para cada vértice v, o menor número de pré-ordem (= lowest preorder number) que pode ser alcançado a partir de v usando qualquer arco de retorno exceto o arco-pai de v (ou seja, o arco de retorno que vai de v ao pai de v). Esse número será denotado por
low[v].
Explico melhor: Digamos, para efeito desta explicação, que um caminho com origem v é interessante se
(No caso 3, o último arco do caminho é fatalmente diferente do arco-pai de v.) Por exemplo, o caminho de comprimento 0 de v a v é interessante. Outro exemplo: se v-w é um arco de retorno e w é diferente do pai de v então o caminho v-w é interessante. Mais um exemplo: se v-w é um arco da floresta DFS e w-x é um arco de retorno então o caminho v-w-x é interessante (mesmo que x seja o pai de v).
Digamos agora que o valor de um caminho interessante é o número de pré-ordem do último vértice do caminho. Podemos dizer então que
low[v] é o valor de um caminho interessante de valor mínimo.
É claro que low[v] ≤ pre[v] para todo vértice v, sendo pre[v] o número de pré-ordem de v. Além disso, para todo arco v-w do grafo,
Essas observações permitem calcular low recursivamente (ao mesmo tempo que pre e o vetor de pais). É o que faremos abaixo.
Considere o grafo com vértices a b c d e f g h i j definido pelas listas de adjacência a seguir.
a: b
b: e c a
c: j e d b
d: e c
e: h g f d c b
f: g e
g: f e
h: j i e
i: h
j: h c
Uma busca DFS produz a seguinte floresta DFS (veja vetor parent) e numeração em pré-ordem (veja vetor pre):
v a b c d e f g h i j
parent[v] a a j c b g e e h h
pre[v] 0 1 5 6 2 9 8 3 7 4
Segue uma figura da floresta DFS (que tem uma só arborescência) e uma cópia da figura que mostra os números pre dos vértices. Os arcos de retorno, que não aparecem nas figuras, são c-b c-e d-e f-e .
a (0)
| |
b (1)
| |
e (2)
/ \ / \
h g (3) (8)
/ \ \ / \ \
j i f (4) (7) (9)
/ /
c (5)
/ /
d (6)
Eis o menor número pre ao alcance de cada vértice v:
v a b c d e f g h i j
low[v] 0 1 1 2 1 2 2 1 7 1
A seguir, os caminhos interessantes que explicam os valores de low:
a
b
c-b
d-e
e-h-j-c-b
f-e
g-f-e
h-j-c-b
i
j-c-b
Considere o grafo definido pela lista de arestas: 0-2 0-3 2-3 2-8 3-8 8-1 8-10 10-4 10-7 4-7 4-9 9-5 9-6 5-6 . Uma busca DFS no grafo produz a numeração pre dada a seguir.
v 0 1 2 3 4 5 6 7 8 9 10
pre[v] 0 4 1 2 6 8 9 10 3 7 5
A correspondente floresta DFS é indicada pelos arcos vermelhos na figura.
O vetor low a seguir dá o menor pre ao alcance de cada vértice.
v 0 1 2 3 4 5 6 7 8 9 10
low[v] 0 4 0 0 5 7 7 5 1 7 5
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 pre definido pela busca. Exiba o vetor low associado à floresta DFS.
A propriedade acima pode ser reformulada assim: em qualquer floresta DFS de um grafo, um arco v-w da floresta faz parte de uma ponte se e somente se low[w] é igual a pre[w]. Com essa observação, é possível encontrar todas as pontes de um grafo com uma única busca em profundidade.
/* Nosso grafos terão no máximo maxV vértices. */
static int conta, pre[maxV], numpts, low[maxV]; static Vertex parent[maxV];/* A função abaixo calcula e devolve o número de pontes do grafo G. Também imprime todas as pontes. (O código foi inspirado no programa 18.7, p.108, de Sedgewick.) */
int GRAPHbridges( Graph G) { Vertex v; conta = numpts = 0; for (v = 0; v < G->V; v++) pre[v] = -1; for (v = 0; v < G->V; v++) if (pre[v] == -1) { parent[v] = v; bridgeR( G, v); } return numpts; }void bridgeR( Graph G, Vertex v) { link p; pre[v] = conta++; low[v] = pre[v]; for (p = G->adj[v]; p != NULL; p = p->next) { Vertex w = p->w; if (pre[w] == -1) { parent[w] = v; bridgeR( G, w); if (low[v] > low[w]) low[v] = low[w]; if (low[w] == pre[w]) { numpts++; printf( "%d-%d\n", v, w); } } else if (w != parent[v] && low[v] > pre[w]) low[v] = pre[w]; } }
Como muitas outros algoritmos baseados em busca em profundidade, a função GRAPHbridges é linear: ela consome tempo proporcional a V+E quando aplicada a um grafo com V vértices e E arestas. A variante dessa função para matrizes de adjacência consome tempo proporcional a V2.
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
0-6 0-1 0-5 1-2 2-6 3-5 4-5 4-11 4-9 4-3 6-7 7-8 7-10 9-11 10-8 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 floresta DFS do grafo.
void bridgeR( Graph G, Vertex v) {
link p;
pre[v] = conta++;
low[v] = pre[v];
for (p = G->adj[v]; p != NULL; p = p->next) {
Vertex w = p->w;
if (pre[w] == -1) {
parent[w] = v;
bridgeR( G, w);
if (low[v] > low[w]) low[v] = low[w];
}
else if (w != parent[v] && low[v] > pre[w])
low[v] = pre[w];
}
if (low[v] == pre[v]) {
numpts++;
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. (Portanto, grafos desse tipo são "tolerantes a falhas".)
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 GRAPHbridges para encontrar todas as pontes do grafo. Encontre todos as componentes aresta-biconexas.
