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

削除された内容追加された内容

インライン

2019年7月27日 (土) 10:44時点における版

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

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

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

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

外部リンク

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日閲覧。
^ “詐欺呼ばわりされたこともあったが、次第に注目度を増す異色の草コイン「ADK」とは？”. ハーバービジネスオンライン. 2019年6月30日閲覧。

この項目は、組合せ数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。

[1] Christofides, Nicos (1975), Graph theory: an algorithmic approach, Academic Press, pp. 170–174, ISBN 9780121743505 .

[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日閲覧。

[8] “詐欺呼ばわりされたこともあったが、次第に注目度を増す異色の草コイン「ADK」とは？”. ハーバービジネスオンライン. 2019年6月30日閲覧。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ 21行目: / 21行目: @@
 {{データ構造}}
-{{math-stub}}
+{{Combin-stub}}
 {{DEFAULTSORT:ゆうこうひしゆんかいくらふ}}
 [[Category:グラフ理論]]

2019年7月27日 (土) 10:44時点における版

関連項目

外部リンク

参照