有向非巡回グラフ
トポロジカルソートを使うと、妥当な順序を手に入れることができる。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。また、有向非巡回グラフはイベント間の因果関係を表現することにも使える。さらに、有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。
無向グラフにおける対応する概念は森で、森は閉路のない無向グラフである。森から方向を選ぶとpolytreeと呼ばれる特殊な有向非巡回グラフを作ることができる。しかしながら、無向非巡回グラフ(森)に方向付けする方法では作れない有向非巡回グラフがあり、全ての無向グラフはacyclic orientationがあるため、辺に方向付けると有向非巡回グラフになる。この理由から、directed acyclic graphと呼ぶよりもacyclic directed graphと呼ぶ方が正確である。
DAG における到達可能性(英語版)関係は、 DAG の頂点の半順序 ≤ として形式化できる。 この半順序では、頂点 u と頂点 v は、DAG 内に u から v への有向パスが存在するとき、すなわち v が u から到達可能なときに、 u ≤ v として順序づけられる。 しかし、異なる DAG から、同じ到達可能性関係と同じ半順序集合が得られる場合もある。 例えば、2 つの辺 a → b、b → c を持つ DAG は、3 つの辺 a → b、b → c、a → c を持つ DAG と同じ到達可能性関係を持ち、どちらも頂点が a ≤ b ≤ c の順に並んだ半順序集合を持つ。
DAG G の推移閉包は、G と同じ到達可能性関係を表す DAG の中で、最も多くの辺を持つものである。 これは、頂点 u から v に到達できるときには必ず辺 u → v を持つ。 つまり、G の到達可能性関係において異なる要素の関連するペア u ≤ v は必ず辺を持つので、到達可能性関係 ≤ をグラフ理論的に直訳したものと考えてよい。