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

m
編集の要約なし
(en:Directed acyclic graph 14:30, 17 November 2014‎ から翻訳)
 
m
'''有向非巡回グラフ'''、'''有向非循環グラフ'''、'''有向無閉路グラフ'''(ゆうこうひじゅんかいぐらふ、{{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>
 
有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は半[[順序集合|順序]]を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。[[トポロジカルソート]]を使うと、妥当な順序を手に入れることが出来る。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。また、有向非巡回グラフはイベント間の因果関係を表現することにも使える。さらに、有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。
 
無向グラフにおける対応する概念は森で、森は閉路のない無向グラフである。森から方向を選ぶと polytree と呼ばれる特殊な有向非巡回グラフを作ることが出来る。しかしながら、無向非巡回グラフ(森)に方向付けする方法では作れない有向非巡回グラフがあり、全ての無向グラフは acyclic orientation があるため、辺に方向付けると有向非巡回グラフになる。この理由から、directed acyclic graph と呼ぶよりも acyclic directed graph と呼ぶ方が正確である。
== 関連項目 ==
* [[グラフ理論]]
* [[トポロジカルソート]]
* [[ベイジアンネットワーク]]
 
791

回編集