主题
Search

串联约简树

下载 Mathematica 笔记本下载 Wolfram 笔记本
SeriesReducedTrees

串联约简树是一种树，其中所有节点的度数都不同于 2（换句话说，没有节点仅仅允许单条边“通过”）。串联约简树也称为同胚不可约树（Harary 和 Palmer 1973，第 61-62 页）或拓扑树（Bergeron等人1998）。具有 1, 2, ... 个节点的串联约简树的数量为 1, 1, 0, 1, 1, 2, 2, 4, 5, 10, 14, ... (OEIS A000014)。Harary 和 Palmer（1973，第 62 页，图 3.3.3）展示了节点数为 8 个及以下的串联约简树。

串联约简树的特殊情况包括烷烃图和星图 S_n，其中 n>3 个节点。

串联约简树在流行文化中最广为人知，是因为它们出现在 1997 年电影心灵捕手的第二个黑板问题中，该问题提出了找到所有 (10) 个具有 10 个节点的此类树的问题。

具有 n=1, 2, ... 个节点的串联约简种植树的数量为 0, 1, 0, 1, 1, 2, 3, 6, 10, 19, 35, ... (OEIS A001678)，串联约简有根树的数量为 1, 1, 0, 2, 2, 4, 6, 12, 20, 39, 71, ... (OEIS A001679)。

将与 2 度顶点 v_j 相邻的边 e_(ij)e_(jk) 替换为单条边 e_(ik) 的过程称为图平滑。

另请参阅

心灵捕手问题, 图平滑, 种植树, 有根树, 树

使用 Wolfram|Alpha 探索

参考文献

Bergeron, F.; Leroux, P.; 和 Labelle, G. 组合物种和树状结构。 英国剑桥：剑桥大学出版社，第 188, 283-284, 291 和 337 页，1998 年。Cameron, P. J. “一些树状对象。” 牛津大学数学季刊 38, 155-183, 1987。Finch, S. R. §5.6 in 数学常数。 英国剑桥：剑桥大学出版社，2003 年。Harary, F. 图论。 美国马萨诸塞州雷丁：艾迪生-韦斯利出版社，第 232 页，1994 年。Harary, F. 和 Palmer, E. M. 图形计数。 纽约：学术出版社，第 61-62 页，1973 年。Harary, F. 和 Palmer, E. M. “树的点的固定概率。” 剑桥哲学学会数学学报 85, 407-415, 1979。Harary, F. 和 Prins, G. “同胚不可约树和其他物种的数量。” 数学学报 101, 141-162, 1959。Harary, F.; Robinson, R. W. 和 Schwenk, A. J. “确定各种物种树木的渐近数量的二十步算法。” 澳大利亚数学学会杂志，A 系列 20, 483-503, 1975。Sloane, N. J. A. 序列 A000014/M0320, A001678/M0768 和 A001679/M0327，来自“整数序列在线百科全书”。

在 Wolfram|Alpha 中被引用

串联约简树

请这样引用

Weisstein, Eric W. “串联约简树。” 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/Series-ReducedTree.html

主题分类