图的谱矩公式研究

重构猜想的研究中涉及的一个问题是找出图不变量的完全组。由于图的第k阶谱矩等于图中长为k的闭途径的条数,可知谱矩序列是图的一个重要不变量。通过研究图的结构特征,首先确定能生成长为8的闭途径的所有子图,然后给出图的第8阶谱矩计算公式。     

谱矩与圈数

图G是一个简单图,其中A(G)表示图G的邻接矩阵,Mk(G)是指图G的k阶谱矩,Mk(G)=tr(A(G)k).也就是说,Mk(G)等于图G中长度为k的闭途径的数目.该文借助谱矩给出了计算任意简单图中圈C3、C4、C5的个数的方法.     

关于图Cn1,n2,n3,n4及Cp,q,s的邻接谱

图的谱确定问题是图论中的一个重要问题,它是根据已知的特征值去确定图形,一般说来这是一件很困难的事.图论界的许多学者研究了一些特殊情形,主要涉及图的邻接谱(或图的Laplacian谱)的研究,其研究的一般途径是通过图的邻接矩阵(或Laplacian矩阵)表示,建立图的拓扑结构(特别是图的各种不变量).通过矩阵论,以及组合矩阵论中的经典结论,用于图的拓扑结构的研究.在已有文献的基础上研究了Cn1,n2,n3,n4图和Cp,q,s图的邻接谱问题,得到了不同构的Cn1,n2,n3,n4图及Cp,q,s图没有相同的邻接谱这个结论.     

一类生产安排优化问题的基的特征与基可行解的求法

本文研究形为:的线性规划问题。给出了当(m n)个变量为基变量的充要条件,是以下三个条件同时成立: (1)G不包含奇异闭回路 (2)G的任何两个非奇异闭回路不连接 (3)G中任何一个闭回路与X_(in )(i=1,2,…,n)均不连接     

拟谱分布及其性质

定义了一种谱分布并讨论了这种谱分布的性质，证明了闭算子A为某k阶谱分布的矩量的充要条件是iA生成某k阶分布群，此时1／2（iA)^2生成一个正则半群。     

一类图的谱半径

研究了一类图--风筝图的谱半径.在给定图的最大团数的条件下,通过变量引入,利用Maple数学软件进行数值比较,得出了风筝图邻接谱半径下界的估计;同时,利用变量引入法,通过求解线性递推关系,给出了风筝图邻接谱半径上界的估计.由此给出了风筝图邻接谱半径的一个比较小的取值区间.     

完美匹配树谱半径的进一步排序

用图的谱对图进行分类和排序是图谱理论的研究方向之一.主要研究了完美匹配树依谱半径排序的问题.事实上,到目前为止,具有前七大谱半径的完美匹配树已经排出,且具有第八大至第二十大谱半径的完美匹配树的范围也已经确定,但它们之间的大小顺序还没有具体给出.借助图的移接变形和图的特征多项式等工具,完整地解决了这一问题,具体排出了具有第八大至第二十大谱半径的完美匹配树.     

图的多项式不变量的一个推广

图论中的一个核心问题是研究图的不变量.对于给定的一个平图,可以建立该图的Tutte多项式不变量.一直以来,认为Tutte多项式是最一般的图的不变量.经典的Tutte多项式不变量是含有2个变元x,y的多项式,但是这个多项式却不能区分所有的图.这促使我们考虑可以通过增加变元的方法来细分图的类别.对于给定一个的平图,将图的Tutte多项式不变量进行了推广,得到一个新的n变元多项式,并证明其是图的不变量.进而,也验证它能区分Tutte多项式不能区分的一类图,这类图是给定的一个图与在这个图上再加一些与之不相交的点.     

具有最大无符号拉普拉斯谱半径的拟树

若存在一个顶点,使得删除这个点后得到的图是一个树,则称该图是拟树,该文基于拟树的概念,利用相应的枝节变换,刻画了固定某个顶点的度及给定悬挂点数的所有拟树中具有最大无符号拉普拉斯谱半径的极图.     

固定直径树的极大hyper-Wiener指数

图的hyper-Wiener指数是一种基于距离的图的不变量, 是预测有机化合物的物理化学性质的结构描述符. 利用hyper-Wiener指数的定义及性质,研究了直径至多为4的树的极大hyper-Wiener指数, 给出了计算公式, 并且刻画了相应的极图.     

图的拉普拉斯谱半径对应的特征向量性质及其应用

研究图的拉普拉斯谱半径对应的特征向量的性质及应用,并得到一些有关图的移接变形对拉普拉斯谱半径影响的结果.     

4度点数固定的树的距离谱半径

引入了一种图的变换,得到了距离谱半径的变化规律.进一步研究了四度点数固定的树集,刻画了该图类中距离谱半径最大的极图.最后,讨论了更一般的图类,即度至少为4的点数固定的树集,并确定了极图.     

直径为n-1,n-2和n-3的树的补图的奇异性

利用图谱理论对树的补图的奇异性进行了研究,得到了直径为n-1,n-2和n-3的树的补图的奇异性的一般判断方法,推广了前人的研究成果.     

不含三圈的双圈图的谱半径

Nikiforov等人最近将图谱研究与极值图论相结合,提出了谱Turán型问题:给定一个图F,设G是一个不含子图与F同构的n阶图,那么图G的谱半径至多是多少?双圈图是边数等于顶点数加1的简单连通图。近期,部分学者对双圈图的谱半径进行了研究,确定了双圈图谱半径的第1~10大值和相应的极图。受此启发,研究了不含三圈的双圈图,确定不含三圈的双圈图的谱半径的上界,并刻画了相应的极图。     

判别哈密尔顿图的新方法

提出求一个图的顶点覆盖的VC算法，定义图的VC表示式及其全闭链的概念，证明一个连通无向图是哈密顿图当且仅当其VC表示式含有一条全闭链，并证明对构造全闭链有用的定理和推论。     

最小生成树边与边的权的调整

图的最小生成树已经有了好算法，但当图增加或删去几条边或少数几条边的边调整时，最小生成树的边、权可能发生变化，用原算法寻找最小生成树时，显得比较麻烦．利用破回路算法给出一个简单的 方法．并给出了相应的示例．     

A novel method for solving the multiple traveling salesmen problem with multiple depots

Multi-traveling salesman problem(MTSP) is an extension of traveling salesman problem,which is a famous NP hard problem,and can be used to solve many real world problems,such as railway transportation,routing and pipeline laying.In this paper,we analyze the general properties of MTSP,and find that the multiple depots and closed paths in the graph is a big issue for MTSP.Thus,a novel method is presented to solve it.We transform a complicated graph into a simplified one firstly,then an effective algorithm is proposed to solve the MTSP based on the simplified results.In addition,we also propose a method to optimize the general results by using 2-OPT.Simulation results show that our method can find the global solution for MTSP efficiently.     

关于满Steiner树问题的一个近似算法

满Steiner树问题(TST)是求解一个正则点都是叶子的最小Steiner树问题.Fabio Viduani Martinez等人给出了此问题的近似算法,它的性能比为2ρ-ρ/(3ρ-2)≈2.52,而目前求解Steiner树问题的近似算法的性能比,最小值约为1.550.对满Steiner树问题给出了一个近似算法,并将它的性能比改进为2ρ-3ρ/(6ρ-2)≈2.463.     

等值线图形的扫描线法

一般的等值线图形采用函数值跟踪算法,该法对内部封闭等值线的起点确定比较麻烦。笔者采用面向对象的程序设计方法给出适用于任意形状单元的等值线图的通用扫描线生成方法,采用VC6.0中的MFC实现了三点三角形、六点三角形、四点四边形、八点四边形和九点四边形的计算结果图形显示。并给出了算例。