「有向非巡回グラフ」の版間の差分

編集の要約なし
m
[[File:Directed acyclic graph 3.svg|right|frame|有向非巡回グラフの例]]
'''有向非巡回グラフ'''、'''有向非循環グラフ'''、'''有向無閉路グラフ'''(ゆうこうひじゅんかいぐらふグラフ、{{lang-en-short|Directed acyclic graph, '''DAG'''}})とは、[[グラフ理論]]における[[閉路]]のない[[有向グラフ]]の事。有向グラフは頂点と有向辺(方向を示す[[矢印]]付きの辺)からなり、辺は頂点同士をつなぐが、ある頂点 v から出発し、辺をたどり、頂点 v に戻ってこないのが有向非巡回グラフである。<ref>{{citation|title=Graph theory: an algorithmic approach|first=Nicos|last=Christofides|publisher=Academic Press|year=1975|pages=170–174}}.</ref><ref>{{citation|title=Graphs: Theory and Algorithms|first1=K.|last1=Thulasiraman|first2=M. N. S.|last2=Swamy|publisher=John Wiley and Son|year=1992|isbn=978-0-471-51356-8|contribution=5.7 Acyclic Directed Graphs|page=118}}.</ref><ref>{{citation|title=Digraphs: Theory, Algorithms and Applications|first1=Jørgen|last1=Bang-Jensen|first2=|last2=|series=Springer Monographs in Mathematics|edition=2nd|publisher=Springer-Verlag|year=2008|isbn=978-1-84800-997-4|contribution=2.1 Acyclic Digraphs|pages=32–34}}.</ref>
 
有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は半[[順序集合|順序]]を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。[[トポロジカルソート]]を使うと、妥当な順序を手に入れることが出来る。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。また、有向非巡回グラフはイベント間の因果関係を表現することにも使える。さらに、有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。