|
grafo dirigido ou grafo orientado |
um par (V,E)
onde V é um conjunto finito
e E é um conjunto
de pares ordenados de elementos de V
os elementos de V são chamados vértices e os de E são arcos ou arestas |
| ∇+(X) | o conjunto dos arcos que saem de um subconjunto X de V |
| ∇–(Y) | o conjunto dos arcos que entram em um subconjunto Y de V |
| conjunto-fonte | um subconjunto próprio e não-vazio X de V tal que ∇–(X) é vazio |
| conjunto-sorvedouro | um subconjunto próprio e não-vazio Y de V tal que ∇+(Y) é vazio |
| corte dirigido | qualquer conjunto de arcos da forma ∇+(X), onde X é um conjunto-fonte |
| dijunção |
um conjunto J de arcos tal que,
para cada dois vértices u e v,
existe um caminho de u a v
cujos arcos diretos (ou seja, arcos orientados "pra frente")
estão em J
um conjunto de arcos é uma dijunção se e somente se intercepta todos os cortes dirigidos |