Algoritmos para Grafos, via Sedgewick | Índice remissivo
A grosso modo, um digrafo é conexo se for "união disjunta" de dois digrafos menores. A definição precisa do conceito depende da ideia de corte. No caso de grafos (ou seja, digrafos simétricos), a caracterização da conexão envolve a ideia de caminho, a ser introduzida em outra página.
Um corte (= cut) de um digrafo é uma bipartição do conjunto de vértices do digrafo. Em outras palavras, um corte é um par de conjuntos de vértices, 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,Y) de um digrafo, dizemos que um arco pertence ao corte, ou atravessa o corte, se tiver uma ponta em X e outra em Y. Um corte é vazio se não for atravessado por nenhum arco.
Considere, por exemplo, o digrafo definido pelos arcos abaixo.
0-1 1-0 0-2 2-1 3-5 4-5
A tabela lista alguns cortes (com X na primeira coluna e Y na segunda) e os arcos que atravessam esses cortes:
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 segundo corte da tabela é vazio.
Um digrafo é fracamente conexo (= weakly connected) se não tem cortes vazios. [A propósito, 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,Y) de seu conjunto de vértices, algum arco tem uma ponta em X e outra em Y.
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.
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.
0-1 0-2 0-3 1-3 2-3
Quais desses subgrafos são induzidos?