A grosso modo, um digrafo é conexo se for "união disjunta" de dois digrafos menores. A definição precisa do conceito depende da idéia de corte. No caso de grafos (ou seja, digrafos simétricos), a caracterização da conexão envolve a idéia de caminho.

Cortes

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.

Digrafos conexos

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.

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.

Referência: IME