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

m
編集の要約なし
(テンプレート挿入)
m
タグ: 2017年版ソースエディター
[[File:Directed acyclic graph 3.svg|right|frame|有向非巡回グラフの例]]
'''有向非巡回グラフ'''、'''有向非循環グラフ'''、'''有向無閉路グラフ'''(ゆうこうひじゅんかいグラフ、[[英語|英]]: {{lang-en-short|Directed acyclic graph, '''DAG'''}})とは、[[グラフ理論]]における[[閉路]]のない[[有向グラフ]]のことである。有向グラフは頂点と有向辺(方向を示す[[矢印]]付きの辺)からなり、辺は頂点同士をつなぐが、ある頂点<math>v</math>から出発し、辺をたどり、頂点<math>v</math>に戻ってこないのが有向非巡回グラフである<ref>{{citation|title=Graph theory: an algorithmic approach|first=Nicos|last=Christofides|publisher=Academic Press|year=1975|pages=170–174|isbn=9780121743505}}.</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={{google books quote|id=4kHN6uSinQoC|page=118|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={{google books quote|id=5GdXCWhE4-MC|page=32|32}}–34}}.</ref>。
 
有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は[[半順序]]を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。[[トポロジカルソート]]を使うと、妥当な順序を手に入れることができる。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。また、有向非巡回グラフはイベント間の因果関係を表現することにも使える。さらに、有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。