无穷区间上二阶奇异微分方程三点边值问题正解的存在性

讨论了一类无穷区间上二阶奇异微分方程三点边值问题正解的存在性和唯一性.通过应用对角延拓原理,不动点指标理论和不等式技巧,得到了该类边值问题正解存在性和唯一性的充分条件,允许非线性项有奇性.     

高密度情形格点Sierpinski地毯上渗流模型无穷开串的唯一性

本文证明高密度情形格点Ｓｉｅｒｐｉｎｓｋｉ地毯上边渗流模型无穷开串的唯一性,同时给出本模型相变存在性的一个新的证明．一种再标度技巧被发展并用作我们证明的主要工具．     

一类非线性无穷多点边值问题正解的存在性

运用锥拉伸与锥压缩不动点理论,讨论了一类非线性二阶常微分方程无穷多点边值问题u″+a(t).f(u)=0,t∈(0,1),u(1)=∑a_iu(ζ_i),u′(0)=∑b_iu′(ζ_i)正解的存在性.其中a∈C([0,1],[0,∞)),ζ_i∈(0,1),a_i,b_i∈[0,∞),f∈C([0,∞),[0,∞))并且满足∑a_i<1,∑b_i<1.推广了已有文献中的一些结果.     

一类无穷多点边值问题正解的存在性

研究一类二阶非线性常微分方程无穷多点边值问题正解的存在性,利用不动点指数理论得到了方程至少存在一个正解的若干充分条件.     

有向网络中具有一个枢纽点的最小支撑树的计算方法

对有向网络中具有一个枢纽点的支撑树的问题和性质进行了研究,给出了在有向网络图中寻找以某一定点为枢纽点的最小支撑树的计算方法,并对算法的复杂性进行了讨论,最后将该算法应用于实际算例的计算．     

一类二阶常微分方程无穷多点边值问题解的存在性

运用Leray-Schauder原理在.f满足至多线性增长的条件下研究了无穷多点边值问题{y'(x)=f(x,y(x),y'(x))+e(x),0x1y(0)=0,y(1)=∞∑i=1a_iy(ξ_i)解的存在性.     

树映射有异状点的一个充要条件

讨论了树上连续自映射的拓扑熵与非稳定流形之间的关系． 证明了：树上连续自映射有异状点的充要条件是其拓扑熵大于零． 因而推广了区间上连续自映射的一个结果．     

一类二阶常微分方程无穷多点边值问题多个正解的存在性

研究了一类二阶非线性常微分方程无穷多点边值问题多个正解的存在性,运用不动点指数理论及Holder不等式得到了方程至少存在两个正解的若干充分条件,推广和改进了相关文献的结果.     

连续树映射非游荡集的拓扑结构

本文研究树（即不含有圈的一维紧致连通的分支流形）上连续自映射的非游荡集的拓扑结构．证明了孤立的周期点都是孤立的非游荡点；具有无限轨道的非游荡点集的聚点都是周期点集的二阶聚点，以及ω－极限集的导集等于周期点集的导集和非游荡集的二阶导集等于周期点集的二阶导集．     

单位无穷范数下边权有界的最小支撑树逆最优值问题

研究了单位$l_{\infty}$范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$, 支撑树$T^0$, 下界向量$\bm{l}$, 上界向量$\bm{u}$及数值$K$, 寻求一个新的边权向量$\bm{\bar{w}}$满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$, 且$T^0$是在向量$\bm{\bar{w}}$下权值为$K$的一个最小支撑树, 目标是在单位$l_{\infty}$范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$的强多项式时间算法。     

Multi-Faithful Spanning Trees of Infinite Graphs

For an end and a tree T of a graph G we denote respectively by m() and m _T () the maximum numbers of pairwise disjoint rays of G and T belonging to , and we define tm() := min{m _T(): T is a spanning tree of G}. In this paper we give partial answers — affirmative and negative ones — to the general problem of determining if, for a function f mapping every end of G to a cardinal f() such that tm() f() m(), there exists a spanning tree T of G such that m _T () = f() for every end of G.     

Random minimal spanning tree and percolation on the N-cube

The N-cube is a graph with 2^N vertices and N2^N−1 edges. Suppose independent uniform random edge weights are assigned and let T be the spanning tree of minimal (total) weight. Then the weight of T is asymptotic to N⁻¹2^N ∑^∞_i=1 i⁻³ as N→∞. Asymptotics are also given for the local structure of T and for the distribution of its kth largest edge weight, k fixed. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 63–82, 1998     

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

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

通讯网络中极小费用生成树的一种算法

针对具有n个通讯站的局域网络,运用增加或调整虚设站的方法,给出一种在混合距离下的极小费用生成树的算法.并就MCM91问题B,求出了极小费用生成树,其总费用小于美国马里兰州里斯勃来莱州立大学数学科学系B.A.Fusaro所提供的论文中的费用.     

Steiner Minimal Trees in Rectilinear and Octilinear Planes

This paper considers the Steiner Minimal Tree （SMT） problem in the rectilinear and octilinear planes. The study is motivated by the physical design of VLSI： The rectilinear case corresponds to the currently used M-architecture, which uses either horizontal or vertical routing, while the octilinear case corresponds to a new routing technique, X-architecture, that is based on the pervasive use of diagonal directions. The experimental studies show that the X-architecture demonstrates a length reduction of more than 10-20%. In this paper, we make a theoretical study on the lengths of SMTs in these two planes. Our mathematical analysis confirms that the length reduction is significant as the previous experimental studies claimed, but the reduction for three points is not as significant as for two points. We also obtain the lower and upper bounds on the expected lengths of SMTs in these two planes for arbitrary number of points.     

有向图中几类支撑树数目的计算公式

将W.T.Tultte提出的计算有向图中以某点为根的支撑出树数目的公式推广到了更一般的情况,并给出了有向图中具有不同特点的支撑树数目的计算公式。     

On the Entropy of Spanning Trees on a Large Triangular Lattice

The double integral representing the entropy S_tri of spanning trees on a large triangular lattice is evaluated using two different methods, one algebraic and one graphical. Both methods lead to the same result

Inapplicability of Asymptotic Results on the Minimal Spanning Tree in Statistical Testing

Penrose has given asymptotic results for the distribution of the longest edge of the minimal spanning tree and nearest neighbour graph for sets of multivariate uniformly or normally distributed points. We investigate the applicability of these results to samples of up to 100 points, in up to 10 dimensions. We conclude that the asymptotic results provide an acceptable approximation only in the uniform case. Their inaccuracy for the multivariate normal case means that they cannot be applied to improve Rohlf's gap test for an outlier in a set of multivariate data points, which depends on the longest edge of the minimal spanning tree of the set.     

Minimum Spanning Trees with Sums of Ratios

We present an algorithm for finding a minimum spanning tree where the costs are the sum of two linear ratios. We show how upper and lower bounds may be quickly generated. By associating each ratio value with a new variable in `image space,' we show how to tighten these bounds by optimally solving a sequence of constrained minimum spanning tree problems. The resulting iterative algorithm then finds the globally optimal solution. Two procedures are presented to speed up the basic algorithm. One relies on the structure of the problem to find a locally optimal solution while the other is independent of the problem structure. Both are shown to be effective in reducing the computational effort. Numerical results are presented.     

On the Minimum Number of Spanning Trees in k‐Edge‐Connected Graphs

We show that a k‐edge‐connected graph on n vertices has at least spanning trees. This bound is tight if k is even and the extremal graph is the n‐cycle with edge multiplicities . For k odd, however, there is a lower bound , where . Specifically, and . Not surprisingly, c₃ is smaller than the corresponding number for 4‐edge‐connected graphs. Examples show that . However, we have no examples of 5‐edge‐connected graphs with fewer spanning trees than the n‐cycle with all edge multiplicities (except one) equal to 3, which is almost 6‐regular. We have no examples of 5‐regular 5‐edge‐connected graphs with fewer than spanning trees, which is more than the corresponding number for 6‐regular 6‐edge‐connected graphs. The analogous surprising phenomenon occurs for each higher odd edge connectivity and regularity.