Esta página discute uma importante bipartição do conjunto dos arcos de qualquer digrafo. Essa bipartição ajuda a entender a estrutura de componentes fortes do digrafo.
Para qualquer conjunto X de vértices de um digrafo, o leque de saída de X é o conjunto de todos os arcos que têm ponta inicial em X e ponta final fora de X. O leque de entrada de X é definido de maneira análoga. O leque de saída de X será denotado por Ls(X) e o leque de entrada será denotado por Le(X). (Muitos livros dizem "corte" no lugar do meu "leque" e escrevem δ+(X) ou ∇+(X) no lugar do meu Ls(X) e δ−(X) ou ∇−(X) no lugar do meu Le(X).)
Se V é o conjunto de todos os vértices do digrafo, é evidente que Ls(X) = Le(V−X) e Le(X) = Ls(V−X) para toda parte X de V.
Um conjunto-fonte é qualquer conjunto X de vértices tal que Le(X) é vazio. Um conjunto-sorvedouro é qualquer conjunto X de vértices tal que Ls(X) é vazio. É claro que X é um conjunto-sorvedouro se e somente se V−X é um conjunto-fonte. O conjunto vazio e o conjunto de todos os vértices são conjuntos-fonte e também conjuntos-sorvedouro. Esses dois conjuntos são considerados triviais.
É claro que um vértice v é uma fonte se o conjunto unitário {v} é um conjunto-fonte e é um sorvedouro se {v} é um conjunto-sorvedouro.
Um corte orientado é qualquer conjunto da forma Ls(X) onde X é um conjunto-fonte. Equivalentemente, um corte orientado é qualquer conjunto da forma Le(Y) onde Y é conjunto-sorvedouro.
Não é difícil verificar o seguinte "teorema da dicotomia":
Teorema: Em qualquer digrafo, todo arco pertence a um ciclo ou a um corte orientado mas não a ambos.
É fácil decidir se um dado arco uv de um digrafo D é de ciclo ou de corte: se u está no território de v então o arco uv é de ciclo; caso contrário, uv é de corte.
Diante do que discutimos acima, é natural fazer as seguintes perguntas:
Os digrafos do primeiro tipo são, precisamente, os digrafos acíclicos. Quanto ao segundo tipo, todo digrafo fortemente conexos é certamente do segundo tipo, embora a recíproca não seja verdadeira. Um digrafo do segundo tipo é fortemente conexo desde que seja fracamente conexo (a noção de conexão fraca será definida na próxima seção).
Essa discussão ajuda a entender a estrutura do dag dos componentes fortes de um digrafo: todo arco de ciclo tem ambas as pontas num mesmo componente forte e todo arco de corte tem pontas em componentes fortes distintos. Reciprocamente, todo arco com ambas as pontas num mesmo componente forte é de ciclo e todo arco com pontas em componentes fortes distintos é de corte.
Um conjunto X de vértices é isolado se for, ao mesmo tempo, um conjunto-fonte e um conjunto-sorvedouro. Em outras palavras, X é isolado se o seu leque de entrada e o seu leque de saída são ambos vazios. O conjunto de todos os vértices e o conjunto vazio são obviamente isolados.
Um digrafo é conexo (diz-se também fracamente conexo) se seus únicos conjuntos isolados são o vazio e o conjunto de todos os vértices.
Um componente (há quem diga componente fraco) de um digrafo é um conjunto isolado não vazio minimal. (A definição não é tão complicada quanto parece, como passo a explicar. Digamos que X é o conjunto de todos os conjuntos isolados não vazios. Um elemento X de X é minimal se não contém algum outro elemento de X. Portanto, um componente é um conjunto isolado não vazio que não inclui propriamente outro conjunto isolado não vazio.) Tal como definido, um componente é um conjunto de vértices. Mas é conveniente, às vezes, confundir um componente X com o digrafo (X,B), onde B é o conjunto de todos os arcos que têm ambas as pontas em X.