「有向非巡回グラフ」の版間の差分
削除された内容 追加された内容
Solareenlo (会話 | 投稿記録) 編集の要約なし |
ARAKI Satoru (会話 | 投稿記録) lk, isbn, mathworld |
||
| 1行目: | 1行目: | ||
[[File:Directed acyclic graph 3.svg|right|frame|有向非巡回グラフの例]] |
[[File:Directed acyclic graph 3.svg|right|frame|有向非巡回グラフの例]] |
||
'''有向非巡回グラフ'''、'''有向非循環グラフ'''、'''有向無閉路グラフ'''（ゆうこうひじゅんかいグラフ、{{lang-en-short|Directed acyclic graph, '''DAG'''}}）とは、[[グラフ理論]]における[[閉路]]のない[[有向グラフ]]の事。有向グラフは頂点と有向辺（方向を示す[[矢印]]付きの辺）からなり、辺は頂点同士をつなぐが、ある頂点 v から出発し、辺をたどり、頂点 v に戻ってこないのが有向非巡回グラフである |
'''有向非巡回グラフ'''、'''有向非循環グラフ'''、'''有向無閉路グラフ'''（ゆうこうひじゅんかいグラフ、{{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|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>。 |
||
有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は半[[順序集合|順序]]を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。[[トポロジカルソート]]を使うと、妥当な順序を手に入れることが出来る。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。また、有向非巡回グラフはイベント間の因果関係を表現することにも使える。さらに、有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。 |
有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は半[[順序集合|順序]]を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。[[トポロジカルソート]]を使うと、妥当な順序を手に入れることが出来る。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。また、有向非巡回グラフはイベント間の因果関係を表現することにも使える。さらに、有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。 |
||
| 12行目: | 12行目: | ||
* [[トポロジカルソート]] |
* [[トポロジカルソート]] |
||
* [[ベイジアンネットワーク]] |
* [[ベイジアンネットワーク]] |
||
== 外部リンク == |
|||
* {{MathWorld|title=Acyclic Digraph|urlname=AcyclicDigraph}} |
|||
== 参照 == |
== 参照 == |
||
2019年3月27日 (水) 18:55時点における版
有向非巡回グラフ、有向非循環グラフ、有向無閉路グラフ（ゆうこうひじゅんかいグラフ、英: Directed acyclic graph, DAG）とは、グラフ理論における閉路のない有向グラフの事。有向グラフは頂点と有向辺（方向を示す矢印付きの辺）からなり、辺は頂点同士をつなぐが、ある頂点 v から出発し、辺をたどり、頂点 v に戻ってこないのが有向非巡回グラフである[1][2][3]。
有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は半順序を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。トポロジカルソートを使うと、妥当な順序を手に入れることが出来る。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。また、有向非巡回グラフはイベント間の因果関係を表現することにも使える。さらに、有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。
無向グラフにおける対応する概念は森で、森は閉路のない無向グラフである。森から方向を選ぶと polytree と呼ばれる特殊な有向非巡回グラフを作ることが出来る。しかしながら、無向非巡回グラフ（森）に方向付けする方法では作れない有向非巡回グラフがあり、全ての無向グラフは acyclic orientation があるため、辺に方向付けると有向非巡回グラフになる。この理由から、directed acyclic graph と呼ぶよりも acyclic directed graph と呼ぶ方が正確である。
なお、有向非巡回グラフをプロトコルとした仮想通貨に、BYTEBALL、IOTAがある[4][5][6][7]。
関連項目
外部リンク
- Weisstein, Eric W. "Acyclic Digraph". mathworld.wolfram.com (英語).
参照
- ^ Christofides, Nicos (1975), Graph theory: an algorithmic approach, Academic Press, pp. 170–174, ISBN 9780121743505.
- ^ Thulasiraman, K.; Swamy, M. N. S. (1992), “5.7 Acyclic Directed Graphs”, Graphs: Theory and Algorithms, John Wiley and Son, p. 118, ISBN 978-0-471-51356-8.
- ^ Bang-Jensen, Jørgen (2008), “2.1 Acyclic Digraphs”, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics (2nd ed.), Springer-Verlag, pp. 32–34, ISBN 978-1-84800-997-4.
- ^ “仮想通貨の未来はDAGコインにあり？ブロックチェーンに代わる技術に注目”. Cointelegraph. 2018年1月29日閲覧。
- ^ “ブロックチェーンではない新技術・DAGで構築される暗号通貨、Byteballとは。そのビジョンなど。”. Think Nomad. 2018年1月29日閲覧。
- ^ “DAGベースの暗号通貨 Byteballとは。”. Byteballの未来. 2018年1月29日閲覧。
- ^ “Byteball — smart payments made simple”. 2018年1月29日閲覧。
 | この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。 |