字典序地生成有序森林的一个算法

本文给出有序森林的一种序列表示法,并描述了一个字典序地生成具有n个顶点的所有有序森林的一个算法.它是[1]中算法的推广.§1 有序森林的序列表示法文献[1]给出了有序根树的一种序列表示法.本文利用[1]中的表示法给出有序森林的一种序列表示法及生成它们的算法.本文中未加说明的术语皆见[1].若F的每一个连通     

字典序地生成叶子数限制的有序根树的算法

本文利用一个正整数序列来表示一棵叶子数限制的有序根树,给出了一个序列为某叶子数限制的有序根树的表示序列的充要条件,从而给出了字典序地生成所有叶子数限制的有序根树的算法.§1.叶子数限制的有序根树的序列表示法设T表示有序根树,用|T|表示T的边树.若v是T的顶点,v不是根且次数为1,则称v是T的叶子.     

按字典序遍数K分树

本文研究了Ll-限制K分树,文中用叶子的层数表示一个K分树,每个具有n个叶子的K分树对应一个n个正整数组成的序列.首先给出由n个正整数组成的序列代表一个具有n个叶子的Ll-限制K分树的充分必要条件.然后给出一个字典序列出所有具有n个叶子的Ll-限制K分树的算法.     

非奇函数是M序列反馈函数的一个充要条件

本文第1段系将文献[2]中所引进的M序列反馈函数用标号表示的概念推广为非奇反馈函数的标号表示法.文献[3]在第 2章里给出了非奇函数是M序列反馈函数的一些必要条件,而在本文第2段则根据文献[2]中的剪接法与有关结论给出了非奇函数是M序列反馈函数的一个充分与必要条件.     

Cauchy多边形数定理的一个简短证明

本文对下述事实给出一个简单的证明:每个自然数是m+2个m+2边形数之和. 设m≥1,一个m+2边形数是形如 Pm(k)=m/2(k2-k)+k,(k=0,1,2,…)的数.Fermat[3]断言:每一个自然数是m+2个m+2边形数之和.对于m=2,Lagrange[5]证明了每一个自然数是4个平方数P2(k)=k2之和.对于m=1,Gauss [4]证明了每一个自然数是3个三角数P1(k)=1/2(k2+k)之和,或等价的,每一个满足n≡3(mod 8)的正整数n都是3个奇数平方之和,Cauchy[1]对所有的m≥3证明了Fermat的断言,Legendre[6]进一步细化和推广了这一结果.对于m≥3且n≤120m,Pepin [8]给出了将n写成m+2个m+2边形数之和的显示表达的表,其中至少有m-2个取值于0或1.     

CCR_n 及 PCR_n 因子关联图中的重边

对补轮换 CCR_n 及纯轮换 PCR_n 因子关联图(?)及Γ~(n)_((x)_0)的研究,对于构造和分析 M 序列有着重要的意义:(?)及Γ~(n)_(x_0)的全部生成树分别对应着全部具最大及最小重量的 n 阶 M 序列;它们中的重边替换与用自同构产生的小项更迭给出了构造 M 序列的途径;而(?)中环的裂分又可给出其它重量的 n 阶 M 序列;这种生成树的方法还可与剪接法结合得到一种更快速的剪接——生成树法.本文在[1,4—6]的基础上从另一     

强有序输入消解原理

本文是在文献[1]的基础上提出一种直接判误法,并给出了相应的算法。然后又提出强有序输入消解原理,证明这个新原理对Horn集也是完备的。同时揭示了它与文献[1]中讨论的正单项有序消解策略的内在关系。最后给出了相应的算法和例子。     

无单调性集值变分不等式的一种投影算法

本文给出了求解无单调性集值变分不等式的一个新的投影算法,该算法所产生的迭代序列在Minty变分不等式解集非空且映射满足一定的连续性条件下收敛到解.对比文献[10]中的算法,本文中的算法使用了不同的线性搜索和半空间,在计算本文所引的两个数值例子时,该算法比文献[10]中的算法所需迭代步更少.     

序列的一种无组合系数的根表示

本文在讨论了组合数C_x~k等在GF(q)上的多元多项式表示的基础上,给出了序列的一种避免组合系数的根表示法,并利用它对两个有重根的反馈多项式生成序列之积的线性复杂性进行了讨论.     

形如2kp+1的数的素性检验

本文初步探讨了如何快速检验一个大数n是素数(这里n-1含有大的素因子)的算法问题以及如何生成一个大素数p使得p-1有大的素因子q的算法问题.我们给出了形如n=2kp+1的数的素性检验的多项式时间算法,这里p是一个给定的大素数,k是正整数满足22k＜2kp.该算法的计算量为O(log32n).然后我们给出了生成一个大素数p使得p-1有大的素因子q的算法,其中q满足q＞(p-1)/log2(p-1).特别地,我们给出了判定并生成一个安全素数p的算法.     

SOME COMBINATORIAL PROBLEMS ON ORDERED TREES

Some formulas are established to calculate the number of leaves on all structurallydifferent ordered trees with n nodes,and the total leaf path length and the total node pathlength for those trees.Certainly,respective average numbers are obtained(the average pathlength may be considered as the average height of random ordered trees with n nodes),Actually,this paper presents a general method dealing with some classes of combinaorialproblems on ordered trees.     

The CRT is the scaling limit of unordered binary trees

We prove that a uniform, rooted unordered binary tree (also known as rooted, binary Pólya tree) with n leaves has the Brownian continuum random tree as its scaling limit for the Gromov‐Hausdorff topology. The limit is thus, up to a constant factor, the same as that of uniform plane trees or labeled trees. Our analysis rests on a combinatorial and probabilistic study of appropriate trimming procedures of trees. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 467–501, 2011     

The rotation graph of binary trees is Hamiltonian

In this paper we study the rotation transformation on binary trees and consider the properties of binary trees under this operation. The rotation is the universal primitive used to rebalance dynamic binary search trees. New binary search tree algorithms have recently been introduced by Sleator and Tarjan. It has been conjectured that these algorithms are as efficient as any algorithm that dynamically restructures the tree using rotations. We hope that by studying rotations in binary trees we shall gain a better understanding of the nature of binary search trees, which in turn will lead to a proof of this “dynamic optimality conjecture”. We define a graph, RG(n), whose vertex set consists of all binary trees containing n nodes, and which has an edge between two trees if they differ by only one rotation. We shall introduce a new characterization of the structure of RG(n) and use it to demonstrate the existence of a Hamiltonian cycle in the graph. The proof is constructive and can be used to enumerate all binary trees with n nodes in constant time per tree.     

On the average number of nodes in a subtree of a tree

For any tree T (labelled, not rooted) of order n, it will be shown that the average number of nodes in a subtree of T is at least $\text{(n + 2)}\text{3}$, with this minimum achieved iff T is a path. For T rooted, the average number of nodes in a subtree containing the root is at least $\text{(n + 1)}\text{2}$ and always exceeds the average over all unrooted subtrees. For the maximum mean, examples show that there are arbitrarily large trees in which the average subtree contains essentially all of the nodes. The mean subtree order as a function on trees is also shown to be monotone with respect to inclusion.     

On the average shape of monotonically labelled tree structures

Let $\text{B}$_k denote one of the families of binary trees, t-aray trees (t> 2) or ordered trees with nodes labelled monotonically by elements of {1 < 2 < ? < k}. The average height of the j-th leaf of the trees of $\text{B}$_k with exactly n nodes is shown to converge to a finite limit (depending on k and j) for n → ∞. The limit is determined explicitly for small values of k and its asymptotic behaviour in j and k is investigated. Some recent results on the average shape of rooted tree structures appear as special cases.     

Properties of Subtree-Prune-and-Regraft Operations on Totally-Ordered Phylogenetic Trees

We study some properties of subtree-prune-and-regraft (SPR) operations on leaflabelled rooted binary trees in which internal vertices are totally ordered. Since biological events occur with certain time ordering, sometimes such totally-ordered trees must be used to avoid possible contradictions in representing evolutionary histories of biological sequences. Compared to the case of plain leaf-labelled rooted binary trees where internal vertices are only partially ordered, SPR operations on totally-ordered trees are more constrained and therefore more difficult to study. In this paper, we investigate the unit-neighbourhood U(T), defined as the set of totally-ordered trees one SPR operation away from a given totally-ordered tree T. We construct a recursion relation for | U(T) | and thereby arrive at an efficient method of determining | U(T) |. In contrast to the case of plain rooted trees, where the unit-neighbourhood size grows quadratically with respect to the number n of leaves, for totally-ordered trees | U(T) | grows like O(n³). For some special topology types, we are able to obtain simple closed-form formulae for | U(T) |. Using these results, we find a sharp upper bound on | U(T) | and conjecture a formula for a sharp lower bound. Lastly, we study the diameter of the space of totally-ordered trees measured using the induced SPR-metric. Received May 18, 2004     

On Weighted Depths in Random Binary Search Trees

Following the model introduced by Aguech et al. (Probab Eng Inf Sci 21:133–141, 2007), the weighted depth of a node in a labelled rooted tree is the sum of all labels on the path connecting the node to the root. We analyse weighted depths of nodes with given labels, the last inserted node, nodes ordered as visited by the depth first search process, the weighted path length and the weighted Wiener index in a random binary search tree. We establish three regimes of nodes depending on whether the second-order behaviour of their weighted depths follows from fluctuations of the keys on the path, the depth of the nodes or both. Finally, we investigate a random distribution function on the unit interval arising as scaling limit for weighted depths of nodes with at most one child.     

On Rotations and the Generation of Binary Trees

The rotation graph, G_n, has vertex set consisting of all binary trees with n nodes. Two vertices are connected by an edge if a single rotation will transform one tree into the other. We provide a simpler proof of a result of Lucas that G_n, contains a Hamilton path. Our proof deals directly with the pointer representation of the binary tree. This proof provides the basis of an algorithm for generating all binary trees that can be implemented to run on a pointer machine and to use only constant time between the output of successive trees. Ranking and unranking algorithms are developed for the ordering of binary trees implied by the generation algorithm. These algorithms have time complexity O(n²) (arithmetic operations). We also show strong relationships amongst various representations of binary trees and amongst binary tree generation algorithms that have recently appeared in the literature.