# 有向无环图

## 数学性质

G的传递规约

### 组合计数

1, 1, 3, 25, 543, 29281, 3781503, … （OEIS數列A003024）。

${\displaystyle a_{n}=\sum _{k=1}^{n}(-1)^{k-1}{n \choose k}2^{k(n-k)}a_{n-k}.}$ [12]

## 参考文献

1. ^ Introduction to Algorithms [算法导论]. : 1172. ISBN 978-7-111-40701-0.
2. ^ Thulasiraman, K.; Swamy, M. N. S., 5.7 Acyclic Directed Graphs, Graphs: Theory and Algorithms, John Wiley and Son: 118, 1992, ISBN 978-0-471-51356-8.
3. Bang-Jensen, Jørgen, 2.1 Acyclic Digraphs, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics 2nd, Springer-Verlag: 32–34, 2008, ISBN 978-1-84800-997-4.
4. ^ Christofides, Nicos, Graph theory: an algorithmic approach, Academic Press: 170–174, 1975.
5. ^ Mitrani, I., Simulation Techniques for Discrete Event Systems, Cambridge Computer Science Texts 14, Cambridge University Press: 27, 1982 [2020-01-18], ISBN 9780521282826, （原始内容存档于2021-03-10）.
6. ^ Kozen, Dexter, The Design and Analysis of Algorithms, Monographs in Computer Science, Springer: 9, 1992 [2020-01-14], ISBN 978-0-387-97687-7, （原始内容存档于2021-03-10）.
7. ^ Banerjee, Utpal, Exercise 2(c), Loop Transformations for Restructuring Compilers: The Foundations, Springer: 19, 1993 [2020-01-14], ISBN 978-0-7923-9318-4, （原始内容存档于2021-03-10）.
8. ^ Bang-Jensen, Jørgen; Gutin, Gregory Z., 2.3 Transitive Digraphs, Transitive Closures and Reductions, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Springer: 36–39, 2008 [2020-01-14], ISBN 978-1-84800-998-1, （原始内容存档于2021-03-10）.
9. ^ Jungnickel, Dieter, Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics 5, Springer: 92–93, 2012 [2020-01-15], ISBN 978-3-642-32278-5, （原始内容存档于2021-03-10）.
10. ^ Sedgewick, Robert; Wayne, Kevin, 4,2,25 Unique topological ordering, Algorithms 4th, Addison-Wesley: 598–599, 2011 [2020-01-17], ISBN 978-0-13-276256-4, （原始内容存档于2021-03-10）.
11. ^ Bender, Edward A.; Williamson, S. Gill, Example 26 (Linear extensions – topological sorts), A Short Course in Discrete Mathematics, Dover Books on Computer Science, Courier Dover Publications: 142, 2005 [2020-01-17], ISBN 978-0-486-43946-4, （原始内容存档于2021-03-10）.
12. Robinson, R. W., Counting labeled acyclic digraphs, Harary, F. (编), New Directions in the Theory of Graphs, Academic Press: 239–273, 1973. See also Harary, Frank; Palmer, Edgar M., Graphical Enumeration, Academic Press: 19, 1973, ISBN 978-0-12-324245-7.
13. ^ Weisstein, Eric W. (编). Weisstein's Conjecture. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英语）.
14. ^ McKay, B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.; Wilf, H., Acyclic digraphs and eigenvalues of (0,1)-matrices, Journal of Integer Sequences, 2004, 7 [2020-01-19], （原始内容存档于2021-02-24）, Article 04.3.3.
15. ^ Rebane, George; Pearl, Judea, The recovery of causal poly-trees from statistical data, in Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987 (PDF): 222–228, 1987[永久失效連結].
16. ^ Furnas, George W.; Zacks, Jeff, Multitrees: enriching and reusing hierarchical structure, Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94): 330–336, 1994, ISBN 978-0897916509, doi:10.1145/191666.191778.
17. ; ; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms 2nd. MIT Press and McGraw-Hill. 2001 [1990]. ISBN 0-262-03293-7. Section 22.4, Topological sort, pp. 549–552.
18. Jungnickel (2012), pp. 50–51.
19. ^ For depth-first search based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g. Skiena, Steven S., The Algorithm Design Manual, Springer: 179–181, 2009 [2020-01-21], ISBN 978-1-84800-070-4, （原始内容存档于2021-03-10）.
20. ^ Stanley, Richard P., Acyclic orientations of graphs (PDF), Discrete Mathematics, 1973, 5 (2): 171–178 [2020-01-22], doi:10.1016/0012-365X(73)90108-8, （原始内容存档 (PDF)于2021-02-24）.
21. ^ Garey, Michael R.; Johnson, David S., Problems GT7 and GT8, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman: 191–192, 1979, ISBN 0-7167-1045-5
22. ^ Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin, Structural Models: An Introduction to the Theory of Directed Graphs, John Wiley & Sons: 63, 1965.
23. ^ Skiena (2009), p. 495.
24. ^ Skiena (2009), p. 496.
25. ^ Bang-Jensen & Gutin (2008), p. 38.
26. ^ Picard, Jean-Claude, Maximal closure of a graph and applications to combinatorial problems, , 1976, 22 (11): 1268–1272, MR 0403596, doi:10.1287/mnsc.22.11.1268.
27. ^ Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.
28. ^ Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.
29. ^ Cormen et al. 2001, p. 966.
30. ^ Skiena (2009), p. 469.
31. ^ Al-Mutawa, H. A.; Dietrich, J.; Marsland, S.; McCartin, C., On the shape of circular dependencies in Java programs, 23rd Australian Software Engineering Conference, IEEE: 48–57, 2014, ISBN 978-1-4799-3149-1, doi:10.1109/ASWEC.2014.15.
32. Gross, Jonathan L.; Yellen, Jay; Zhang, Ping, Handbook of Graph Theory 2nd, CRC Press: 1181, 2013 [2020-01-30], ISBN 978-1-4398-8018-0, （原始内容存档于2021-03-10）.
33. ^ Srikant, Y. N.; Shankar, Priti, The Compiler Design Handbook: Optimizations and Machine Code Generation 2nd, CRC Press: 19–39, 2007 [2020-01-30], ISBN 978-1-4200-4383-9, （原始内容存档于2021-03-10）.
34. ^ Wang, John X., What Every Engineer Should Know About Decision Making Under Uncertainty, CRC Press: 160, 2002 [2020-01-31], ISBN 978-0-8247-4373-4, （原始内容存档于2021-03-10）.
35. ^ Sapatnekar, Sachin, Timing, Springer: 133, 2004 [2020-02-03], ISBN 978-1-4020-7671-8, （原始内容存档于2021-03-10）.
36. ^ Dennis, Jack B., First version of a data flow procedure language, Programming Symposium, Lecture Notes in Computer Science 19: 362–376, 1974, ISBN 978-3-540-06859-4, doi:10.1007/3-540-06859-7_145.
37. ^ Touati, Sid; de Dinechin, Benoit, Advanced Backend Optimization, John Wiley & Sons: 123, 2014 [2020-02-04], ISBN 978-1-118-64894-0, （原始内容存档于2021-03-10）.
38. ^ Gopnik, Alison; Schulz, Laura, Causal Learning, Oxford University Press: 4, 2007 [2020-06-01], ISBN 978-0-19-803928-0, （原始内容存档于2021-03-10）.
39. ^ Shmulevich, Ilya; Dougherty, Edward R., Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks, Society for Industrial and Applied Mathematics: 58, 2010 [2020-06-01], ISBN 978-0-89871-692-4, （原始内容存档于2021-03-10）.
40. ^ Cowell, Robert G.; Dawid, A. Philip; Lauritzen, Steffen L.; Spiegelhalter, David J., 3.2.1 Moralization, Probabilistic Networks and Expert Systems, Springer: 31–33, 1999, ISBN 0-387-98767-3.
41. ^ Dorf, Richard C., The Technology Management Handbook, CRC Press: 9-7, 1998 [2020-06-01], ISBN 978-0-8493-8577-3, （原始内容存档于2021-03-10）.
42. ^ Boslaugh, Sarah, Encyclopedia of Epidemiology, Volume 1, SAGE: 255, 2008 [2020-06-01], ISBN 978-1-4129-2816-8, （原始内容存档于2021-03-10）.
43. ^ Pearl, Judea. Causal diagrams for empirical research. Biometrika. 1995, 82 (4): 669–709. doi:10.1093/biomet/82.4.669.
44. ^ Kirkpatrick, Bonnie B., Haplotypes versus genotypes on pedigrees, Algorithms for Molecular Biology, April 2011, 6 (10): 10, , PMID 21504603, doi:10.1186/1748-7188-6-10.
45. ^ McGuffin, M. J.; Balakrishnan, R., Interactive visualization of genealogical graphs (PDF), IEEE Symposium on Information Visualization (INFOVIS 2005): 16–23, 2005 [2020-02-07], ISBN 978-0-7803-9464-3, doi:10.1109/INFVIS.2005.1532124, （原始内容存档 (PDF)于2021-02-24）.
46. ^ Bender, Michael A.; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel, Finding least common ancestors in directed acyclic graphs, Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '01), Philadelphia, PA, USA: Society for Industrial and Applied Mathematics: 845–854, 2001 [2020-02-08], ISBN 978-0-89871-490-6, （原始内容存档于2018-12-01）.
47. ^ Bartlang, Udo, Architecture and Methods for Flexible Content Management in Peer-to-Peer Systems, Springer: 59, 2010 [2020-05-31], ISBN 978-3-8348-9645-2, （原始内容存档于2021-03-10）.
48. ^ Pach, János; Sharir, Micha, Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical surveys and monographs 152, American Mathematical Society: 93–94, [2020-06-01], ISBN 978-0-8218-7533-9, （原始内容存档于2021-03-10）.
49. ^ Price, Derek J. de Solla, Networks of Scientific Papers (PDF), Science, July 30, 1965, 149 (3683): 510–515 [2020-06-01], Bibcode:1965Sci...149..510D, PMID 14325149, doi:10.1126/science.149.3683.510, （原始内容存档 (PDF)于2019-05-20）.
50. ^ Clough, James R.; Gollings, Jamie; Loach, Tamar V.; Evans, Tim S., Transitive reduction of citation networks, Journal of Complex Networks, 2015, 3 (2): 189–203, , doi:10.1093/comnet/cnu039.
51. ^ Crochemore, Maxime; Vérin, Renaud, Direct construction of compact directed acyclic word graphs, Combinatorial Pattern Matching, Lecture Notes in Computer Science 1264, Springer: 116–129, 1997, , ISBN 978-3-540-63220-7, doi:10.1007/3-540-63220-4_55.
52. ^ Lothaire, M., Applied Combinatorics on Words, Encyclopedia of Mathematics and its Applications 105, Cambridge University Press: 18, 2005 [2020-06-01], ISBN 9780521848022, （原始内容存档于2021-03-10）.
53. ^ Lee, C. Y., Representation of switching circuits by binary-decision programs, Bell System Technical Journal, 1959, 38 (4): 985–999, doi:10.1002/j.1538-7305.1959.tb01585.x.
54. ^ Akers, Sheldon B., Binary decision diagrams, IEEE Transactions on Computers, 1978, C–27 (6): 509–516, doi:10.1109/TC.1978.1675141.
55. ^ Friedman, S. J.; Supowit, K. J., Finding the optimal variable ordering for binary decision diagrams, Proc. 24th ACM/IEEE Design Automation Conference (DAC '87), New York, NY, USA: ACM: 348–356, 1987, ISBN 978-0-8186-0781-3, doi:10.1145/37888.37941.