主题
Search

无环有向图

下载 Mathematica 笔记本下载 Wolfram 笔记本
AcyclicDigraphs

无环有向图是一个有向图，不包含有向环，也称为有向无环图或“DAG”。每个有限无环有向图至少有一个出度为 0 的节点。顶点数为 n=1, 2, ... 的无环有向图的数量分别是 1, 2, 6, 31, 302, 5984, ... (OEIS A003087)。

顶点数为 n=1, 2, ... 的标记无环有向图的数量分别是 1, 3, 25, 543, 29281, ... (OEIS A003024)。 韦斯坦因猜想 提出 正特征值 (0,1)-矩阵与顶点数为 n 的标记无环有向图之间存在一一对应关系，随后 McKay et al. (2004) 证明了这一点。因此，两者的计数都由美丽的递推方程给出

a_n=sum_(k=1)^n(-1)^(k-1)(n; k)2^(k(n-k))a_(n-k)

其中 a_0=1 (Harary and Palmer 1973, p. 19; Robinson 1973, pp. 239-273)。

另请参阅

森林, 超串, 正特征值矩阵, 简单有向图, 韦斯坦因猜想

使用 探索

参考文献

Harary, F. 图论。 Reading, MA: Addison-Wesley, p. 200, 1994.Harary, F. 和 Palmer, E. M. "无环有向图。" §8.8 in 图形计数。 New York: Academic Press, pp. 191-194, 1973.McKay, B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.; 和 Wilf, H. "无环有向图和 (0,1)-矩阵的特征值。" 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. "标记无环有向图的计数。" In 图论新方向 (Ed. F. Harary). New York: Academic Press, 1973.Robinson, R. W. "未标记无环有向图的计数。" In 组合数学 V：第五届澳大利亚会议论文集，于 1976 年 8 月 24-26 日在皇家墨尔本理工学院举行)。 Providence, RI: Amer. Math. Soc., pp. 28-43, 1976.Sloane, N. J. A. 序列 A003087/M1696 in "整数序列在线百科全书。"

在 上被引用

无环有向图

引用此内容为

韦斯坦因，埃里克·W. "无环有向图。" 来自 Web 资源。 https://mathworld.net.cn/AcyclicDigraph.html

主题分类