有向非巡回グラフのソースを表示

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

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

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

== 定義 ==
グラフは、頂点（vertex）と、2 つの頂点を結ぶ辺（edge）によって形成される。頂点は、辺によってペアで接続されるあらゆる種類のオブジェクトである。
有向グラフの場合、各辺はある頂点から別の頂点への方向性を持つ。
有向グラフの経路（path）とは、各辺の終点となる頂点が次の辺の始点となる頂点と同じであるという性質を持つ辺の列である。
経路は、その最初の辺の始点となる頂点が最後の辺の終点となる頂点と同じであるとき、サイクル（閉路）を形成する。
有向非巡回グラフは、サイクルを持たない有向グラフのことである<ref name="thul">{{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=118}}.</ref><ref name="bang">{{citation|title=Digraphs: Theory, Algorithms and Applications|first1=Jørgen|last1=Bang-Jensen|series=Springer Monographs in Mathematics|edition=2nd|publisher=Springer-Verlag|year=2008|isbn=978-1-84800-997-4|contribution=2.1 Acyclic Digraphs|pages=32–34}}.</ref><ref>{{citation|title=Graph theory: an algorithmic approach|first=Nicos|last=Christofides|author-link=Nicos Christofides|publisher=Academic Press|year=1975|pages=170–174}}</ref>。

有向グラフの頂点 {{mvar|v}} は、頂点 {{mvar|u}} を始点とし頂点 {{mvar|v}} を終点とする経路が存在するとき、頂点 {{mvar|u}} から到達可能であるという。
特別な例として、すべての頂点は、自分自身から（辺がの数が 0 の経路によって）到達可能であると考えられる。
ある頂点が、非自明な経路（辺の数が 1 つ以上の経路）で自身に到達できる場合、その経路はサイクルである。
このため、どの頂点も非自明な経路では自身に到達できないグラフ、としても有向非巡回グラフを定義することができる<ref>{{citation|title=Simulation Techniques for Discrete Event Systems|volume=14|series=Cambridge Computer Science Texts|first=I.|last=Mitrani|year=1982|publisher=Cambridge University Press|isbn=9780521282826|page=27|url=https://books.google.com/books?id=CF04AAAAIAAJ&pg=PA27}}</ref>。

== 数学的特性 ==

=== 到達可能性関係・推移閉包・推移簡約 ===
DAG における{{仮リンク|到達可能性|en|Reachability}}関係は、 DAG の頂点の[[半順序]] ≤ として形式化できる。
この半順序では、頂点 {{mvar|u}} と頂点 {{mvar|v}} は、DAG 内に {{mvar|u}} から {{mvar|v}} への有向パスが存在するとき、すなわち {{mvar|v}} が {{mvar|u}} から到達可能なときに、 {{mvar|u}} ≤ {{mvar|v}} として順序づけられる<ref>{{citation|title=The Design and Analysis of Algorithms|series=Monographs in Computer Science|first=Dexter|last=Kozen|author-link=Dexter Kozen|publisher=Springer|year=1992|isbn=978-0-387-97687-7|page=9|url=https://books.google.com/books?id=L_AMnf9UF9QC&pg=PA9}}</ref>。
しかし、異なる DAG から、同じ到達可能性関係と同じ[[半順序集合]]が得られる場合もある<ref>{{citation|title=Loop Transformations for Restructuring Compilers: The Foundations|first=Utpal|last=Banerjee|publisher=Springer|year=1993|isbn=978-0-7923-9318-4|page=19|bibcode=1993ltfr.book.....B|contribution=Exercise 2(c)|url=https://books.google.com/books?id=Cog7zSSlqFwC&pg=PA19}}</ref>。
例えば、2 つの辺 {{mvar|a}} → {{mvar|b}}、{{mvar|b}} → {{mvar|c}} を持つ DAG は、3 つの辺 {{mvar|a}} → {{mvar|b}}、{{mvar|b}} → {{mvar|c}}、{{mvar|a}} → {{mvar|c}} を持つ DAG と同じ到達可能性関係を持ち、どちらも頂点が {{mvar|a}} ≤ {{mvar|b}} ≤ {{mvar|c}} の順に並んだ半順序集合を持つ。

{{multiple image|image1=Tred-G.svg|width1=175|image2=Tred-Gprime.svg|width2=124|caption1=有向非巡回グラフ {{mvar|G}}|caption2={{mvar|G}} の推移簡約}}

DAG {{mvar|G}} の[[推移閉包]]は、{{mvar|G}} と同じ到達可能性関係を表す DAG の中で、最も多くの辺を持つものである。
これは、頂点 {{mvar|u}} から {{mvar|v}} に到達できるときには必ず辺 {{mvar|u}} → {{mvar|v}} を持つ。
つまり、{{mvar|G}} の到達可能性関係において異なる要素の関連するペア {{mvar|u}} ≤ {{mvar|v}} は必ず辺を持つので、到達可能性関係 ≤ をグラフ理論的に直訳したものと考えてよい。
この方法はより一般的に有効で、全ての有限半順序集合（{{mvar|S}}、≤）に対して、{{mvar|S}} の各メンバーに頂点を持ち、{{mvar|u}} ≤ {{mvar|v}} で関連する要素のペアに辺を持つグラフは、自動的に DAG の推移閉包となり、（{{mvar|S}}、≤）を到達可能性関係として持つ。
このようにして、全ての有限半順序集合は、DAG の到達可能性関係として表すことができる。

DAG {{mvar|G}} の{{仮リンク|推移簡約|en|Transitive reduction}}とは、{{mvar|G}} と同じ到達可能性関係を表す DAG の中で、最も少ない辺を持つものである。
これは {{mvar|G}} のサブグラフであり、{{mvar|G}} が {{mvar|u}} から {{mvar|v}} に至るより長いパスを持つ場合に辺 {{mvar|u}} → {{mvar|v}} を廃棄することで形成される。
推移閉包と同様、推移簡約も DAG に対して一意に定義される。
一方、DAG 以外の有向グラフでは、同じ到達可能性関係を持つ最小部分グラフが複数存在する場合がある<ref>{{citation|title=Digraphs: Theory, Algorithms and Applications|series=Springer Monographs in Mathematics|first1=Jørgen|last1=Bang-Jensen|first2=Gregory Z.|last2=Gutin|publisher=Springer|year=2008|isbn=978-1-84800-998-1|url=https://books.google.com/books?id=4UY-ucucWucC&pg=PA36|contribution=2.3 Transitive Digraphs, Transitive Closures and Reductions|pages=36–39}}</ref>。

[[File:Hasse diagram of powerset of 3.svg|thumb|300px|3要素集合の部分集合間の集合包含（⊆）の半順序集合を表すハッセ図]]

DAG {{mvar|G}} が半順序 ≤ で表される到達可能性関係を持つとき、{{mvar|G}} の推移簡約は {{mvar|G}} サブグラフであり、≤ の{{仮リンク|被覆関係|en|Covering relation}} にある全てのペアに対し辺 {{mvar|u}} → {{mvar|v}} を持つ。 
推移簡約は同じ半順序を表す他のグラフに比べて辺の数が少なく、グラフの描画が単純になるため、半順序を視覚化するのに便利である。
半順序の[[ハッセ図]]は、推移簡約を図示したもので、各辺の向きを、辺の始点の頂点を終点の頂点よりも低い位置に置いて示している<ref>{{citation|title=Graphs, Networks and Algorithms|volume=5|series=Algorithms and Computation in Mathematics|first=Dieter|last=Jungnickel|publisher=Springer|year=2012|isbn=978-3-642-32278-5|pages=92–93|url=https://books.google.com/books?id=PrXxFHmchwcC&pg=PA92}}.</ref>。

== 注釈・出典 ==
{{reflist}}

== 関連項目 ==
* [[グラフ理論]]
* [[トポロジカルソート]]
* [[ベイジアンネットワーク]]

== 外部リンク ==
* {{MathWorld|title=Acyclic Digraph|urlname=AcyclicDigraph}}
* [http://www.dagitty.net/ DAGitty] – DAG をつくるためのオンラインツール

{{Graph Theory-footer}}
{{データ構造}}
{{Combin-stub}}

{{DEFAULTSORT:ゆうこうひしゆんかいくらふ}}
[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]