Algoritmos para Grafos, via Sedgewick | Índice remissivo

Cortes e digrafos desconexos

A grosso modo, um digrafo é desconexo se for a união de dois ou mais digrafos "separados". A definição exata do conceito depende da ideia de corte, que discutimos a seguir.

Cortes

Um corte (= cut) em um digrafo é uma bipartição do conjunto de vértices do digrafo. Em outras palavras, um corte é um par de conjuntos, ambos não vazios, tal que todo vértice do digrafo pertence a um e apenas um dos conjuntos do par.

Dado um corte (X,X) de um digrafo, dizemos que um arco está no corte, ou atravessa o corte, se uma de suas pontas está em X e outra está em X. Um corte é vazio se nenhum arco o atravessa.

Considere, por exemplo, o digrafo definido pelos arcos a seguir.

     0-1 1-0 0-2 2-1 3-5 4-5

Cada linha da seguinte tabela define um corte. Em cada linha temos: primeiro os vértices de um conjunto X, depois os vértices do complemento X de X, e finalmente os arcos que atravessam o corte (X,X).

     0       1 2 3 4 5    0-1 1-0 0-2                           
     2 3       0 1 4 5    0-2 2-1 3-5
     0 1 2       3 4 5   
     0 1 2 5       3 4    3-5 4-5

O terceiro corte da tabela é vazio.

Digrafos conexos e desconexos

Um digrafo é conexo se não tem cortes vazios e é desconexo em caso contrário. Às vezes dizemos fracamente conexo (= weakly connected) no lugar de conexo. [O conceito de digrafo fortemente conexo é mais complexo e será discutido em outra ocasião.]

Portanto, um digrafo é fracamente conexo se, para toda bipartição (X,X) de seu conjunto de vértices, algum arco tem uma das pontas (a inicial ou a final) em X e a outra em X.

Exercícios 1

Para mostrar que um digrafo é desconexo, basta exibir um corte vazio. Como fazer para mostrar que um digrafo é (fracamente) conexo?
Como é possível determinar se um dado digrafo é (fracamente) conexo?

Grafos conexos

O conceito de conexão é particularmente importante em digrafos simétricos. Nesse caso, o "fracamente" é omitido: se um grafo não tem cortes vazios, dizemos simplesmente que ele é conexo (= connected). Assim, se X é um conjunto de vértices de um grafo conexo G então alguma aresta de G tem uma ponta em X e outra fora de X, a menos que X seja vazio ou contenha todos os vértices de G.

Exercícios 2

Faça uma lista de todos os cortes do grafo definido pelas arestas abaixo.
```
     0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5
```
Para cada corte, diga quais arestas atravessam o corte.
Faça uma lista de todos os subgrafos conexos do grafo definido pelo conjunto de arestas abaixo.
```
     0-1 0-2 0-3 1-3 2-3
```
Quais desses subgrafos são induzidos?