----- > [!proposition] Proposition. ([[vertically ordering acyclic networks]]) > Every [[network|directed]] [[acyclic network]] can be drawn such that all edges point downward. The converse is also true. > ![[CleanShot 2023-09-14 at [email protected]]] > Moreover, the algorithm for doing this *tells us* whether our [[network]] is acyclic or not. > [!proof] Algorithm. ([[vertically ordering acyclic networks]]) > > It is obvious that any [[network]] that can be arranged so that all nodes face downward must not have cycles, so we'll focus only on one direction. > > Let $G$ be an [[acyclic network]] with $n$ nodes. Then $G$ must contain a node that has ingoing edges only and has no outgoing edges [^1]. Label that node [^2] *node 1*, and then remove it and its attached edges. We are left with a [[network]] of $n-1$ edges that is [[acyclic network|acyclic]], so we may repeat the process $n$ times in total, until all nodes have been removed. This yields an [[ordered set|ordering]] of the nodes of $G$. > \ > The rearrangement is then constructed by placing nodes in ascending order from bottom-to-top of the plane and drawing the directed edges between them [^3]. > \ > Here is the official algorithm for testing [[acyclic network|network acyclicity]]: > 1. Find a node with no outgoing edges; > 2. If no such node exists, the [[network]] is cyclic [^4] and we're done. Else remove the node and its edges; > 3. If all nodes have been removed, the [[network]] is [[acyclic network|acyclic]] and we're done. Else start over at step $1$. > [^1]: To see this, BWOC assume all nodes of $G$ with ingoing edges have outgoing edges. Then we may construct an indefinite 'walk' through $G$, following from ingoing-to-outgoing *ad infimum*. But this contradicts the fact that $G$ has $n$ nodes. [^2]: Breaking ties arbitrarily. [^3]: Since every node has outgoing edges only to nodes of lower index because it had no outgoing edges when it was removed from the network. [^4]: Because a given cycle in network contains nodes which all have an outgoing edge. ----- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```