有向非巡回グラフ
(有向非輪状グラフ から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/12/16 04:51 UTC 版)
有向非巡回グラフ、有向非循環グラフ、有向無閉路グラフ（ゆうこうひじゅんかいグラフ、英: Directed acyclic graph, DAG）とは、グラフ理論における閉路のない有向グラフのことである。有向グラフは頂点と有向辺（方向を示す矢印付きの辺）からなり、辺は頂点同士をつなぐが、ある頂点から出発し、辺をたどり、頂点に戻ってこないのが有向非巡回グラフである[1][2][3]。
- ^ 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.
- ^ 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.
- ^ Christofides, Nicos (1975), Graph theory: an algorithmic approach, Academic Press, pp. 170–174
- ^ Mitrani, I. (1982), Simulation Techniques for Discrete Event Systems, Cambridge Computer Science Texts, 14, Cambridge University Press, p. 27, ISBN 9780521282826
- ^ Kozen, Dexter (1992), The Design and Analysis of Algorithms, Monographs in Computer Science, Springer, p. 9, ISBN 978-0-387-97687-7
- ^ Banerjee, Utpal (1993), “Exercise 2(c)”, Loop Transformations for Restructuring Compilers: The Foundations, Springer, p. 19, Bibcode: 1993ltfr.book.....B, ISBN 978-0-7923-9318-4
- ^ Bang-Jensen, Jørgen; Gutin, Gregory Z. (2008), “2.3 Transitive Digraphs, Transitive Closures and Reductions”, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Springer, pp. 36–39, ISBN 978-1-84800-998-1
- ^ Jungnickel, Dieter (2012), Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics, 5, Springer, pp. 92–93, ISBN 978-3-642-32278-5.
[続きの解説]
「有向非巡回グラフ」の続きの解説一覧
- 1 有向非巡回グラフとは
- 2 有向非巡回グラフの概要
- 3 関連項目
- 有向非巡回グラフのページへのリンク
