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

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

インライン

2020年12月21日 (月) 16:47時点における版

有向非巡回グラフ、有向非循環グラフ、有向無閉路グラフ（ゆうこうひじゅんかいグラフ、英: 英: 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]。

参照

[脚注の使い方]

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

外部リンク

Weisstein, Eric W. "Acyclic Digraph". mathworld.wolfram.com (英語).

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

[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]

@@ 1行目: / 1行目: @@
 [[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>。
+'''有向非巡回グラフ'''、'''有向非循環グラフ'''、'''有向無閉路グラフ'''（ゆうこうひじゅんかいグラフ、[[英語|英]]: {{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>。
 有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は[[半順序]]を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。[[トポロジカルソート]]を使うと、妥当な順序を手に入れることができる。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。また、有向非巡回グラフはイベント間の因果関係を表現することにも使える。さらに、有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。
@@ 7行目: / 7行目: @@
 なお、有向非巡回グラフをプロトコルとした[[仮想通貨]]には、[[BYTEBALL]]、[[IOTA (暗号通貨)|IOTA]]、ADKがある<ref>{{Cite web|url=https://jp.cointelegraph.com/news/future-of-digital-currency-may-not-involve-blockchains |title=仮想通貨の未来はDAGコインにあり？ブロックチェーンに代わる技術に注目 |publisher=Cointelegraph |accessdate=2018-1-29 |rel=harv}}</ref><ref>{{Cite web|url=https://junyahirano.com/archives/1710 |title=ブロックチェーンではない新技術・DAGで構築される暗号通貨、Byteballとは。そのビジョンなど。 |publisher=Think Nomad |accessdate=2018-1-29 |rel=harv}}</ref><ref>{{Cite web|url=http://www.byteballjp.com/entry/whatisbyteball |title=DAGベースの暗号通貨 Byteballとは。 |publisher=Byteballの未来 |accessdate=2018-1-29 |rel=harv}}</ref><ref>{{Cite web|url=https://byteball.org/ |title=Byteball — smart payments made simple |accessdate=2018-1-29 |rel=harv}}</ref><ref>{{Cite web|title=詐欺呼ばわりされたこともあったが、次第に注目度を増す異色の草コイン「ADK」とは？|url=https://hbol.jp/172517|website=ハーバービジネスオンライン|date=|accessdate=2019-06-30|language=|publisher=}}</ref>。
+== 参照 ==
+{{脚注ヘルプ}}
+{{reflist}}
 == 関連項目 ==
@@ 16行目: / 20行目: @@
 * {{MathWorld|title=Acyclic Digraph|urlname=AcyclicDigraph}}
+{{Graph Theory-footer}}
-== 参照 ==
-{{reflist}}
 {{データ構造}}
 {{Combin-stub}}
 {{DEFAULTSORT:ゆうこうひしゆんかいくらふ}}
 [[Category:グラフ理論]]

表話編歴グラフ理論
要素・定義・表現	頂点辺（英語版）グラフ無向有向ラベル付き（英語版）重み付き（英語版）ハイパーグラフ接続行列隣接行列隣接リスト
指標	位数（英語版）サイズ（英語版）次数次数行列距離（英語版）半径直径内周 (頂点)彩色数辺彩色数（英語版）点連結度辺連結度交叉数（英語版）
部分構造	ループ（英語版）多重辺（英語版）部分グラフ（英語版）誘導部分グラフ道閉道連結成分（英語版）強連結成分（英語版）橋（英語版）カットクリーク独立集合支配集合（英語版）マッチングオイラー路シュタイナー木全域木ハミルトン路
全体構造	連結グラフ正則グラフ立方体グラフケージ強正則グラフ木平面グラフ 2部グラフ有向非巡回グラフ弦グラフムーアグラフパーフェクトグラフ対称グラフ半対称グラフ頂点推移グラフ辺推移グラフ距離推移グラフ補グラフ双対グラフグラフ同型
固有名を持つグラフ	パスグラフ（英語版） $P n$ 閉路グラフ $C n$ 完全グラフ $K n$ 完全2部グラフ $K m, n$ スター $S n = K 1, n$ 車輪グラフ $W n$ 空グラフピーターセングラフヒーウッドグラフマギーグラフホフマンシングルトングラフフォークマングラフ
トピック・定理	一筆書きオイラーの多面体定理クラトフスキの定理四色定理五色定理ケイリーの公式プリューファー列最短経路問題巡回セールスマン問題中国人郵便配達問題ダイクストラ法ベルマン-フォード法ワーシャル-フロイド法ハミルトン閉路問題最大クリーク問題頂点被覆問題最小頂点被覆問題最大独立集合問題最大流最小カット定理支配集合問題次数直径問題安定結婚問題
カテゴリ / コモンズ