Cutting down random trees
Cutting down random trees
复制标题
DOI：
10.1017/s1446788700006698
复制
发表时间：
1970-08
影响因子：
0.7
通讯作者：
A. Meir;J. Moon
中科院分区：
文献类型：
--
作者：
A. Meir;J. Moon
设Tn表示一个有n（n ~ 2）个标号点的树：我们假设Tn的根在一个给定的点x，比如标号为1的点（这里没有给出定义，见[3]）。如果我们去掉Tn的一些边e，则Tn福尔斯落入两个子树中，其中一个，比如说Tk，包含根x。如果k ≥ 2，我们可以去掉Tk的一些边，得到Tn的一个更小的包含x的子树。如果我们重复这个过程，我们最终会得到由x本身组成的子树。设λ = λ（Tn）表示在根x被孤立之前从Tn移除的边的数目。这里我们的主要目的是在以下假设下确定λ（Tn）的期望值μ（n）和方差σ2（n）：（1）Tn是从nn-2棵树的集合中随机选择的，树的n个标号点都以点x为根，（2）在每一阶段，被移除的边是从包含x的剩余子树的边中随机选择的。从我们的结果可以得出，当n趋于无穷大时，μ（n）~（1/2 πn）1/2和（2 - 1/2 π）n ~（2 - 1/2 π）n。我们还考虑了相应的问题，森林的根树和树的程度的根是指定的。我们感谢阿利斯泰尔·拉克兰教授向我们提出了最初的问题。
Let Tn denote a tree with n(≧ 2) labelled points: we assume Tn is rooted at a given point x, say the point labelled 1 (see [3] for definitions not given here). If we remove some edge e of Tn, then Tn falls into two subtrees one of which, say Tk, contains the root x. If k ≧ 2 we can remove some edge of Tk and obtain an even smaller subtree of Tn that contains x. If we repeat this process we will eventually obtain the subtree consisting of x itself. Let λ = λ(Tn) denote the number of edges removed from Tn before the root x is isolated. Our main object here is to determine the expected value μ(n) and variance σ2(n) of λ(Tn) under the assumptions (1) Tn is chosen at random from the set of nn−2 trees with n labelled points that are rooted at point x, and (2) at each stage the edge removed is chosen at random from the edges of the remaining subree containing x. It follows from our results that μ(n) ~ (½πn)½ and (2−½π)n ~ (2−½π)n as n tends to infinity. We also consider the corresponding problem for forests of rooted trees and for trees in which the degree of the root is specified. We are indebted to Professor Alistair Lachlan for suggesting the original problem to us.