树映射的单侧γ-极限点集与拓扑熵

本文讨论了树映射的单侧γ-极限点集与吸引中心的关系，得到了树映射具有正拓扑熵的几个等价条件．此外，还得到了树映射是强非混沌以及逐片单调树映射的拓扑熵为零的几个等价条件．     

σ-映射的等度连续性

讨论了σ-映射的等度连续性，得到了σ-映射的等度连续性的几个充要条件。     

树映射具有正拓扑熵的几个等价条件

本文讨论树映射的拓扑熵,得到树映射具有正拓扑熵的几个等价条件。     

乘积G-空间中周期跟踪性和等度连续的研究

介绍了拓扑群作用下乘积空间中G-周期跟踪性和G-等度连续的概念,利用乘积映射的性质,研究了乘积映射f×g与分映射f和g在这些动力学性质方面的关系,得到如下结果:1)乘积映射f×g具有G-周期跟踪性当且仅当f具有G_1-周期跟踪性,g具有G_2-周期跟踪性;2)乘积映射f×g具有G-等度连续当且仅当f具有G_1-等度连续,g具有G_2-等度连续.这些结论弥补了拓扑群作用下乘积空间中G-周期跟踪性和G-等度连续理论的缺失.     

树环中的流量疏导问题研究

H为定义在树环G上的一个超图,将H的每条超边映射为G中不同的映射树,称为超边在G中的嵌入问题.超图在树环中的嵌入问题即为寻找H在G中的最优映射使得G中任一边被H所有超边的映射经过的最大次数最小.应用超图嵌入圈(MCHEC)问题的算法可得超图嵌入树环问题的一个2-近似算法.     

集值映射空间上的基数函数

讨论了集值映射空间在赋予点态收敛拓扑或紧开拓扑下的权数,特征,网络权,稠密度等基数函数,利用自然映射,诱导映射和嵌入等方法将单值连续映射空间的有关结论推广到集值映射空间类上.     

树映射的非游荡集与拓扑混合性

设 T是个树 ,C0 ( T)表示 T上所有的连续自映射 (即 :树映射 )的集合 ,W={ fn:n≥ 2是自然数 ,f∈ C0 ( T) } .讨论了每一点都是非游荡点的树映射的性质 ,并证明了 :若混合映射 f∈ W( W在 C0 ( T)内的闭包 )且 T的每个端点都不是 f的不动点 ,则存在 g∈ C0 ( T)及自然数 k>1使 f=gk.     

区间和圆周上的distal自映射

本文研究distal连续自映射,给出了区间和圆周上distal连续自映射的刻画,并证明了对于连续自映射,等度连续性不能蕴涵distal性.     

非混沌的树映射

设f是树T上的连续自映射,SAP(f),ω(f),Ω(f)分别是f的强几乎周期点集,ω-极限集,非游荡集.本文证明下面几条是等价的(i)f是非混沌的;(ii)SAP(f)=ω(f);(iii)f|Ω(f)是逐点等度连续的;(iv)f|ω(f)是逐点等度连续的;(v)f是一致非混沌的.     

非混沌的树映射

设f是树T上的连续自映射,SAP(f),ω(f);Ω(f)分别是f的强几乎周期点集,ω-极限集,非游荡集.本文证明下面几条是等价的:(i)f是非混沌的;(ii)SAP(f)=ω(f);(iii)fΩ(f)是逐点等度连续的;(iv)f│ω(f)是逐点等度连续的;(v)f是一致非混沌的。     

Tree template matching in unranked ordered trees

We consider the problem of tree template matching, a type of tree pattern matching, where the tree templates have some of their leaves denoted as “donʼt care”, and propose a solution based on the bottom-up technique. Specifically, we transform the tree pattern matching problem for unranked ordered trees to a string matching problem, by transforming the tree template and the subject tree to strings representing their postfix bar notation, and then propose a table-driven algorithm to solve it. The proposed algorithm is divided into two phases: the preprocessing and the searching phase. The tree template is preprocessed once, and the searching phase can be applied to many subject trees, without the need of preprocessing the tree template again. Although we prove that the space required for preprocessing is exponential in the size of the tree template in the worst case, we show that for a specific class of tree templates, the space required is linear in the size of the tree template. The time for the searching phase is linear in the size of the subject tree in the worst case. Thus, the algorithm is asymptotically optimal when one needs to search for a given tree template, of constant to logarithmic size, in many subject trees.     

On component-size bounded Steiner trees

A Steiner tree is a tree interconnecting a given set of points in a metric space such that all leaves are given points. A (full) component of a Steiner tree is a subtree which results from splitting the Steiner tree at some given points. A k-size Steiner tree is a Steiner tree in which every component has at most k given points. The k-Steiner ratio is the largest lower bound for the ratio between lengths of a minimum Steiner tree and a minimum k-size Steiner tree for the same set of points. In this paper, we determine the 3-Steiner ratio in weighted graphs.     

m重似星树的谱半径

仅有一个顶点的度大于2的树称为似星树.
在一棵似星树的每个一度点粘接一棵似星树构成的图称为$m$重似星树.
Gutman 和L. Shi给出了似星树谱半径的一个界.
在本文中我们给出了另外一个更简洁的证明方法并做了深入的讨论,
同时给出了$m$重似星树谱半径的一个最好界.     

Flexible isosurfaces: Simplifying and displaying scalar topology using the contour tree

The contour tree is an abstraction of a scalar field that encodes the nesting relationships of isosurfaces. We show how to use the contour tree to represent individual contours of a scalar field, how to simplify both the contour tree and the topology of the scalar field, how to compute and store geometric properties for all possible contours in the contour tree, and how to use the simplified contour tree as an interface for exploratory visualization.     

Tree template matching in ranked ordered trees by pushdown automata

We consider the problem of tree template matching in ranked ordered trees, and propose a solution based on the bottom-up technique. Specifically, we transform the tree pattern matching problem to a string matching problem, by transforming the tree template and the subject tree to strings representing their postfix notation, and then use pushdown automata as the computational model. The method is analogous to the construction of string pattern matchers. The given tree template is preprocessed once, by constructing a nondeterministic pushdown automaton, which is then transformed to the equivalent deterministic one. Although we prove that the space required for preprocessing is exponential to the size of the tree template in the worst case, the space required for a specific class of tree templates is linear. The time required for the searching phase is linear to the size of the subject tree in both cases.     

基于CHAID决策树的个人收入分析

本文提出了应用CHAID决策树方法来分析国民个人收入。首先本文全面分析了CHAID决策树的构造过程,最后通过实证分析,从大量的个人信息数据集中,运用CHAID决策树构建出了一个分析模型,该模型提供了许多潜在的、有用的信息。     

Random cutting and records in deterministic and random trees

We study random cutting down of a rooted tree and show that the number of cuts is equal (in distribution) to the number of records in the tree when edges (or vertices) are assigned random labels. Limit theorems are given for this number, in particular when the tree is a random conditioned Galton–Watson tree. We consider both the distribution when both the tree and the cutting (or labels) are random and the case when we condition on the tree. The proofs are based on Aldous' theory of the continuum random tree. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Adaptive discretization of convex multistage stochastic programs

We propose a new scenario tree reduction algorithm for multistage stochastic programs, which integrates the reduction of a scenario tree into the solution process of the stochastic program. This allows to construct a scenario tree that is highly adapted on the optimization problem. The algorithm starts with a rough approximation of the original tree and locally refines this approximation as long as necessary. Promising numerical results for scenario tree reductions in the settings of portfolio management and power management with uncertain load are presented.     

Galton——Watson~���ľֲ����޵�һ������

Take any subcritical offspring distribution with bounded support and consider the corresponding Galton--Watson tree. In this short note we condition this Galton--Watson tree on large width and show that the conditioned tree does not converge locally to any random tree with at most one infinite spine.     

A CAPACITY EXPANSION PROBLEM WITH BUDGET CONSTRAINT AND BOTTLENECK LIMITATION

1 IntroductionIn [2] tl1e authors considered a type of coustrained maximim capacity path problem whichcan be described briefly as: kuowing the costs for expallding one unit of capacity along differentedge8 of a l1etwork aud the availabIe budget, how to iucrease the caparities of the edges so thattlle capasity between any pair of nodes in the lletwork can be raised unifornily to the maximumextent? As the total cost is a summation of the expansion costs on all edges, this problem i8related to mi…