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

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