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

テンプレート挿入
m
タグ: モバイル編集 モバイルウェブ編集 改良版モバイル編集
(テンプレート挿入)
[[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>。
 
有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は[[半順序]]を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。[[トポロジカルソート]]を使うと、妥当な順序を手に入れることができる。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。また、有向非巡回グラフはイベント間の因果関係を表現することにも使える。さらに、有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。
 
なお、有向非巡回グラフをプロトコルとした[[仮想通貨]]には、[[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}}
 
== 関連項目 ==
* {{MathWorld|title=Acyclic Digraph|urlname=AcyclicDigraph}}
 
{{Graph Theory-footer}}
== 参照 ==
{{reflist}}
 
{{データ構造}}
 
{{Combin-stub}}
 
{{DEFAULTSORT:ゆうこうひしゆんかいくらふ}}
[[Category:グラフ理論]]