|
directed graph or digraph |
a pair (V,E)
where V is a finite set
and E is a set of
ordered pairs of elements of V
the elements of V are called vertices and those of E are arcs or edges |
| ∇+(X) | the set of arcs leaving a subset X of V |
| ∇–(Y) | the set of arcs entering a subset Y of V |
| source-set | a non-empty proper subset X of V such that ∇–(X) is empty |
| sink-set | a non-empty proper subset Y of V such that ∇+(Y) is empty |
| dicut | a set of arcs of the form ∇+(X), where X is a source-set |
| dijoin |
a set J of arcs having the following property:
for any two vertices u and v,
there exists a path from u to v
whose forward-directed arcs are in J
a set of arcs is a dijoin if and only if it intersects all the dicuts |