树的3-彩虹控制数的上界

对树的3-彩虹控制数进行研究,首先用构造法找到直径较小的树的3-彩虹控制数的上界.再通过分类讨论思想和数学归纳法得到一般的阶n大于等于5的树的3-彩虹控制数的上界.     

Strong Circuit Double Cover of Some Cubic Graphs

Let C be a given circuit of a bridgeless cubic graph G. It was conjectured by Seymour that G has a circuit double cover (CDC) containing the given circuit C. This conjecture (strong CDC [SCDC] conjecture) has been verified by Fleischner and Häggkvist for various families of graphs and circuits. In this article, some of these earlier results have been improved: (1) if contains a Hamilton path or a Y‐tree of order less than 14, then G has a CDC containing C; (2) if is connected and , then G has a CDC containing C.     

基于动态调整的GA-SVM多分类二叉树的方法

基于遗传算法的支持向量机决策树多分类方法仍然存在错误累积的问题,累积的错误往往使分类准确率下降,分类效果变差,存在全局优化缺陷的问题;并且在每个节点进行二分类常用的实数编码切分方法,效率低下。针对这两方面的问题,提出从根节点开始逐层构造二叉树,运用二进制编码的遗传算法进行每一阶段的二叉树构造。二进制编码对于每个节点的分类以及进行交叉、变异更高效,不用考虑从什么位置切分。针对越靠近根节点产生的误差对后续节点分类误差的累积影响,提出一种动态调整的方法,此方法对每个节点赋予权重再进行对权重的调整使得整体的分类误差减小,最终得到二叉树的全局最优,从而提高分类精度。通过实验并进行五折交叉验证表明,DABT-SVM比多种传统的支持向量机多分类算法在全局优化能力和分类精度上有很大的提升。验证了该算法的可行性和有效性。     

基于近景摄影测量技术的关键林分参数的获取研究

为了研究利用摄影测量技术来获取和反演关键林分参数的准确性,从而为推算其他林分因子提供相关思路,以实现快捷高效的森林资源调查。选取了一片亚热带人工混交林作为实验样地,并利用样地中6个优势树种的实测数据分别构建了多个胸径-树高、冠幅回归模型,并得到了对应的最优模型;在此基础上,利用从点云数据中获取的树高和冠幅,反演出单株树木的胸径;最后通过分析实测胸径与基于点云计算得到的胸径之间的相关性来判断算法的准确度。结果表明:(1)6个树种的实测树高与基于点云获取的树高相关性较高,R~2均在0.7以上;(2)多数树种的实测冠幅与获取的冠幅相关性偏低,其中仅喜树的冠幅R~2高达0.88,其余树种的冠幅R~2最高只有0.61;(3)最优回归模型拟合胸径与实测胸径的回归分析中,发现高大落叶乔木比如马褂木、喜树的R~2均在0.7以上,而落叶小乔木比如樱花树以及柏类树木比如圆柏、龙柏等R~2最高仅0.25,雪松的R~2则为0.54。     

A class of solvable reaction-diffusion processes on a Cayley tree

Considering the most general one-species reaction-diffusion processes on a Cayley tree, it has been shown that there exist two integrable models. In the first model, the reactions are the various creation processes, i.e. °°→•°, °°→•• and °•→••, and in the second model, only the diffusion process •°→°• exists. For the first model, the probabilities P_l(m;t), of finding m particles on the lth shell of the Cayley tree, have been found exactly, and for the second model, the functions P_l(1;t) have been calculated. It has been shown that these are the only integrable models if one restricts consideration to the L+1-shell probabilities P(m₀,m₁,…,m_L;t).     

On spanning tree congestion of graphs

Let G be a connected graph and T be a spanning tree of G. For e∈E(T), the congestion of e is the number of edges in G connecting two components of T−e. The edge congestion ofGinT is the maximum congestion over all edges in T. The spanning tree congestion ofG is the minimum congestion of G in its spanning trees. In this paper, we show the spanning tree congestion for the complete k-partite graphs and the two-dimensional tori. We also address lower bounds of spanning tree congestion for the multi-dimensional grids and the hypercubes.     

Approximation algorithms for constrained generalized tree alignment problem

In generalized tree alignment problem, we are given a set S of k biologically related sequences and we are interested in a minimum cost evolutionary tree for S. In many instances of this problem partial phylogenetic tree for S is known. In such instances, we would like to make use of this knowledge to restrict the tree topologies that we consider and construct a biologically relevant minimum cost evolutionary tree. So, we propose the following natural generalization of the generalized tree alignment problem, a problem known to be MAX-SNP Hard, stated as follows:

Constrained Generalized Tree Alignment Problem [S. Divakaran, Algorithms and heuristics for constrained generalized alignment problem, DIMACS Technical Report 2007-21, 2007]: Given a set S of k related sequences and a phylogenetic forest comprising of node-disjoint phylogenetic trees that specify the topological constraints that an evolutionary tree of S needs to satisfy, construct a minimum cost evolutionary tree for S.

In this paper, we present constant approximation algorithms for the constrained generalized tree alignment problem. For the generalized tree alignment problem, a special case of this problem, our algorithms provide a guaranteed error bound of 2−2/k.     

Genus distribution of ladder type and cross type graphs

In this paper a method is given to calculate the explicit expressions of embedding genus distribution for ladder type graphs and cross type graphs. As an example, we refind the genus distribution of the graph J _n which is the first class of graphs studied for genus distribution where its genus depends on n. This work was supported National Natural Science Foundation of China (Grant Nos. 10571013, 60433050) and the State Key Development Program of Basic Research of China (Grant No. 2004CB318004)     

A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree

Let X_n be the number of cuts needed to isolate the root in a random recursive tree with n vertices. We provide a weak convergence result for X_n. The basic observation for its proof is that the probability distributions of are recursively defined by , where D_n is a discrete random variable with ? , which is independent of . This distributional recursion was not studied previously in the sense of weak convergence. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009