双星的带宽

本文研究了双星图的带宽问题,给出了它的计算公式。     

一些特殊树的对偶带宽

图G的对偶带宽是指图G中相邻两点最小标号差的最大值。确定了一些特殊树的对偶带宽，主要结果如下：(1)如果树T有n个顶点，并且其最大度△(T)不小于[n/2]，那么树T的对偶带宽等于n一△(T)的充要条件为T是双层星且其内星的中心为最大度顶点；(2)完全二叉树T2,k的对偶带宽等于2^k-1；(3)等高单毛虫树Pm,n的对偶带宽为[mn/2]。     

一类树问题的快速并行算法

本文给出了一类树问题的快速并行算法.这些问题包括:求树中任意两顶点之间的路径和路径长度、求所有顶点的深度等.以这些基本算法为基础,给出了求树中任意两个顶点的最小公共祖先问题、边修改动态最小生成树问题和树同构问题的并行算法.本文使用的模型是单指令流多数据流共享存贮器并行计算机,允许多个处理机同时读存贮器的一个单元的内容但不允许同时写,称这种模型为CREW PRAM.对n个顶点的树,以上算法均使用O(n)个处理机,时间复杂度为O(logn).按Cook的定义,证明了以上问题都属于NC类.     

毛虫图的带宽

求出毛虫图的带宽的计算公式并给出一个较简洁的证明，讨论了此带公式的计算复杂性问题，提出一种更简单的算法。     

两类图的带宽和上界

设Ｇ是有ｎ个顶点的简单图．ｆ：Ｖ（Ｇ）→｛１,２,…,ｎ｝是双射。定义Ｓ（Ｇ）＝ｍｉｎＳｆ（Ｇ）,其中Ｓｆ（Ｇ）＝∑／∈Ｅ｜ｆ（ｕ）－ｆ（ｖ）｜,称Ｓ（Ｇ）为Ｇ的带宽和,得到了树及无三角形图的带宽和上界。     

一类交錯树

Ringel猜想是说,所有的树都是优美树,这个猜想至今尚未解决,是图论中的一个引人注目的难题,1979年,K.M.Koh等人提出交错树的概念,对于Ringel猜想的研究起了很大的推动作用,本文的结果是证明一类树是交错树。     

似双星树的自同态型

刻画了似双星树的自同态型, 并且给出了它在不同的自同态下的计数.     

一类树的匹配唯一性

本文证明：若ｎ∈Ｚｅ＾＋则Ｔ形树Ｔ（１,３,ｎ）匹配唯一当且仅当ｎ≠６。     

一类树的优美性

本文研究了1星与n星点接树的优美性,给出了若干树的优美标号。     

一类树的优美性的讨论

在优美图的问题中，Ｒｏｓａ猜想树是优美的；本文讨论了一类树，用Ｔｎｍ表示。     

一类平面图的生成树数目

利用平面图的对偶图的Kirchhoff矩阵来求一些平面图的生成树数目,求这类平面图的生成树数目比直接利用Cayley公式要简单,且该方法对于同一类的平面图可以进一步推广.     

有向最优树的一个新算法

本文给出了有向最优树的一个新的有效算法，证明了此算法的时间复杂度为Ｏ（ｎ４），并给出一个数字例子     

有序树、根树和树与某些自然数之间的一一对应关系

本文由有序树、根树和树的路长序列出发,定义了有序树、根树和树的价格,从而在有序树、根树和树与某些自然数之间建立了一一对应关系。     

生成根树的递归算法

刘家壮给出了生成根树的一种算法。本文通过引进根树的递归生成的思想，给出了另一种算法，它的时间复杂性是线性的。     

一类树关于能量的序

称一个图G的所有特征根的绝对值的和为G的能量,用E(G)表示.用Tn,d表示具有n个顶点,直径为d的树集.这里3 0d 0n-2,设T(n,d;n1,n2,…,nd-1)∈Tn,d是由路v0v1…vd的顶点vi(1 0i 0d-1)粘结ni条悬挂边得到的树,显然n=d+1+∑id=-11ni.令Tn,d={T(n,d;0,…,ni,0,…,0)|n=ni+d+1}.本文对树集Tn,d中的树依能量进行了排序.     

具有约束条件的谱系树拟合

本文提出了一种新的具有约束条件的谱系树拟合模型。着重介绍了具有已知先代的拟合,并指出有序样品的聚类为该模型的应用特例。     

有向树的叶子数目

农庆琴和黄承兴介绍了树的叶子数目和度序列之间的关系.在这篇文章里,笔者把一些结果由无向树推广到有向树当中.当知道有向树的度序列的时候,可以直接计算出树的叶子数目,也可以通过计算机用搜索的方法计算.     

一类优美树的构造

给出了将一类优美树序列列接到路上，生成优美树的一种构造方法。     

一类树的Hosoya指数

图的Hosoya指数是指图中的匹配总数.本文给出了恰有两个最大度顶点的树的最大Hosoya指数,并刻画了取得极值时的图.