论有序树的路长序列

F.Rulkey,与T.C.Hu 1977年和1978年曾用叶子的路长序列分别表示二分树和K分树,从而字典序地遍数了二分树和K分树;1980年朱永津和王建方又用叶子的路长序列表示一个具有路长限制的K分树,从而字典序地生成了所有具有路长限制的K分树。本文将用顶点的路长序列表示一个有序     

树的序列表示法及其在数树上的应用

谢力同等利用有序根树的每个顶点的次得到一个非负整数序列来表示一个有序根树。文献利用根树的每个分支的顶点数来排列各个分支的次序,从而得到一个方法:把所有的不同构的根树、树排列起来,并且能够依次数出来,而本文则利用树的每个顶点所确定的树枝的顶点数作出一个序列来表示一个树。这种表示法与过去的表示法不同,它不依赖于顶点     

论有序根树的顶点次序列

一、引言有序根树在计算机科学中占有重要的地位,因此讨论有序根树的文章很多,如在文献[1]中讨论了字典序地产生2分树;在文献[2]中讨论了字典序地产生2分树和k分树,以及用0,1序列表示的一般有序根树的方式。而在这些文章中用整数序列表示有序根树,又起了重要的作用。     

论有序树次序列间的对偶性

文献[1—3]都给出有序树的一个次序列表示,本文将在文献[3]中给出的次序列之间给出一种对偶关系,从而在具有i个内点和l个外点的有序树的集合与具有l个内点和i个外点的有序树的集合之间建立了一一对应关系。     

关于2树的1因子定理

Bineke等人研究了2树的特征。本文给出了一个2树有1因子的充分必要条件。有3个顶点的2树是一个三角形。当n≥3时,有n 1个顶点的2树T是从有n个顶点的2树T′增加一个新的顶点和一个含这个顶点的三角形     

具有给定叶数的有向树、自由树的计数

在Knuth的名著中,曾对二叉树、有序树、有向树、自由树的一些组合性质及其在计算机科学中的应用作了广泛的讨论,给出了n阶(n个结点)所有结构不同的上述各类树的计数式。近年来,王振宇先后给出了n阶各类树的总叶数公式。作为对上述结果更精细的分类,最     

具有根式不可解特征多项式的最小图

文献[1]的末尾(p。266—267)提出9个关于图谱方面的问题。其中第7个问题为求一个图G,使得其特征多项式Pc(λ)=0根式不可解。 为方便起见,我们将具有根式不可解特征多项式的(无向简单)图叫作不可解的,否则便叫作该图是可解的,Goclsil证明了几乎所有树均是不可解的,但是若用他的方法构作出不可解树则需要有1.1×10~(27)个顶点。在文献[3]中我们找出两个10顶点不可解树,它们如图1所     

简单MCD图的边数的上界

用f(n)(f~*(n))表示具有n个顶点的没有两个等长圈的图(简单图)的最大可能的边数。确定f(n)的问题是Erd(?)s于1975年提出的至今尚未解决的难题。我们称具有n个顶点和f(n)(f~*(n))条边的图(简单图)为MCD图(简单MCD图)。在[2]中,我们已经证明f(n)     

有序树的一个计数问题

在先前的一篇文章里,我们得到了下述结果:令Ω_(m,n)为具m个内点、n个叶子的有序树所成的集合,并令O_(m,n)=|Ω_(m,n)|,则对所有m,n≥1,有     

拟阵的次限制次小基

一、引言大家知道,在连通图上求最小权的支撑树,有许多算法,其中著名的Greedy算法被用来求拟阵的最小基。在连通图上特别指定了一个顶点,求在该顶点具次限制的最小权的支撑树,Glover-klingman也给出了好算法。Burns-Haff给出了图的支撑树按权的大小进行排序的生成算法,并且指出能够把它推广为拟阵基的排序算法。本文主要结果是对一般的拟阵M=     

具有给定叶数的植树、自由树的计数

本文指出文献[1]定理2证明的错误之处,给出具有给定叶数的植树、自由树的计数公式。 以G_(n,m)、T_(n,m)、t_(n,m)分别表示n阶m叶植树、有向树、自由树的个数,其计数级数分别记为G(x,y)、T(x,y)、t(x,y)。     

粘贴DNA计算机模型(Ⅱ): 应用

经典的粘贴DNA计算模型采用单、双链混合型DNA分子编码, 其生物操作具有无需DNA链的延伸、无需生物酶以及DNA链可重复使用等优点, 已经受到不同学科学者的关注. 在经典模型的基础上, 进行一定的扩展与完善, 必对DNA计算机的研究有良好的贡献. 基于此, 对粘贴DNA计算机模型进行了较为深入的研究: (1) 提出了基于粘贴模型的矩阵表达模型; (2) 对经典粘贴模型应用于图与组合优化等方面的研究成果给予综述, 诸如集合覆盖问题、图的顶点覆盖问题、图的Hamilton路与圈问题、图的团与独立集问题、图的生成树与Steiner树问题等; (3) 给出了基于粘贴模型的图的同构问题的算法.     

树的几个计数问题

对于t≥2叉树和有序树,具有r≥0棵非空子树的节点称为r次节点。考虑具有n≥0个节点的t叉树族Γ_n和有序树族~_n,本文建立了以下结果。它们在计算机科学的算法分析中有着直接的应用。 定理1 设b_n是Γ_n中树的总数,g_k~(?)是Γ_(?)中位于第k层的r次节点的总数,并且     

经典Ramsey数R(4,12),R(5,11)和R(5,12)的新下界

已知经典Ramsey数R(m,n)(m,n≥2)是一定存在的,但确定经典Ramsey数R(m,n)是组合数学和图论中著名的难题,至今在理论和方法上尚未见到取得突破的迹象,因此近年来各国学者主要用各种方法借助计算机对一些具体的Ramsey数给出估计。王清贤、谢继国等人沿用文献[4]的方法研究一般的循环图,得到一些Ramsey数的下界。这种方法在用字典排列法产生参数时,由于大量同构的图均要一一考察,占用大量计算机机时。因此我们作出新的尝试:利用素数阶循环图的平移和旋转等性质改进了产生参数的方法,提高了运算效率,得到3个Ramsey数的新下界。     

二阶张量n次幂的表示定理

文[1]利用Cayley-Hamilton定理和罗必塔法则给出了三维空间中二阶张量A的n次幂的表示定理.其表示形式中的系数是由A的特征根给出的.当有重根出现时,则需要用罗必塔法则进行特殊处理,不同的根的分布情况所对应的系数表达式也不一致.显然,这样的结果不便推广到一般的m 维空间上去.     

双周期阵列的迹表示

二维线性递归阵列在二维信息加密、雷达定位、声纳系统等方面有重要应用,因而得到数字通讯、密码学、信息加工和数学等领域专家的重视,二维线性递归阵列的研究主要涉及到多变元的多项式环,而不是主理想环,故与一维序列的研究方法有本质的不同,本义主要给出二维线件递归阵列的一个好的表示,称为迹表示,从而提供一个研究二维阵列结构的有力工具,目前,对于具有极大周期的二维线性递归阵列(即m-阵列)的迹表示在文献中已给出,进而对阵列的线性递归关系对应的理想只有2个生成元,且其一生成元在没有重根的条件下也得到迹表示,本文是研究一般的线性递归阵列,其对应的主理想只要求是Nother环中的理想,我们利用Gr(?)bner基理论,先找出阵列空问的一组特殊的基底,进而得到阵列的迹表     

关于树的带次数路径长度问题

Knuth引入了树的带次数路径长度的概念,对于树的每个叶,将位于此叶到根的路径上的每个内结点的次数求和,再将此结果对诸叶求和,即得一个树的带次数路径长度。Knuth用此概念解决了如何对磁盘构造一个好的合并模式问题。他还给出了一个定理回答下述问题:在具有n个叶子的树中,哪一个树具有最小的带次数路径长度?五年之后,Gbel和Hoede用不同方法给出了同一定理。本文中我们首先研究下列问题:对任一给定的整数n>0,所     

初等线性群之间同构的提升

令R和A为含1交换环,m和n为≥3的整数,考虑同构E_m(R)E_n(A)何时以及怎样才能提升为相应Steinberg群之间的同构.已经证明,若E_m(R)同构于E_n(A),则m=n(见文献[1]),当,n≥4时,任一同构E_n(R)E_n(A)是标准形的,可自然且唯一地提升为St_n(R)到St_n(A)的同构。但情形n=3不同于n≥4,因3维线性群之间存在例外同构(文献[3]及[2]中给出的反例)。本文研究同构E_3(R)E_3(A)能够提升的充要条件。     

严格k可约n竞赛图的计数

如果n竞赛图T_n中任意n—k 1子竞赛图都是可约的,则T_n称为k可约的。如果T_n是k可约的,但不是k 1可约的,则T_n称为严格k可约的。设t(n)和s(n)分别表示n竞赛图和强n竞赛图的所有同构类的个数。对于给定正整数k,设     

二值图像的数字搜索树表示及其线性编码

基于递归分解原则的四元树及八元树是表示二维及三维图像的一类重要的空间数据结构.这类结构传统上以指针方式实现,为了进一步压缩存储,可对结点先序遍历形成线性序列,即线性四元树(Iinear quadtree,简称LQ)及线性八元树(Iinear octree,简称LO)。LQ及LO的压缩编码已接近其极限。本文提出的二值图像的数字搜索树表示及其线性编