有向非巡回グラフ

有向非巡回グラフ（DAG）とは

有向非巡回グラフ（Directed Acyclic Graph, DAG）とは、グラフ理論における基本的な概念の一つで、閉路（サイクル）を持たない有向グラフのことです。有向グラフは、頂点と有向辺（方向を示す矢印付きの辺）から構成され、辺は頂点同士をつなぎます。DAGでは、ある頂点から出発して辺をたどり、再び元の頂点に戻ることができません。この特徴から、DAGは様々な情報をモデル化するのに役立ちます。

定義

頂点（vertex）: グラフを構成する要素で、オブジェクトを表します。
辺（edge）: 2つの頂点を結ぶ線で、有向グラフでは方向を持ちます。
経路（path）: 辺の列で、各辺の終点が次の辺の始点と一致します。
サイクル（閉路）: 経路が最初の頂点に戻る場合、サイクルを形成します。
有向非巡回グラフ（DAG）: サイクルを持たない有向グラフ。

DAGでは、ある頂点vから別の頂点uへ向かう経路が存在する場合、uはvから到達可能であるといいます。また、全ての頂点は、辺がない経路によって自分自身に到達可能と見なされます。

数学的特性

到達可能性関係と半順序

DAGにおける到達可能性関係は、半順序として形式化できます。頂点uから頂点vへの有向パスが存在する場合、u ≤ vと順序づけられます。ただし、異なるDAGでも同じ半順序を持つ可能性があります。例えば、a → b、b → cという辺を持つDAGと、a → b、b → c、a → cという辺を持つDAGは、どちらもa ≤ b ≤ cという半順序を持ちます。

推移閉包と推移簡約

推移閉包: DAGの到達可能性関係を保持したまま、最も多くの辺を持つDAGです。頂点uからvに到達可能ならば、必ず辺u → vを持ちます。
推移簡約: DAGの到達可能性関係を保持したまま、最も少ない辺を持つDAGです。頂点uからvへのより長いパスがある場合、辺u → vは削除されます。

推移簡約は、半順序を視覚化する際に役立ちます。ハッセ図は、推移簡約を図示したもので、辺の方向を頂点の位置関係で示します。

DAGの応用

タスクの順序付け

タスクの集合を、実行順序の制約とともに表現する際にDAGが利用されます。タスクを頂点、制約条件を辺とすることで、DAGとして表現できます。トポロジカルソートを用いると、タスクの実行順序を決定できます。

シーケンスの表現

一部が重複するシーケンスの集合を表現する際に、DAGは空間効率の良い表現方法として利用できます。

因果関係の表現

イベント間の因果関係を表現する際にも、DAGが使われます。イベントを頂点、因果関係を辺として表現します。

データフローネットワーク

データの流れが一定方向のネットワークを表現するためにも、DAGが使われます。

その他の関連概念

無向グラフにおけるDAGの対応概念は森であり、森は閉路のない無向グラフです。森に方向を与えることで、polytreeと呼ばれる特殊なDAGを作成できます。ただし、すべてのDAGが森に方向付けすることで得られるわけではありません。このため、有向非巡回グラフを指す際には、"acyclic directed graph"（非巡回有向グラフ）という用語がより正確であるとされています。

関連項目

グラフ理論
トポロジカルソート
ベイジアンネットワーク

外部リンク

Weisstein, Eric W. "Acyclic Digraph". mathworld.wolfram.com (英語)
DAGitty – DAG をつくるためのオンラインツール

もう一度検索