有向非巡回グラフ

提供: miniwiki
移動先:案内検索
ファイル:Directed acyclic graph 3.svg
有向非巡回グラフの例

有向非巡回グラフ有向非循環グラフ有向無閉路グラフ(ゆうこうひじゅんかいグラフ、: Directed acyclic graph, DAG)とは、グラフ理論における閉路のない有向グラフの事。有向グラフは頂点と有向辺(方向を示す矢印付きの辺)からなり、辺は頂点同士をつなぐが、ある頂点 v から出発し、辺をたどり、頂点 v に戻ってこないのが有向非巡回グラフである。[1][2][3]

有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は半順序を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。トポロジカルソートを使うと、妥当な順序を手に入れることが出来る。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。また、有向非巡回グラフはイベント間の因果関係を表現することにも使える。さらに、有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。

無向グラフにおける対応する概念は森で、森は閉路のない無向グラフである。森から方向を選ぶと polytree と呼ばれる特殊な有向非巡回グラフを作ることが出来る。しかしながら、無向非巡回グラフ(森)に方向付けする方法では作れない有向非巡回グラフがあり、全ての無向グラフは acyclic orientation があるため、辺に方向付けると有向非巡回グラフになる。この理由から、directed acyclic graph と呼ぶよりも acyclic directed graph と呼ぶ方が正確である。

なお、有向非巡回グラフをプロトコルとした仮想通貨に、BYTEBALLIOTAがある[4][5][6][7]

関連項目

参照

  1. Christofides, Nicos (1975), Graph theory: an algorithmic approach, Academic Press, pp. 170–174 .
  2. 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 .
  3. 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 .
  4. 仮想通貨の未来はDAGコインにあり?ブロックチェーンに代わる技術に注目”. Cointelegraph. . 2018-1-29閲覧.
  5. ブロックチェーンではない新技術・DAGで構築される暗号通貨、Byteballとは。そのビジョンなど。”. Think Nomad. . 2018-1-29閲覧.
  6. DAGベースの暗号通貨 Byteballとは。”. Byteballの未来. . 2018-1-29閲覧.
  7. Byteball — smart payments made simple”. . 2018-1-29閲覧.

テンプレート:データ構造