Esta página trata de uma interessante bipartição do conjunto dos arcos de qualquer digrafo. Essa bipartição ajuda a entender a estrutura de componentes fortes do digrafo.
O leque de saída (= fan-out) de um vértice v de um digrafo é o conjunto de todos os arcos que saem de v, ou seja, que têm ponta inicial v (e portanto ponta final diferente de v). O leque de entrada (= fan-in) de v é definido de maneira análoga. O leque de saída de v será denotado por Ls(v) e o leque de entrada será denotado por Le(v).
O grau de saída de um vértice v é a cardinalidade de
Ls(v)
e o grau de entrada é a cardinalidade de
Le(v).
Uma fonte (= source)
é qualquer vértice que tenha grau de entrada nulo.
Analogamente,
um sorvedouro (= sink)
(ou ralo
)
é qualquer vértice que tenha grau de saída nulo.
Para qualquer conjunto X de vértices de um digrafo,
o leque de saída (= fan-out)
de X
é o conjunto de todos os arcos que saem de X, ou seja,
que têm ponta inicial em X
e ponta final fora de X.
O leque de entrada (= fan-in)
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)
ou ∇+(X)
no lugar do meu Ls(X).
Também escrevem
∂−(X)
ou δ−(X)
ou ∇−(X)
no lugar do meu Le(X).)
É evidente que Ls(X) = Le(V−X) e Le(X) = Ls(V−X) para toda parte X do conjunto V de todos so vértices.
Um conjunto-fonte (= source-set) é qualquer conjunto X de vértices tal que Le(X) é vazio. Um conjunto-sorvedouro (= sink-set) é 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.
Um corte orientado (= directed cut) é 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 G é de ciclo ou de corte: se u está ao alcance 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 acíclicos. Quanto ao segundo tipo, todo digrafo fortemente conexo é certamente do segundo tipo, embora a recíproca não seja verdadeira. Um digrafo do segundo tipo é fortemente conexo desde que seja fracamente conexo, conforme a próxima seção.
Essa discussão ajuda a entender a estrutura do DAG das componentes fortes de um digrafo: todo arco de ciclo tem ambas as pontas numa mesma componente forte e todo arco de corte tem pontas em componentes fortes distintas. Reciprocamente, todo arco com ambas as pontas numa mesma componente forte é de ciclo e todo arco com pontas em componentes fortes distintas é 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 seu leque de entrada e 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 é fracamente conexo (= weakly connected) se seus únicos conjuntos isolados são o vazio e o conjunto de todos os vértices.
Uma componente fraca (= weak component) de um digrafo é um conjunto isolado não vazio minimal.
Tal como definido, uma componente é um conjunto de vértices. Mas é conveniente, às vezes, confundir uma componente X com o subdigrafo induzido por X.