= Order-induced acyclic orientation
Choose a <strict total order> $v_1<\cdots<v_n$ of the <vertices> of a finite <simple graph>. Direct every <edge> $v_iv_j$ from $v_i$ to $v_j$ when $i<j$. Along every <directed path>, the index strictly increases. Returning to the starting <vertex> would require an impossible strict increase back to the initial index, so this is an <acyclic orientation>. The displayed $D_1$ comes from $A<B<C$.
The chosen <strict total order> is a <topological order> of the resulting <Directed acyclic graph>. Conversely, every <acyclic orientation> of a finite <simple graph> has a <topological order>, and orienting its <edges> from earlier to later in that order recovers it. Different <topological orders> can induce the same <acyclic orientation>, since <vertices> with no <edge> between them need not impose a choice of arrow.<6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 14: Graphs II: Depth-First Search>[printed pp. 4–6: job scheduling, topological sorting and its edge-order correctness condition]{ref}
An order respects <reachability> but does not create it: $u<v$ in a chosen <topological order> does not imply a <directed path> from $u$ to $v$. For example, orient the two <edges> of the <graph path> $A,B,C$ using $A<C<B$. The arrows are $A\to B$ and $C\to B$; there is no <directed path> from $A$ to $C$, despite $A<C$. In $D_1$, however, $A$ reaches $C$ both directly and via $B$. Following outgoing <directed edges> with <graph search> decides this directional <reachability>.<6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 14: Graphs II: Depth-First Search>[printed pp. 1–2: directed adjacency lists contain outgoing edges; a search sees vertices reachable from its start]{ref}
Back to article page
