Aqui trataremos 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).

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.

Algoritmo
código

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 para Fixação

1. Faça esse algoritmo para lista de adjacências.
2. Mostre que todo grafo biconexo é aresta-biconexo.
3. Qual o número mínimo de arestas que um grafo biconexo com V vértices deve ter?
4. Porque é importante identificar pontos de articulação? Dê uma situação prática.
5. Explique com suas palavras o que é um grafo biconexo.
6. Qual a diferença entre pontes e articulações?
7. Modifique o algoritmo acima para que ele somente diga se existe ponto de articulação ou não.

Referência: IME