
Apt,
Blair,
and
Walker
and if (p,q) is a negative edge, then the level assigned to q is strictly smaller
than that assigned to p. Thus, there are no cycles in the dependency graph
through a negative edge.
For the converse, decompose the dependency graph into strongly connected
components, each of maximum cardinality (i.e., such that any two nodes in a
component are connected in a cycle). Then the relation "there is an edge from
component G to component H" is well founded, since it is finite, and contains
no cycles. Thus, for some η the numbers
l,...,n
can be assigned to the com-
ponents so that if there is an edge from G to H, then the numbe ...