Read More
Date: 1-5-2022
1532
Date: 24-7-2016
2112
Date: 27-4-2022
1499
|
An acyclic digraph is a directed graph containing no directed cycles, also known as a directed acyclic graph or a "DAG." Every finite acyclic digraph has at least one node of outdegree 0. The numbers of acyclic digraphs on , 2, ... vertices are 1, 2, 6, 31, 302, 5984, ... (OEIS A003087).
The numbers of labeled acyclic digraphs on , 2, ... nodes are 1, 3, 25, 543, 29281, ... (OEIS A003024). Weisstein's conjecture proposed that positive eigenvalued -matrices were in one-to-one correspondence with labeled acyclic digraphs on nodes, and this was subsequently proved by McKay et al. (2004). Counts for both are therefore given by the beautiful recurrence equation
with (Harary and Palmer 1973, p. 19; Robinson 1973, pp. 239-273).
Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 200, 1994.
Harary, F. and Palmer, E. M. "Acyclic Digraph." §8.8 in Graphical Enumeration. New York: Academic Press, pp. 191-194, 1973.
McKay, B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.; and Wilf, H. "Acyclic Digraphs and Eigenvalues of -Matrices." J. Integer Sequences 7, Article 04.3.3, 1-5, 2004.
http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html.Robinson, R. W. "Counting Labeled Acyclic Digraphs." In New Directions in Graph Theory (Ed. F. Harary). New York: Academic Press, 1973.
Robinson, R. W. "Counting Unlabeled Acyclic Digraphs." In Combinatorial Mathematics V: Proceedings of the Fifth Australian Conference, held at the Royal Melbourne Institute of Technology, Aug. 24-26, 1976). Providence, RI: Amer. Math. Soc., pp. 28-43, 1976.
Sloane, N. J. A. Sequence A003087/M1696 in "The On-Line Encyclopedia of Integer Sequences."
|
|
دراسة يابانية لتقليل مخاطر أمراض المواليد منخفضي الوزن
|
|
|
|
|
اكتشاف أكبر مرجان في العالم قبالة سواحل جزر سليمان
|
|
|
|
|
المجمع العلمي ينظّم ندوة حوارية حول مفهوم العولمة الرقمية في بابل
|
|
|