Growth of Lévy trees

We construct random locally compact real trees called Lévy trees that are the genealogical trees associated with continuous-state branching processes. More precisely, we define a growing family of discrete Galton–Watson trees with i.i.d. exponential branch lengths that is consistent under Bernoulli percolation on leaves; we define the Lévy tree as the limit of this growing family with respect to the Gromov–Hausdorff topology on metric spaces. This elementary approach notably includes supercritical trees and does not make use of the height process introduced by Le Gall and Le Jan to code the genealogy of (sub)critical continuous-state branching processes. We construct the mass measure of Lévy trees and we give a decomposition along the ancestral subtree of a Poisson sampling directed by the mass measure. T. Duquesne is supported by NSF Grants DMS-0203066 and DMS-0405779. M. Winkel is supported by Aon and the Institute of Actuaries, EPSRC Grant GR/T26368/01, le département de mathématique de l’Université d’Orsay and NSF Grant DMS-0405779.     

晶体学与准晶体学点群的母子群关系

依据群论，得出了准晶体学点群的直积或半直积推导算式；依据结晶学理论，绘出了五角、八角、十角和十二角晶系各点群的极赤投影图.据此推导出了每一个准晶体学点群的全部最大子群，从而推导并绘制出了三维晶体学和准晶体学点群之间的母子群关系(60个点群的“家谱”).该“家谱”以最大子群链的图解形式直观地给出了每个点群的最小母群和最大子群. 关键词： 准晶体 晶体 点群 最大子群 最小母群 群链     

Corrections of proofs for Hansen and Mélot's two theorems

The Randi? index R(G) of a (chemical) graph G is also called connectivity index. Hansen and Mélot [Variable neighborhood search for extremal graphs 6: analyzing bounds for the connectivity index, J. Chem. Inf. Comput. Sci. 43 (2003) 1-14] in their paper, characterized the chemical trees of given order and number of pendent vertices which have the minimum and maximum Randi? index, respectively. In this note, we point out the mistakes in the proofs of their results Theorems 8 and 10, while we still believe that the two theorems are true, and then we give their corrected proofs.     

最小树的一般算法

本文根据设计并行算法的基本原则,给出了最小树的两个对偶定理.在此基础上,建立了两种对偶的同步并行算法的雏型.这两种算法恰恰在对偶的意义下,概括了以往的最小树算法.     

带有边集限制的最均匀支撑树问题

本在无向网络中，建立了带有边集限制的最均匀支撑树问题的网络模型．中首先解决最均匀支撑树问题，并给出求无向网络中最均匀支撑树的多项式时间算法；然后，给出了求无向网络中带有边集限制的最小树多项式时间算法；最后，在已解决的两个问题的基础上解决了带有边集限制的最均匀支撑树问题．     

On the Spectral Radius of Trees with the Given Diameter d

Let T denote a tree with the diameter d(d≥2) and order n. Let P^*d,r,n-d-1denote the tree obtained by identifying the rth vertex of path Pd l and the center of starKl,K1,n-d-1, where r = r(d) is the integer part about d 2/2. Then p(T)≤ p(P^*d,r,n-d-1), andequality holds if and only if T≌P^*d,r,n-d-1     

The Computable Dimension of I-Trees of Infinite Height

We study computable trees with distinguished initial subtree (briefly, I-trees). It is proved that all I-trees of infinite height are computably categorical, and moreover, they all have effectively infinite computable dimension.     

Identifying phylogenetic trees

A central problem that arises in evolutionary biology is that of displaying partitions of subsets of a finite set X on a tree whose vertices are partially labelled with the elements of X. Such a tree is called an X-tree and, for a collection of partitions of subsets of X, characterisations for the existence and uniqueness of an X-tree that displays have been previously given in terms of chordal graphs. In this paper, we obtain two closely related characterisations also in terms of chordal graphs. The first describes when identifies an X-tree, and the second describes when a compatible subset of is of maximum size.     

最小费用k度限制树对策

本在Glover—Klingman算法及最小费用支撑树对策的基础上，讨论了最小费用k度限制树对策问题．利用威胁、旁支付理论制订了两种规则，并利用优超、策略等价理论分别给出了在这两种规则下最小费用k度限制树对策核心中的解，从而证明了在这两种规则下其核心非空．     

Locally minimal uniformly oriented shortest networks

The Steiner problem in a λ-plane is the problem of constructing a minimum length network interconnecting a given set of nodes (called terminals), with the constraint that all line segments in the network have slopes chosen from λ uniform orientations in the plane. This network is referred to as a minimum λ-tree. The problem is a generalization of the classical Euclidean and rectilinear Steiner tree problems, with important applications to VLSI wiring design.A λ-tree is said to be locally minimal if its length cannot be reduced by small perturbations of its Steiner points. In this paper we prove that a λ-tree is locally minimal if and only if the length of each path in the tree cannot be reduced under a special parallel perturbation on paths known as a shift. This proves a conjecture on necessary and sufficient conditions for locally minimal λ-trees raised in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222]. For any path P in a λ-tree T, we then find a simple condition, based on the sum of all angles on one side of P, to determine whether a shift on P reduces, preserves, or increases the length of T. This result improves on our previous forbidden paths results in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222].