DAG)とは、グラフ理論における閉路のない有向グラフのことである。戻ってこないのが有向非巡回グラフである[1][2][3]。有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は半順序を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。トポロジカルソートを使うと、妥当な順序を手に入れることができる。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。有向非巡回グラフはイベント間の因果関係を表現することにも使える。有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。無向グラフにおける対応する概念は森で、森は閉路のない無向グラフである。森から方向を選ぶとpolytreeと呼ばれる特殊な有向非巡回グラフを作ることができる。orientationがあるため、辺に方向付けると有向非巡回グラフになる。graphと呼ぶ方が正確である。有向非巡回グラフをプロトコルとした仮想通貨には、BYTEBALL、IOTA、ADKがある[4][5][6][7][8]。2018年1月29日閲覧。“ブロックチェーンではない新技術・DAGで構築される暗号通貨、Byteballとは。2018年1月29日閲覧。Byteballとは。2018年1月29日閲覧。2018年1月29日閲覧。R木グラフ有向グラフ有向非巡回グラフ二分決定グラフハイパーグラフカテゴリこの項目は、組合せ数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。(日時は個人設定で未設定ならばUTC)。表示-継承ライセンスの下で利用可能です。追加の条件が適用される場合があります。詳細は利用規約を参照してください。Cookieに関する声明モバイルビュ。