Algoritmos para Grafos, via Sedgewick
|
Índice remissivo
Articulações e grafos biconexos
Esta página trata de
grafos que deixam de ser
conexos
quando perdem um de seus vértices.
Ela se restringe a grafos
(embora o conceito também faça sentido em
digrafos não simétricos).
[A página é um resumo da segunda parte da seção 18.6, p.106-114,
do livro de Sedgewick.]
Articulações em grafos
Uma
articulação
(= articulation point) ou
vértice de corte
(= cut vertex)
de um grafo
é um vértice cuja remoção aumenta
o número de componentes
do grafo.
Exercícios
-
Seja v-w uma
ponte em um grafo.
Suponha que v tem outro vizinho além de w.
Prove que v é uma articulação.
-
Prove ou desprove:
em qualquer árvore,
todos os vértices são articulações.
-
Use uma variante da função
GRAPHcc
para decidir se um grafo tem articulações.
(Sugestão: Marcar um vértice x com lbl[x]=0
antes do início da busca
tem o mesmo efeito que remover x do grafo.)
Sua função consumirá tempo proporcional
a V·(V+E).
-
[Sedgewick 18.36]
Faça um desenho da arborescência de busca em profundidade
do grafo
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.)
Use a arborescência para encontrar as articulações do grafo.
-
[Sedgewick 18.37]
Repita o exercício anterior
depois de representar o grafo por sua matriz de adjacência.
Algoritmo eficiente
É possível encontrar todas as articulações de um grafo
de maneira muito rápida:
basta usar uma variante apropriada da função
bridgeR
que calcula as pontes
de um grafo.
Exercício
-
Escreva uma função que imprima todas as articulações
de um grafo dado.
(Sugestão:
Modifique a função bridgeR.
A raiz da arborescência de busca deve receber cuidado especial:
ela é uma articulação
se e somente se tem dois ou mais filhos.)
Biconexão
Um grafo é
biconexo
(= biconnected)
ou
2-conexo
se é conexo e
não tem articulações.
Portanto,
é preciso remover pelo menos 2 vértices de um grafo biconexo
para que ele deixe de ser conexo.
Fato básico importante:
Um grafo é biconexo
se e somente se,
para cada par (s,t) de seus vértices,
existem (pelo menos) dois caminhos de s e t
sem vértices internos em comum
(ou seja, s e t
são os únicos vértices comuns aos dois caminhos).
Exercícios
-
Prove que todo grafo biconexo é
aresta-biconexo.
-
[Sedgewick 18.39]
Seja G um grafo biconexo.
Sejam s e t dois vértices de G.
Prove que existem dois caminhos de s e t
sem vértices internos em comum.
(Sugestão:
Tome um caminho de s a t.
Os vértices internos desse caminho não são articulações.
Use esse fato para construir dois caminhos de s a t
sem vértices internos em comum.)
-
[Sedgewick 18.44]
Qual o número mínimo de arestas que um grafo biconexo
com V vértices deve ter?
