关于生成树数目的公式

本文得到了比 Cayley 公式更一般的关于生成树数目的公式:τ(K_n·a_1·a_2·…·a_k)=(multiply from i=1 to k a_1)n~(k-2).     

概率树在全概率公式中的应用

针对应用全概率公式计算复杂事件概率时遇到的问题,提出采用概率树进行分析的方法．该方法能使试验的整个过程更加清楚直观,易于理解和分析;而且乘法原理与加法原理的应用,便于掌握和计算,从而能使复杂问题得以有效解决．     

几种复合图生成树个数的一般求法

若一个图能够由某一个或某几个运算作用于不相交的图上而得到，则称该图为复合图．记ｔ（Ｇ）为图Ｇ的生成树个数，Ｈ（Ｇ）为图Ｇ的Ｋｉｒｃｈｈｏｆｆ矩阵，用“ｏ”表示图的某种运算，如“＋”，“×”，“合成”等，本文研究了Ｈ（ＧｏＧ′）与Ｈ（Ｇ），Ｈ（Ｇ′）的特征值关系，给出了ｔ（ＧｏＧ′）的一般性公式，提供了几种复合图生成树个数的一般性公式，提供了几种复合图生成树个数的一般求法，大大推广了［２，３］的结果，同时简化了许多图类生成树个数表达式的求法．     

关于司特林公式的概率证明

本文利用中心极限定理与拉氏变换法给出了司特林公式的一个简捷证明．     

数列通项公式的求法

在关于由递推关系求通项公式的问题中,有一类递推关系既含有项,又含有和,即项和混杂,若一并考虑,则困难重重.对此种式子应先消元:即利用项与和之间的关     

一类数列极限的概率求法

通过建立适当的随机模型,应用概率方法可以确定一类具有复杂结构的数列的极限．本通过举例说明这种方法的运用．     

一类数列极限的概率求法

通过建立适当的随机模型,应用概率方法可以确定一类具有复杂结构的数列的极限,本文通过举例说明这种方法的运用     

数列通项公式的求法

数列是一种以自然数 1,2 ,… ,ｎ作为自变量的函数 ,给出数列的方式常常有两种 ,一是由项与项数的关系给出的即通项公式法 ,二是由相邻项的关系给出的即递推公式法 .这两种方式都反映出了数列的结构特点和构成规律 .那么怎样由己知数列的递推公式来探求数列的通项公式呢 ?本文通过具体实例介绍几种常用的方法 .一、转化成等差等比数列此方法主要根据数列的递推关系式的特征 ,通过适当变形 ,构造出关于某个整体的等比或等差数列 ,求出该整体的通项后再求所求数列的通项 .例 1　已知数列 {ａｎ}中 ,ａ1 =1,ａｎ =3ａｎ-1 + 1(ｎ =1,2 ,3,… ) …     

数列通项公式的求法

数列是高一数学教与学的重点和难点,它方法灵活,技巧性强,往往难以把握．数列通项又是数列中的难中之难,同学们常因不得解题要领而束手无策,那么,如何帮助大家系统地掌握数列通项公式的求法呢?下面通过实例来展示常规题型的解法,希望能对大家有点帮助．     

数列通项公式的求法

在关于由递推关系求通项公式的问题中,有一类递推关系既含有“项”,又含有“和”,即“项”“和”混杂,若一并考虑,则困难重重．对此种式子应先消元：     

一些图的生成树数

图 G 的生成树是它的连通子图(子树).本文精确地计算出了一些图的生成树的数目, 例如双心轮图、双柄扇图等等.     

树上最大支撑森林对策

本文在无向网络上定义了最大支撑森林对策,利用图论知识研究了树上最大支撑森林对策的核和核仁,并将所得结论推广到无关网络上.     

The Complexity of Minimum Ratio Spanning Tree Problems

We examine the complexity of two minimum spanning tree problems with rational objective functions. We show that the Minimum Ratio Spanning Tree problem is NP-hard when the denominator is unrestricted in sign, thereby sharpening a previous complexity result. We then consider an extension of this problem where the objective function is the sum of two linear ratios whose numerators and denominators are strictly positive. This problem is shown to be NP-hard as well. We conclude with some results characterizing sufficient conditions for a globally optimal solution.     

Euclidean Bounded-Degree Spanning Tree Ratios

Let _K be the worst-case (supremum) ratio of the weight of the minimum degree-K spanning tree to the weight of the minimum spanning tree, over all finite point sets in the Euclidean plane. It is known that ₂ = 2 and ₅ = 1. In STOC 94, Khuller, Raghavachari, and Young established the following inequalities: 1.103 < ₃ \le 1.5 and 1.035 < ₄ \le 1.25. We present the first improved upper bounds: ₃ < 1.402 and ₄ < 1.143. As a result, we obtain better approximation algorithms for Euclidean minimum bounded-degree spanning trees. Let _K ^(d) be the analogous ratio in d-dimensional space. Khuller et al. showed that₃ ^(d) < 1.667 for any d. We observe that ₃ ^(d) < 1.633.     

The Minimum Stretch Spanning Tree Problem for Typical Graphs

Acta Mathematicae Applicatae Sinica, English Series - With applications in communication networks, the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the...     

几类图的支撑树的个数

推广了计算图的支撑树个数的递归公式,解释了组合计数原理的用法.用组合技巧和常系数线性递归序列的解法,对n步梯、n-棱柱、Mobius n-棱柱及有关图,找到了计算它们的支撑树的个数的若干公式.     

A Spanning Tree with High Degree Vertices

Let G be a connected graph, let ${X \subset V(G)}$ and let f be a mapping from X to {2, 3, . . .}. Kaneko and Yoshimoto (Inf Process Lett 73:163–165, 2000) conjectured that if |N _G (S) ? X| ≥ f (S) ? 2|S| + ω _G (S) + 1 for any subset ${S \subset X}$ , then there exists a spanning tree T such that d _T (x) ≥ f (x) for all ${x \in X}$ . In this paper, we show a result with a stronger assumption than this conjecture; if |N _G (S) ? X| ≥ f (S) ? 2|S| + α(S) + 1 for any subset ${S \subset X}$ , then there exists a spanning tree T such that d _T (x) ≥ f (x) for all ${x \in X}$ .     

On a Spanning Tree with Specified Leaves

Let k ≥ 2 be an integer. We show that if G is a (k + 1)-connected graph and each pair of nonadjacent vertices in G has degree sum at least |G| + 1, then for each subset S of V(G) with |S| = k, G has a spanning tree such that S is the set of endvertices. This result generalizes Ore’s theorem which guarantees the existence of a Hamilton path connecting any two vertices. Dedicated to Professor Hikoe Enomoto on his 60th birthday.     

Stable routing under the Spanning Tree Protocol

The Spanning Tree Protocol routes traffic on shortest path trees. If some edges fail, the traffic has to be rerouted consequently, setting up alternative trees. In this paper we design efficient algorithms to compute polynomial-size integer weights so as to enforce the following stability property: if q=O(1) edges fail, traffic demands that are not affected by the failures are not redirected. Stability is a goal pursued by network operators in order to minimize transmission delays due to the restoration process.     

Stirling数的概率表示和应用

本文证明了第二类Ｓｔｉｒｌｉｎｇ数Ｓ（ｎ，ｋ）和第一类Ｓｔｉｒｌｉｎｇ数ｓ（ｎ，ｋ）都是常见的随机变量和的矩，从而使概率论的方法和技巧，在组合和式计算、恒等式的发现与证明以及渐近估计等方面得到许多新的结果．