具有给定叶数的T叉树的组合参数

本文考察了(m,n)T叉树的结构,并进一步研究了(m,n)T叉数的下列重要组合参数:叶路径总长度,结点路径总长度,叉数路径总长度。     

有向树的几个组合问题

本文计算有n个结点,m个叶子和具有叶路径长度为s的有向树的个数,以及n个结点,结点路径总长度为r的有向树个数。从而,解决了有向树的叶路径总长度,结点路径总长度的计算问题。     

正则m叉树T的S(n)={Ki:1≤i≤n}-因子数的递归公式

在正则m叉树T中,删除K2及端点关联边,通过所得子正则m叉树中分枝点、叶数和m之间内在联系,本文导出正则m叉树T的S(n)={Ki:1≤i≤n}-因子数递归公式.特别当m=2时,正则2叉树递归公式为:At=A2t/2+2A2t/4At/2,t为正则2叉树T的叶数.     

正则m叉树T的S(n)={Ki:1≤i≤n}-因子数的递归公式

在正则m叉树T中,删除K₂及端点关联边,通过所得子正则m叉树中分枝点、叶数和m之间内在联系,本文导出正则m叉树T的S⁽ⁿ⁾={K_i:1≤i≤n}-因子数递归公式.特别当m=2时,正则2叉树递归公式为:A_t=A_t/2²+2A_t/4² A_t/2,t为正则2叉树T的叶数.     

顾客为子树结构的树上反中心选址问题

顾客为子树结构的树上反中心选址问题是在树T上寻找一点(位于顶点处或在边的内部),使得该点与子树结构的顾客之间的最小赋权带加数距离尽可能地大.给出了该问题的一个有效算法,其时间复杂度为O(cn+sum from j=1 to m n_j),其中n_j为各子树T_j的顶点个数,c为不同的子树权重个数,n为树的顶点数.     

按字典序遍数K分树

本文研究了Ll-限制K分树,文中用叶子的层数表示一个K分树,每个具有n个叶子的K分树对应一个n个正整数组成的序列.首先给出由n个正整数组成的序列代表一个具有n个叶子的Ll-限制K分树的充分必要条件.然后给出一个字典序列出所有具有n个叶子的Ll-限制K分树的算法.     

有序树的一个计数问题(英文)

我们在本文中研究了具 m 个内节点和 n 个叶子的有序树的个数。令 O_(m,n)为此数,我们得到 O_(m,n)的一个递推公式:O_(m,n)=sum from i=1 to n O_(m-i,i)(?),m,n≥1,还得到 O_(m,n)的一个显式表达式:O_(m,n)=1/n(?),m,(?)≥1.     

一类速度不同的具有m台通用机的n组工件的排序问题

研究的目的在于解决实践中对多组任务的优化排序问题,即在最短的时间内完成所有给定的任务,由于这类问题往往都是NP完全问题,人们通常寻求其近似算法．文中提出了一种改进的LPT算法,利用。首先空闲”准则,讨论了将n组工件安排在n台速度不同的专用机,m台速度小于专用机的通用机上的C‰。。问题,得到了利用该近似算法所得的解T与最优解T＊的—个估计：T/T＊≤2＋（n-2）/（m＋1）     

灵活应用“1” 巧解不等式

不等式中有一类题,如果能根据题目特征,灵活应用“1”进行穿针引线,将获得赏心悦目的简单解法. 解设a,b,m,n∈R ,且m n=1,比较 T= 与的大小. 分析初看本题无从下手、非常困难,但只要注意到已知条件中的“1=m n”,且Q中的m、n与T中的m、n在方次上的差别,不难想到下面活用“1”的解法.     

带固定工件的单机排序问题1｜FB, rj,pmtn｜∑j Uj的多项式算法

研究具有若干固定工件和自由工件,其中固定工件必须在指定时间窗内加工,而自由工件具有不同交工的时间,并且其加工可以中断的单机排序问题,其目标是极小化工件的误工数.该问题可以表示为1|FB,rj,pmtn|∑j Uj.首先讨论了问题的几个重要性质,以此为基础建立了求解该问题的动态规划算法,其时间复杂度为O(n4+m log m),其中m和n分别是固定工件数和自由工件数.     

对称的高逼近阶多小波的构造

本文基于已有的对称多小波,给出构造对称的高逼近阶多小波的一个显式算法．具体地,假设Φ（x）：=（φ1（x）…．,φr（x））T是一个具有逼近阶m的对称加细函数向量．对于任意非负整数n,一个具有逼近阶m＋n的新对称加细函数向量Φ^new（x）：=（φ1^new（x）…．,φr^new（x））^T可由上述算法构造出来．另外,揭示了Φ（x）与Φ^new（x）之间的关系．为了使我们的结果具体化,从具有逼近阶4的三次Hermite函数出发,构造了一个具有逼近阶6的对称加细函数向量．     

图的指数多个最大亏格嵌入与完全图的亏格嵌入

本文研究一般图的最大亏格嵌入的计数问题及其应用. 结果表明: 一个连通图往往有指数级别多个最大亏格嵌入. 特别地, 一个简单的n阶3-正则图G至少具有${(\sqrt{2})}^{m+n+\frac{\,\alpha}{\,2}}$个不同的最大亏格潜入, 其中α与m分别是G的最优树T的内部节点数目和G&;#8722;T的奇连通分支数目. 值得注意的是: (不同)图的最大亏格与最小亏格之间存在着某些必然联系. 事实上, 作为以上结果的一个直接应用, 证明了如下结果: 对于充分大的形如12s+4, 12s+7, 12s+10的自然数n, 完全图K_n至少具有$C2^{\frac{\,n}{\,4}}$个不同的最小亏格嵌入, C是一个与n关于模12剩余类有关的常数. 这些结果从本质上改进了V. P. Korzhik与H.-J. Voss所得到的结果, 并且所用的方法更加直接而简洁.     

具有离散参数齐次随机场线性预测

设{X(m,n)}是含有两个取整数值 m,n 的齐次随机场,它的线性预测问题的一般提法是:设 T 及 T′是平面上格子点(m,n)的二个集合,当点(m,n)∈T 时,{X(m,n)}值已观察到,而当点(m′,n′)∈T′时,{X(m′,n′)}值未知,现在要以已观察到的值的线性组合及其均方意义下的极限去预测未观察到的值{X(m′,n′),(m′,n′)∈T′},使均方误差最小。江泽培教授首先研究了这个问题。后有许多文献继续这个问题的研究(例如文献[2—     

树网络上f模式最优广播问题的线性算法

网络G的一个结点v上的一次广播是指从它将一个消息传递给若干相邻结点.所谓f模式广播,是指结点v在一次广播中至多向f(v)个相邻结点传递信息(f为给定的整值函数).假定每一次广播的执行时间为一单位.网络G的广播过程是广播的时间安排,使所有结点均获得消息.最优广播问题是求总时间最少的广播过程.在G是树网络情形,文献中已给出时间界为O(n2)的算法.本文给出线性时间的简捷算法.     

字典序地生成有序根树的一个算法

§1.引言由于树的生成在计算机科学中有着重要应用,近年来许多文章研究了树的生成,其中大多数文章是讨论2分树及 k 分树的生成.研究一般有序根树的文章尚少.文献[1]给出了有序根树的一个序列表示法,并描述了一个生成有序根树的算法.文献[2]及[3]讨论了生成2分树及 k 分树的算法.本文用0,1序列表示有序根树,并给出了一个字典序地生成具有 n 个顶点的所有有序根树的算法.本文的表示法及算法与文献[1]中所提方法不同.本算法亦可用来生成具有 n 个叶子的所有2分树.它比[2]中的算法更简单.本文中未加说明的术语皆见[1].     

具有有界变量的瓶颈分配问题的一个并行算法(英文)

本文提出一并行算法求解具有优个约束以及n个非负有界变量的瓶颈资源分配问题,若有m台处理机,在一定条件下该并行算法的复杂度为O(n(n+logm))。     

图的指数多个最大亏格嵌人与完全图的亏格嵌入

本文研究一般图的最大亏格嵌入的计数问题及其应用.结果表明:一个连通图往往有指数级别多个最大亏格嵌入.特别地,一个简单的n阶3-正则图G至少具有(2~(1/2))~(m n (α/2))个不同的最大亏格潜入,其中α与m分别是G的最优树T的内部节点数目和G-T的奇连通分支数目.值得注意的是:(不同)图的最大亏格与最小亏格之间存在着某些必然联系.事实上,作为以上结果的一个直接应用,证明了如下结果:对于充分大的形如12s 4,12s 7,12s 10的自然数n,完全图K_n至少具有C2~(n/4)个不同的最小亏格嵌入,C是一个与n关于模12剩余类有关的常数.这些结果从本质上改进了V.P.Korzhik与H.-J.Voss所得到的结果,并且所用的方法更加直接而简洁.     

不带微商的边界型求积公式

本文在不带微商项的条件下,对一些特殊区域构造了具有最高代数精确度的边界型求积公式。还对某些较广泛的区域解决了构造3次边界型或非边界型求积公式的“最少结点数”的问题。 首先,我们在立方体区域上将Sadowsky的42点5次边界型求积公式的结点个数减少到32点,并证明了要构造立方体区域上的5次边界型对称求积公式,结点个数不能少于32。文中还构造出n维双层球壳区域上具有最高(3次)代数精度和最少结点个数((2n+2)点)的边界型求积公式。因此,[5]中构造出的3维双层球壳区域上的8点3次边界型求积公式是“最少结点数”的求积公式。最后,证明了对于2维、3维轴对称区域(即关于所有坐标轴都对称的区域)构造3次求积公式,至少分别用到4个和6个结点。对于n维球域构造3次求积公式至少要用到2n个结点。 本文出现的求积公式都是不带微商项的。     

Dijkstra算法的一个改进

本文得到了一种Dijkstra算法的改进算法，如果最短路问题具有n个点和m条边，那么改进算法把问题的计算复杂性从原来的O(nlogn m)降低为O(nlogn M)(M≤m)。     

递归树的若干枚举特征

递归树由Meir和Moon定义作非平面增长树的一种，且所有节点出度都是允许的．本文首先在n个节点的递归树集合和n-1个元素的排列之间建立一个新的──对应，这个对应能同时给出树叶子和排列中的路段之间的对应和树叶子数和排列中的路段数之间的密切关系．同时还研究递归树的各种枚举特征，诸如节点的分类枚举（内节点和叶子节点、偶节点和奇节点，具不同出度的节点）和通路长度枚举（接各种节点分类）．