Algoritmos em Grafos  |  Livros  |  WWW  |  Índice de Termos

 

Componentes

Um conjunto  X  de vértices é isolado se for, ao mesmo tempo, uma fonte e um sorvedouro. Há dois casos degenerados que vale a pena destacar: o conjunto de todos os vértices e o conjunto vazio são sempre isolados.

Um  componente  [acho que seria melhor dizer "pedaço"]  de um grafo é um conjunto isolado não vazio minimal. A definição parece complicada mas é simples, como passo a explicar. Digamos que  A  é o conjunto de todos os conjuntos isolados distintos do conjunto vazio.  Um elemento  X  de  A  é minimal se não contém algum outro elemento de  A . Portanto, um componente é um conjunto isolado que não inclui propriamente outro conjunto isolado, exceto o vazio.

Esta é uma boa ocasião para discutir, abstratamente, a diferença entre "minimal" e "mínimo". Digamos que eu tenho uma coleção  A  de conjuntos.  Um elemento  X  de  A  é minimal se não existe um elemento  X'  de  A  que seja subconjunto próprio de  X.  Um elemento  X  de  A  é mínimo se não existe um elemento  X'  de  A  menor que X, isto é, tal que  | X' | < | X |.

Exercícios

1. Prove que os componentes de um grafo são disjuntos dois a dois.

2. Quantos e quais são os componentes do grafo  random_graph (9,10,1,1,1,NULL,NULL,0,0,79)  definido no exemplo 1 do capítulo O que é um grafo??

3. Seja A uma coleção de conjuntos.  Mostre que todo elemento mínimo de A é minimal.  Mostre que a recíproca em geral não vale.

4. Seja A a coleção de todos os conjuntos isolados não vazios de um grafo.  É verdade que todo elemento minimal de A é mínimo?

5. Escreva uma função C que receba um grafo SGB e um conjunto de  X  de seus vértices e verifique se  X  é ou não isolado. Suponha que o conjunto  X  é dado por meio de um utility field:  v–>marca  vale  1  se  v  está em  X  e  0  em caso contrário.

6. Escreva uma função C que receba um grafo SGB e um conjunto de  X  de seus vértices e verifique se  X  é ou não um componente.  Suponha que o conjunto  X  é dado por meio de um utility field:  v–>marca  vale  1  se  v  está em  X  e  0  em caso contrário.

Cálculo dos componentes

Como representar os componentes de um grafo? Podemos atribuir um rótulo a cada vértice de tal forma que dois vértices tenham o mesmo rótulo se e só se pertencem ao mesmo componente. O seguinte algoritmo calcula tais rótulos:

1 2 3 4 5 6 7

para cada vértice v faça rótulo[v] = v para cada arco (v,w) faça alpha = rótulo[v] beta = rótulo[w] se alpha != beta então para cada vértice x faça se rótulo[x] == beta então rótulo[x] = alpha

Para entender o algoritmo, basta observar que no início de cada iteração, ou seja, a cada passagem pela linha 2, os rótulos identificam corretamente os componentes do grafo  (V,A'),  onde  V  é o conjunto de todos os vértices e  A'  o conjunto dos arcos já examinados.

No algoritmo acima, usamos vértices no papel de rótulos: para cada vértice  v  do grafo,  rótulo[v]  é o "vértice-mestre" do componente que contém  v . Poderíamos igualmente bem ter usado números no papel de rótulos.

O algoritmo poderia ser chamado slow-union-quick-find; ele é exaustivamente discutido na seção 1.2 do livro Algorithms in C (3rd.ed.) de Robert Sedgewick. Na seção 1.3, o livro oferece um alternativa melhor (quick-union-slow-find), depois outra ainda melhor (weighted version), e finalmente uma excelente (with path compression).

Esse algoritmo de identificação de componentes é a base do célebre algoritmo de Kruskal, implementado no módulo MILES_SPAN do SGB. A implementação é ligeiramente diferente das de Sedgewick: ela mantém todos os vértices de um mesmo componente em uma lista circular (veja blocos 16 a 18 do módulo MILES_SPAN e também blocos 3 e 4 do módulo WORD_COMPONENTS).

Exercícios

7. Escreva uma função que receba um grafo SGB e devolva o seu número de componentes. Sugestão: para armazenar o rótulo de um vértice, use um dos utility fields de vértices. Use um algoritmo melhor que o indicado acima: experimente as sugestões do SGB e as do Sedgewick. 

A propósito, veja a tarefa de programação A.