主题
Search

树

下载 Mathematica 笔记本下载 Wolfram 笔记本
Trees

树是一种数学结构，可以被视为图或数据结构。这两种观点是等价的，因为树数据结构不仅包含一组元素，还包含元素之间的连接，从而形成树图。

树最早由 Cayley (1857) 研究。McKay 维护着一个包含多达 18 个顶点的树的数据库，而 Royle 维护着一个包含多达 20 个顶点的树的数据库。

树是一组首尾相连的直线段，不包含闭环（环）。换句话说，它是一个简单、无向、连通、无环的图（或等效地，一个连通的森林）。一个有 n 个节点的树有 n-1 条图边。相反，一个具有 n 个节点和 n-1 条边的连通图是一棵树。所有树都是二分图 (Skiena 1990, p. 213)。没有特别指出节点的树有时被称为自由树（或无根树），以区别于有根树（Skiena 1990, Knuth 1997）。

连接点被称为叉，线段被称为分支。末端线段和节点被称为树叶。在每个叉处有两个分支，并且在每个分支的末端有一个或两个树叶的树被称为二叉树。

可以使用Wolfram 语言测试图是否为树，使用TreeGraphQ[g]。

Hydrocarbons

树在许多不同领域都有应用，包括计算机科学、饱和烃的枚举、电路研究等（Harary 1994, p. 4）。上面说明的与线性烃对应的图被称为 (n-)烷烃图（或有时称为毛毛虫图）。

树是块图。

树 T 要么有一个节点是图中心，在这种情况下它被称为中心树，要么有两个相邻的节点是图中心，在这种情况下它被称为双中心树（Harary 1994, p. 35）。

当指定一个特殊节点将树变成有根树时，它被称为根（或有时称为“夏娃”）。在这样的树中，每个距离给定节点更远一个图边的节点被称为子节点，而连接到同一节点且与根顶点距离相同的节点被称为兄弟节点。

请注意，两个首尾相连的分支等同于一个分支，这意味着例如，只有一个 3 阶树。阶数为 n=1, 2, ... 的非同构树的数量 t(n) （其中阶数为 1、2、...、6 的树如上所示）为 1、1、1、2、3、6、11、23、47、106、235、551、1301、3159、... (OEIS A000055)。

有根树数量的生成函数

T(x)=sum_(n=1)^(infty)T_nx^n
(1)
=xexp[sum_(r=1)^(infty)1/rT(x^r)]
(2)

与无根树数量的生成函数 t(x) 相关，关系如下

t(x)=sum_(n=1)^(infty)t_nx^n
(3)
=T(x)-1/2[T^2(x)-T(x^2)].
(4)

Otter 表明

lim_(n->infty)(t_nn^(5/2))/(alpha^n)=beta,
(5)

(Otter 1948, Harary and Palmer 1973, Knuth 1997)，其中 alpha 和 beta 是两个常数。alpha 由下式给出

alpha=lim_(n->infty)(T_n)/(T_(n-1))
(6)
=2.955765...
(7)

(OEIS A051491; Odlyzko 1995; Knuth 1997, p. 396, 其中 Knuth 写道 1/alpha=2.9557... 而不是 alpha=2.9557...) 并且也是以下方程的唯一正根

T(1/x)=1.
(8)

常数 beta 由下式给出

beta=1/(sqrt(2pi))[1+sum_(k=2)^(infty)T^'(1/(alpha^k))1/(alpha^k)]^(3/2)
(9)
=0.5349485...
(10)

(OEIS A086308; Knuth 1997, p. 396)。

如果 t_n 是 n 个节点上的非同构树的数量，则 t_n 的渐近级数由下式给出

t_n∼alpha^nn^(-5/2)(0.5349496061...+(0.0441699018...)/n+(0.4853877311...)/(n^2)+(2.379745574...)/(n^3)+...),
(11)

其中常数可以用函数的部分导数计算

F(x,y)=xexp[y+sum_(k=2)^infty(T(x^k))/k]-y
(12)

(Plotkin and Rosenthal 1994; Finch 2003)。

另请参阅

烷烃图, B 树, 香蕉树, Barnsley 树, 双中心树, 二叉树, 毛毛虫图, Cayley 树, 中心树, 子节点, Dijkstra 树, 扩展二叉树, 森林, 自由树, k-树, Kruskal 算法, Kruskal 树定理, 标记树, 龙虾图, Mandelbrot 树, 矩阵树定理, 果园种植问题, 有序树, Otter 定理, 路径图, 平面植根树, Pólya 枚举定理, Polynema, 毕达哥拉斯树, 四叉树, Ramus 树, 红黑树, 根顶点, 有根树, 串联约简树, 兄弟节点, 生成树, 星图, Steiner 树, Stern-Brocot 树, 树分解, 树叶, 树搜索, 弱二叉树, 加权树 在 MathWorld 课堂中探索此主题

使用 Wolfram|Alpha 探索

参考文献

Finch, S. R. "Otter's Tree Enumeration Constants." §5.6 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 295-316, 2003.Bergeron, F.; Leroux, P.; and Labelle, G. Combinatorial Species and Tree-Like Structures. Cambridge, England: Cambridge University Press, p. 284, 1998.Cayley, A. "On the Theory of Analytic Forms Called Trees." Philos. Mag. 13, 19-30, 1857. Reprinted in Mathematical Papers, Vol. 3. Cambridge: pp. 242-246, 1891.Chauvin, B.; Cohen, S.; and Rouault, A. (Eds.). Trees: Workshop in Versailles, June 14-16, 1995. Basel, Switzerland: Birkhäuser, 1996.Finch, S. "Two Asymptotic Series." December 10, 2003. http://algo.inria.fr/bsolve/.Gardner, M. "Trees." Ch. 17 in Mathematical Magic Show: More Puzzles, Games, Diversions, Illusions and Other Mathematical Sleight-of-Mind from Scientific American. New York: Vintage, pp. 240-250, 1978.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Harary, F. "Trees." Ch. 4 in Graph Theory. Reading, MA: Addison-Wesley, pp. 32-42, 187-194, and 231-234, 1994.Harary, F. and Manvel, B. "Trees." Scripta Math. 28, 327-333, 1970.Harary, F. and Palmer, E. M. "Trees." Ch. 3 in Graphical Enumeration. New York: Academic Press, pp. 51-80, 1973.Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1997.König, D. Theorie der endlichen und unendlichen Graphen. New York: Chelsea, p. 48, 1950.McKay, B. D. "Trees Sorted by Diameter." http://cs.anu.edu.au/~bdm/data/trees.html.Nijenhuis, A. and Wilf, H. Combinatorial Algorithms for Computers and Calculators, 2nd ed. New York: Academic Press, 1978.Odlyzko, A. M. "Asymptotic Enumeration Methods." In Handbook of Combinatorics, Vol. 2 (Ed. R. L. Graham, M. Grötschel, and L. Lovász). Cambridge, MA: MIT Press, pp. 1063-1229, 1995. http://www.dtc.umn.edu/~odlyzko/doc/asymptotic.enum.pdf.Otter, R. "The Number of Trees." Ann. Math. 49, 583-599, 1948.Plotkin, J. M. and Rosenthal, J. W. "How to Obtain an Asymptotic Expansion of a Sequence from an Analytic Identity Satisfied by Its Generating Function." J. Austral. Math. Soc. Ser. A 56, 131-143, 1994.Royle, G. "Trees On Up to 16 [sic] Vertices." http://school.maths.uwa.edu.au/~gordon/remote/graphs/#trees.Skiena, S. "Trees." Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 107 and 151-153, 1990.Sloane, N. J. A. Sequences A000055/M0791, A051491, and A086308 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. Figure M0791 in The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.Wilf, H. S. Combinatorial Algorithms: An Update. Philadelphia, PA: SIAM, 1989.

在 Wolfram|Alpha 上被引用

树

引用为

Weisstein, Eric W. "树。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Tree.html

主题分类