主题
Search

毛毛虫图

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

毛毛虫图，毛毛虫树，或简称为“毛毛虫”，是一种树，其中每个图顶点都在中心茎干上，或仅距离茎干一个图边（换句话说，移除其端点后会留下一个路径图；Gallian 2007）。一棵树是毛毛虫当且仅当所有度数 >=3 的节点最多被两个度数为 2 或更大的节点包围。

n-烷烃图有时也被称为毛毛虫图 (Boesch et al. 1974; Merrifield and Simmons 1989, pp. 161-162)。

毛毛虫图是优美的。

CaterpillarTrees

节点数为 n>=3 的毛毛虫树的数量是

C_n=2^(n-4)+2^(|_n/2-2_|),

其中 |_x_| 是向下取整函数 (Harary and Schwenk 1973)。对于 n=1, 2, ... 个节点，结果为 1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, ... (OEIS A005418)。上面展示了前几个毛毛虫图。

CaterpillarGraph

节点数为 n=7, 8, ... 的非毛毛虫树的数量为 1, 3, 11, 34, 99, ... (OEIS A052471)。上面展示了节点数 n<=9 的非毛毛虫树。

另请参阅

香蕉树, 蜈蚣图, 龙虾图, 树

使用 Wolfram|Alpha 探索

参考文献

Boesch, F. T.; Chen, S.; 和 McHugh, J. A. M. "关于用点不相交路径覆盖图的点。" In Graphs and Combinatorics (Ed. R. A. Bari 和 F. Harary). Berlin: Springer-Verlag, pp. 201-212, 1974.Gallian, J. "图标记的动态综述。" Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Gardner, M. 轮子，生命和其他数学消遣。 New York: W. H. Freeman, p. 160, 1983.Gutman, I. 和 El-Basil, S. "苯并类系统的拓扑性质。XXXVII. 某些化学图的表征。" Z. Naturforsch. A 40, 923-926, 1985.Harary, F. 和 Schwenk, A. J. "毛毛虫的数量。" Disc. Math. 6, 359-365, 1973.Hoffman, N. "二元网格和一个相关的计数问题。" Two Year Coll. Math. J. 9, 267-272, 1978.Horton, M. "优美树：统计和算法。" 荣誉计算学士论文。塔斯马尼亚大学, 2003. https://eprints.utas.edu.au/19/1/GracefulTreesStatisticsAndAlgorithms.pdf.Merrifield, R. E. 和 Simmons, H. E. 化学中的拓扑方法。 New York: Wiley, 1989.Sloane, N. J. A. 序列 A005418/M0771 和 A052471 在 "The On-Line Encyclopedia of Integer Sequences." 中。Sulanke, R. A. "广义莫茨金路径的矩。" J. Integer Sequences 3, No. 00.1.1, 2000. http://www.math.uwaterloo.ca/JIS/VOL3/SULANKE/sulanke.

请引用为

Weisstein, Eric W. “毛毛虫图。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/CaterpillarGraph.html

主题分类