, i.e. → is a transitive relation. Hiding this fact so far could be considered a conscious obfuscation on my part.Complete DAGs
[DAG is just another TLA I don't approve of; it stands for "Directed Acyclic Graph .]
In a recent manuscript —in the literal sense of the word— : "Some properties of the relative converse" (March 1995), Tony Hoare plays with tetrahedra of which the edges may be directed. (As by-product of his considerations he finds, for instance, that "any non-cyclic ascription of directions to any five of the edges can be non-cyclically extended to the sixth edge.") Here is a little bit of related theory.
* *
*
Let K be the complete graph with n vertices, in which each edge has a direction. Then the following 3 statements are equivalent
(i) K contains no cyclic paths
(ii) K contains no cyclic paths of length 3
(iii) the outdegrees of the vertices of K are the values 0 through n-1
The equivalences hold for n=1, since for n=1, (i), (ii), and (iii) are all true. For general n, the proof proceeds by mathematical induction. The induction step itself is done by cyclic implication: we now consider the complete (n+1)-graph K' with directed edges, and observe for it
(i) ⇒ (ii)
This follows —independently of the induction hypothesis— from the fact that "of length 3" is a restriction.
(ii) ⇒ (iii)
Let A be of K' a vertex of maximum outdegree; let K be the n-graph that remains after removal of A and its n connecting edges. Because of (ii), also K contains no cycles of length 3 and, ex hypothese, the outdegrees of its vertices are the values 0 through n-1; consequently we are done when we show that A has outdegree n (note that then the vertices of K have the same outdegree in K as in K').
Let B be the vertex with outdegree n-1 in K; since, by construction, A is not a vertex of K, A and B are different vertices. We now first deal with
the edge AB, and then with the remaining edges connecting A to K.
The direction of edge AB is A→B for the assumption B→A leads to a contradiction: then B would have in K' the (maximum) outdegree n, and so would A (by virtue of how it has been chosen: outdegree A ≥ outdegree B), but in the directed complete (n+1)-graph, at most 1 vertex has the maximum outdegree n.
Let C be a third vertex; then, because C is a vertex of K, in which B has the maximal outdegree n-1, the direction of edge BC is B→C. From A→B, B→C, and the absence of cycles of length 3 in K', we conclude that the direction of AC is A→C. (Note that, so far, we had only used the absence of cycles in K.) Hence, A has outgoing edges only, quod erat demonstrandum.
(iii) ⇒ (i)
Assume (iii) for K'; let A be the vertex of maximum outdegree n; let K be the n-graph that remains after removal of A and its n connecting edges. Possible cyclic paths in K' are then of two kinds, either they include A, or they lie in K.
Because A has outgoing edges only, no cyclic path leads through it; because of assumption (iii) for K' and of the fact that A has outgoing edges only, we conclude (iii) for K and, ex hypothese, that no cyclic paths lie in K. So, K' contains no cyclic paths, quod erat demonstrandum.
* *
*
The absence of cyclic paths in the complete graph tells us —with apologies for the picture!— that each triangle is of the form , i.e. → is a transitive relation. Hiding this fact so far could be considered a conscious obfuscation on my part.
Austin, 29 March 1995
prof. dr. Edsger W. Dijkstra
Department of Computer Sciences
The University of Texas at Austin
Austin, TX 78712-1188
USA
transcribed by Joel Neely
revised Fri, 14 Mar 2008