\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Directed Paths
Needed by:
Directed Acyclic Graph Ancestry Partial Order
Ordered Undirected Graph Orientations
Sheet PDF
Graph PDF

Directed Acyclic Graphs


If a directed graph has no cycles, then it has a nice property.1


Directed and acyclic graphs (or directed acyclic graphs, DAGs) have partial ordering property on vertices. We call a vertex $s$ an ancestor of a vertex $u$ if there is a directed path from $s$ to $u$.

Partial Order

We call a vertex $s$ and ancestor of a vertex $t$ if there is a directed path from $s$ to $t$. The relation $R$ defined by $(s, t) \in R$ if $s$ is an ancestor of $t$ is a partial order.

Clearly, every subgraph induced on a directed acyclic graph is a directed acyclic graph.

Let $(V, E)$ be a directed acyclic graph. Then there exists a vertex $v \in V$ which is a source and a vertex $w \in V$ which is a sink.
There exists a directed path of maximum length. It must start at a source and end at a sink.2

Topological numbering

We can choose a total ordering that is consistent with the partial order of ancestry.

A topological numbering (or topological sort, topological ordering) of a directed graph $(V, E)$ is a numbering $\sigma : \set{1, \dots , \num{V}} \to V$ satisfying

\[ (v, w) \in E \implies \inv{\sigma }(v) < \inv{\sigma }(w). \]


There exists a topological sort for every acyclic graph.
Let $(V, F)$ be a directed acyclic graph. There exists a source vertex, $v_1$. Set $\sigma (1) = v_1$. Take the subgraph induced by $V - \set{v_1}$. It is directed acyclic, and so has a source vertex, $v_2$. Set $\sigma (2) = v_2$. Continue in this way.4

  1. Future editions will expand this vague introduction. ↩︎
  2. Future editions will expand. ↩︎
  3. Future editions will further explain this concept. ↩︎
  4. Future editions will clarify and expand. ↩︎
Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view