Algoritmos para Grafos | Índice
Este capítulo trata de grafos não-dirigidos que são robustos
no seguinte sentido:
o grafo permanece conexo mesmo quando qualquer um de seus vértices é removido.
Uma articulação (= articulation point) ou vértice de corte (= cut vertex) de um grafo não-dirigido é qualquer vértice que tenha grau pelo menos 2 e incida em duas arestas que não pertencem a um mesmo circuito.
Um vértice v é uma articulação se e somente se a remoção de v produz um grafo com mais componentes conexas que o grafo original. Essa observação permite decidir se um dado vértice é uma articulação. Esse algoritmo é consome tempo linear no tamanho do grafo.
Exemplo A. Considere o grafo não-dirigido representado na figura. O vértice 12 não é uma articulação pois tem grau menor que 2. O vértice 2 não é uma articulação pois as duas únicas arestas que incidem em 2 pertencem a um mesmo circuito. O vértice 4 é uma articulação pois as arestas 4-3 e 4-9 não pertencem a um mesmo circuito (embora as arestas 4-3 e 4-5, por exemplo, pertençam a um mesmo circuito). O grafo tem uma só componente conexa, mas a remoção do vértice 4, por exemplo, produziria um grafo com duas componentes. O mesmo pode ser dito dos vértices 0, 5, 6, 7 e 11. Os demais vértices não são articulações.
O problema das articulações. Embora possamos decidir rapidamente se um dado vértice de um grafo não-dirigido é uma articulação, o seguinte problema é mais difícil:
Problema: Encontrar todas as articulações de um grafo não-dirigido.
Para resolver o problema, pode-se aplicar cegamente a definição de articulação (ou seja, verificar, para cada vértice, se sua remoção aumenta o número de componentes conexas do grafo). Mas é possível fazer algo bem mais eficiente.
É possível encontrar todas as articulações de um grafo não-dirigido de maneira muito rápida: basta usar uma variante apropriada da função UGRAPHbridges3(), que calcula as pontes de um grafo. Os detalhes ficam a cargo do leitor.
Dois vértices s e t
estão biligados
se existem dois caminhos de s a t
sem vértices internos em comum.
A expressão sem vértices internos em comum
significa que
s e t são os dois únicos vértices comuns
aos dois caminhos.
Podemos dizer também que os dois caminhos são
internamente disjuntos
.
De acordo com essa definição, dois vértices adjacentes então estão biligados (pois se s e t são adjacentes então duas cópias do caminho s–t são internamente disjuntas). Da mesma forma, parece compatível com a definição dizer que todo vértice está biligado a si mesmo. Vamos procurar evitar esses dois casos extremos pois eles são um tanto estranhos e desconcertantes.
Vale lembrar que cada aresta consiste em dois arcos antiparalelos. Assim, o inverso de um caminho num grafo não-dirigido também é um caminho. Segue daí que dois vértices distintos e não-adjacentes estão biligados se e somente se pertencem a algum circuito simples.
Exemplo B. Considere o grafo não-dirigido representado na figura. Os vértices 0 e 2 estão biligados: os caminhos 0-6-2 e 0-1-2 ligam os dois vértices e são internamente disjuntos. Os vértices 5 e 11 não estão biligados (os caminhos 5-3-4-11 e 5-4-9-11 não são internamente disjuntos). Os vértices 0 e 8 também não estão biligados.
Um grafo não-dirigido é biconexo (= biconnected) ou 2-conexo se tem três ou mais vértices e cada dois vértices estão biligados (ou seja, pertencem a algum circuito simples). É claro que todo grafo biconexo é conexo.
(A restrição a grafos com 3 ou mais vértices é necessária. Sem ela, um grafo que tem apenas dois vértices e uma aresta seria considerado biconexo. Da mesma forma, um grafo com apenas um vértice também seria considerado biconexo. Esses casos extremos são desconcertantes e inconvenientes.)
Um grafo não-dirigido é biconexo se e somente se tem pelo menos 3 vértices, é conexo, e não tem articulações.
Um grafo não-dirigido é biconexo se e somente se permanece conexo depois da remoção de qualquer um de seus vértices. Assim, é preciso remover pelo menos 2 vértices de um grafo biconexo para que ele fique desconexo.
Uma componente biconexa
(= bloco
??)
de um grafo não-dirigido é um subgrafo ..........
John Hopcroft e Robert Tarjan descobriram (em 1973) um algoritmo muito eficiente para encontrar todas as componentes aresta-biconexas de um grafo não-dirigido. Não por acaso, o algoritmo é semelhante ao que calcula as componentes fortes de um grafo.