相对于Wiener-Hosoya指标的最小树

Wiener-Hosoya指标是由Randic在文[1]中引入的一个指标,旨在揭示分子结构与其化学性质的更进一步的关系.任意给定点数及直径,本文确定了相对于该指标的最小树.进一步地,具有任意给定点数的最小的16个树也得到确定.     

From Isomorphic Rooted Trees to Isometric Ultrametric Spaces

For every finite ultrametric space X we can put in correspondence its representing tree T_X. We found conditions under which the isomorphism of representing trees T_X and T_Y implies the isometricity of ultrametric spaces X and Y having the same range of distances.     

UTV Expansion Pack: Special-purpose rank-revealing algorithms

This collection of Matlab 7.0 software supplements and complements the package UTV Tools from 1999, and includes implementations of special-purpose rank-revealing algorithms developed since the publication of the original package. We provide algorithms for computing and modifying symmetric rank-revealing VSV decompositions, we expand the algorithms for the ULLV decomposition of a matrix pair to handle interference-type problems with a rank-deficient covariance matrix, and we provide a robust and reliable Lanczos algorithm which – despite its simplicity – is able to capture all the dominant singular values of a sparse or structured matrix. These new algorithms have applications in signal processing, optimization and LSI information retrieval. AMS subject classification 65F25     

Maximal Flow in Branching Trees and Binary Search Trees

A capacitated network is a tree with a non negative number, called capacity, associated to each edge. The maximal flow that can pass through a given path is the minimun capacity on the path. Antal and Krapivski (Phys Rev E 74:051110, 2006) study the distribution for the maximal flow from the root to a leaf in the case of a deterministic binary tree with independent and identically distributed random capacities. In this paper their result is extended to three classes of trees with a random number of children and dependent random capacities: binary trees with general capacities distribution, branching trees with exchangeable capacities and random binary search trees.     

升值之言该如何听

自今年6月中国暗示将松动人民币汇率以来,人民币升值幅度仅为0．4％,这大大低于华盛顿的期待,因此,中美两国的关系日益紧张起来。随着失业率的膨胀,以及选举年即将到来,美国国会再一次将人民币汇率摆上了议事日程：9月6日,华盛顿两位高官为缓和中美关系前往北京,就人民币及其他重要问题进行高峰会晤,以期达成共识。     

Embeddings and Other Mappings of Rooted Trees Into Complete Trees

Let T ⁿ be the complete binary tree of height n, with root 1 _n as the maximum element. For T a tree, define and . We disprove a conjecture of Kubicki, Lehel and Morayne, which claims that for any fixed n and arbitrary rooted trees T ₁ T ₂. We show that A(n; T) is of the form where l is the number of leaves of T, and each q _j is a polynomial. We provide an algorithm for calculating the two leading terms of q _l for any tree T. We investigate the asymptotic behaviour of the ratio A(n; T)/C(n; T) and give examples of classes of pairs of trees T ₁, T ₂ where it is possible to compare A(n; T ₁)/C(n; T ₁) and A(n; T ₂)/C(n; T ₂). By calculating these ratios for a particular class of pairs of trees, we show that the conjecture fails for these trees, for all sufficiently large n. Kubicki, Lehel and Morayne have proved the conjecture when T ₁, T ₂ are restricted to being binary trees. We also look at embeddings into other complete trees, and we show how the result can be viewed as one of many possible correlation inequalities for embeddings of binary trees. We also show that if we consider strict order-preserving maps of T ₁, T ₂ into T ⁿ (rather than embeddings) then the corresponding correlation inequalities for these maps also generalise to arbitrary trees.     

Trees and B-series

Numerical Algorithms - The connection between trees and differential equations was pointed out in the classic paper by Cayley (Phil. Mag. 13, 172–176 1857). Trees were also used in the work...     

Transversals in Trees

The total embedding polynomial of a graph G is the bivariate polynomial where is the number of embeddings, for into the orientable surface , and is the number of embeddings, for into the nonorientable surface . The sequence is called the total embedding distribution of the graph G; it is known for relatively few classes of graphs, compared to the genus distribution . The circular ladder graph is the Cartesian product of the complete graph on two vertices and the cycle graph on n vertices. In this article, we derive a closed formula for the total embedding distribution of circular ladders.     

Paired-domination of Trees

Let G= (V, E) be a graph without isolated vertices. A set SV is a paired-dominating set if it dominates V and the subgraph induced by S,S, contains a perfect matching. The paired-domination number _p(G) is defined to be the minimum cardinality of a paired-dominating set S in G. In this paper, we present a linear-time algorithm computing the paired-domination number for trees and characterize trees with equal domination and paired-domination numbers.     

Optimal Partition Trees

We revisit one of the most fundamental classes of data structure problems in computational geometry: range searching. Matoušek (Discrete Comput. Geom. 10:157–182, 1993) gave a partition tree method for d-dimensional simplex range searching achieving O(n) space and O(n ^1−1/d ) query time. Although this method is generally believed to be optimal, it is complicated and requires O(n ^1+ε ) preprocessing time for any fixed ε>0. An earlier method by Matoušek (Discrete Comput. Geom. 8:315–334, 1992) requires O(nlogn) preprocessing time but O(n ^1−1/d log ^O(1) n) query time. We give a new method that achieves simultaneously O(nlogn) preprocessing time, O(n) space, and O(n ^1−1/d ) query time with high probability. Our method has several advantages:

Trees in tournaments

Letf(n) be the smallest integer such that every tournament of orderf(n) contains every oriented tree of ordern. Sumner has just conjectures thatf(n)=2n–2, and F. K. Chung has shown thatf(n)(1+o(1))nlog₂ n. Here we show thatf(n)12n andf(n)(4+o(1))n.     

Maximally Symmetric Trees

We characterize the best model geometries for the class of virtually free groups, and we show that there is a countable infinity of distinct best model geometries in an appropriate sense – these are the maximally symmetric trees. The first theorem gives several equivalent conditions on a bounded valence, cocompact tree T without valence 1 vertices saying that T is maximally symmetric. The second theorem gives general constructions for maximally symmetric trees, showing for instance that every virtually free group has a maximally symmetric tree for a model geometry.     

How to play MetaSquares

The rules of the game MetaSquares as well as computational results suggest to follow a “lattice” strategy. This strategy is presented, and by counting lattice points it is shown to be essentially best possible.      

关于极限的讲法

众所周知,极限是高等数学所有重要概念的基础,又是教学的公认难点,特别是用“ε-δ”语言证明极限的题目．本文是作者在新疆大学讲授这一内容时所做的一些探索性工作,主要方法是：提前引入无穷小概念,以特殊无穷小为标准尺对极限证明题进行论证,使得证明思路清晰、论述简单、易于掌握．     

关于极限的讲法

众所周知,极限是高等数学所有重要概念的基础,又是教学的公认难点,特别是用"ε-δ"语言证明极限的题目.本文是作者在新疆大学讲授这一内容时所做的一些探索性工作,主要方法是:提前引入无穷小概念,以特殊无穷小为标准尺对极限证明题进行论证,使得证明思路清晰、论述简单、易于掌握.     

Monotone Shrinkage of Trees

Abstract

We investigate a new method for regression trees which obtains estimates and predictions subject to constraints on the coefficients representing the effects of splits in the tree. The procedure leads to both shrinking of the node estimates and pruning of branches in the tree and for some problems gives better predictions than cost-complexity pruning used in the classification and regression tree (CART) algorithm. The new method is based on the least absolute shrinkage and selection operator (LASSO) method developed by Tibshirani.     

Trees as Brelot spaces

A Brelot space is a connected, locally compact, noncompact Hausdorff space together with the choice of a sheaf of functions on this space which are called harmonic. We prove that by considering functions on a tree to be functions on the edges as well as on the vertices (instead of just on the vertices), a tree becomes a Brelot space. This leads to many results on the potential theory of trees. By restricting the functions just to the vertices, we obtain several new results on the potential theory of trees considered in the usual sense. We study trees whose nearest-neighbor transition probabilities are defined by both transient and recurrent random walks. Besides the usual case of harmonic functions on trees (the kernel of the Laplace operator), we also consider as “harmonic” the eigenfunctions of the Laplacian relative to a positive eigenvalue showing that these also yield a Brelot structure and creating new classes of functions for the study of potential theory on trees.