有向非巡回グラフ
グラフは、頂点(vertex)と、2 つの頂点を結ぶ辺(edge)によって形成される。頂点は、辺によってペアで接続されるあらゆる種類のオブジェクトである。 有向グラフの場合、各辺はある頂点から別の頂点への方向性を持つ。 有向グラフの経路(path)とは、各辺の終点となる頂点が次の辺の始点となる頂点と同じであるという性質を持つ辺の列である。 経路は、その最初の辺の始点となる頂点が最後の辺の終点となる頂点と同じであるとき、サイクル(閉路)を形成する。 有向非巡回グラフは、サイクルを持たない有向グラフのことである。
有向グラフの頂点 v は、頂点 u を始点とし頂点 v を終点とする経路が存在するとき、頂点 u から到達可能であるという。 特別な例として、すべての頂点は、自分自身から(辺がの数が 0 の経路によって)到達可能であると考えられる。 ある頂点が、非自明な経路(辺の数が 1 つ以上の経路)で自身に到達できる場合、その経路はサイクルである。 このため、どの頂点も非自明な経路では自身に到達できないグラフ、としても有向非巡回グラフを定義することができる。
有向非巡回グラフ、有向非循環グラフ、有向無閉路グラフ(ゆうこうひじゅんかいグラフ、英: Directed acyclic graph, DAG)とは、グラフ理論における閉路のない有向グラフのことである。有向グラフは頂点と有向辺(方向を示す矢印付きの辺)からなり、辺は頂点同士をつなぐが、ある頂点 v {\displaystyle v} から出発し、辺をたどり、頂点 v {\displaystyle v} に戻ってこないのが有向非巡回グラフである。
有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は半順序を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。