基于平图的两种有向链环的Homfly多项式

给定一个平图,Jaeger为之联系了一个有向链环,并建立了该图的Tutte多项式和所得有向链环的Homfly多项式之间的关系.这促使我们考虑其它给图联系有向链环的方式并得到类似的关系.文中给定一个平图,通过其中间图构造了两种有向链环,得到了这两种有向链环的Homfly多项式和该图的Tutte多项式之间的关系,其中一个关系推广了Jaeger的工作.根据上述得到的两个关系,给出了两类有向链环的Homfly多项式.     

两个图同谱的充要条件

0 引言 有相同特征多项式的两个图称为是同谱的。至今为止,除了按定义直接计算特征多项式外,还没有简单的办法通过图的邻接矩阵A的性质,或者通过图的组合性质来判定两个图是否同谱,本文利用顿公式,找到了图的特征多项式系数与该图的组合性质的关系,从而得到了两个图同谱的一个充要条件,这个充要条件在代数上表现为两个图的邻接矩阵各L次幂的迹均相等;在图的组     

论局部标定图的色多项式及其应用

引入了局部标定图的概念,使得标定图和非标定图都成为它的两上特殊情形,它的色多项式屯标定图的色项式和非标定图的色多项式。     

图两参数的关系及图的分类

本文讨论了与图的伴随多项式和匹配多项式密切相关的两类参数的关系,并刻画了匹配多项式参数Ｒｍ（Ｇ）＝１,０,－１,－２,－３的图簇。     

两类图的伴随多项式

本文运用伴随多项式的递归公式,求出了两类图的伴随多项式。     

新型三角多项式图

揭示了传统的三角多项式图的本质是一种随机过程 ,给出了另外 2种新的三角多项式图 ,即新形式的三角多项式图和等欧氏距离的三角多项式图 .通过证明 ,这 2种新的三角多项式图都具有传统三角多项式图所不可替代的优良性质 ,由此拓宽了三角多项式图的应用范围     

色本原多项式的应用

组合计数和图的着色是组合数学与图论的重要内容,而Pólya计数定理和计算图色数的色多项式是研究它们的主要工具,在文献[3]中,杜清晏教授将两者结合,定义了色轨道多项式和色本原多项式,并提出了P-图和SC-图的概念。本文讨论了具体图Cn以及由图Cn组合的图的色轨道多项式和色本原多项式,还给出色轨道多项式和色本原多项式在化学上的应用。     

几类图的Signless Laplacian特征多项式

对于一个简单图G,称矩阵Q（G）=D（G）＋A（G）是图G的Signless Laplacian矩阵,多项式QG（λ）=det（λI—Q）是图G的特征多项式。本文给出了在完全二部图K2,a-2上两种不同的加边方式所得图类和在C3的一个顶点上悬挂P=n-3条边所得图类的Signless Laplacian矩阵特征多项式。     

关于简单图的独立集多项式

定义了简单图的独立集多项式，讨论了图的独立集多项式与图的匹配多项式的关系，给出了图的独立集多项式的结构特征．     

两类图的色性分析

通过计算两类图的伴随多项式，证明了它们是伴随等价；因而构造了两类色等价图类     

完全图的seidel特征多项式及其谱

设A（G）是图G的邻接矩阵,J是全1方阵,I是单位矩阵．称S（G）=J-I-2A（G）为图G的seidel矩阵,与之对应的多项式SG（λ）=｜λI—S（G）｜称为图G的seidel特征多项式．本文给出了完全图Kn的seidel特征多项式及其谱．     

图多项式以及图的不同特征根个数

设G是具有邻接矩阵A的简单图,P(x)是有理系数多项式,如果P(A)是某个图的邻接矩阵,我们记这个图为P(G)。我们考虑这样的问题:给一个图G,什么样的多项式P(x)给出一个图P(G)?这个图是什么样的图?当G是星图时,本文对上述问题给出完全的回答。然后,还导出一个连通正则图的不同特征根个数的新的下界。     

一个大规模网络撕裂的有效算法

该文对大规模网络分析的撕裂技术提出一种拓扑算法，该算法从求最小割集的角度，对网络进行最优撕裂，其算法理论比较简单，保证在多项式时间内获得撕裂支路数最少的撕裂结果。以图论中邻接矩阵为基础，给出了该算法的理论证明，通过实例应用可以看出该算法效果简捷有效。     

网格图的零指标的研究

一个图的零指标是指该图的邻接矩阵的零特征值的个数.二部图的可以应用到化学中,用来检验分子的稳定性.在本文中,我们对网格图标进行了研究,找到了此图类中关于零指标的一个递归关系.借助此任何一个网格图(Pm×Pn)的零指标可以在O(log2 n)时间内计算出来.     

强正则图的途径计数和邻接矩阵分类

强正则图的邻接矩阵A的方幂Am可以表示为A,单位矩阵和全1矩阵的线性组合,进而由该表达式得到强正则图的任意两点之间任意长的途径计数公式,最后给出强正则图的邻接矩阵的奇异性和非奇异性分类.     

一种基于图论的入侵检测方法

在入侵检测系统中引入图论的相关理论并提出了一种基于图论的入侵检测方法,将数据对象之间相似度的关系转换到图论的邻接矩阵中,再将邻接矩阵转换为关联矩阵,以表示数据对象之间的相似关系.利用最速下降法求得最佳的转换矩阵,以完成关联矩阵的块对角矩阵转换而达到数据聚类效果和鉴别出正常数据与入侵攻击数据的类别.同时,利用KDD CUP 1999数据集对系统进行仿真.结果表明,所提出的入侵检测方法能够在很低误警率的情况下达到比模糊C均值聚类算法更高的检测率.     

图论算法的可视化操作平台设计

用Delphi 7.0开发一种程序软件,为图论的可视化算法提供方便的操作平台.用户只需用鼠标点击窗体,就能方便地画出一个图,并由此自动生成相应的邻接矩阵与邻接表提供给相关的图论算法使用.使用该操作平台便于收到图论算法的可视化效果.     

整循环图的能量公式

循环图是互联网络环境下的分布式并行计算中一类非常重要的拓扑图．一个图叫做循环图,如果它是循环群上的Cayley图,也即它的邻接矩阵是一个循环矩阵．若循环图的邻接矩阵的特征值全为整数,则称此循环图为整循环图．图的能量是图的特征值的绝对值的和．本文主要研究整循环图的能量计算公式．     

连通图的拉普拉斯特征值之和的下界

图的拉普拉斯矩阵是指其度对角矩阵和其邻接矩阵之差.设S(G)是图G的前两大的拉普拉斯特征值之和,在所有n阶的连通图中,S(G)的最小值一旦确定,相应的极图也被唯一地刻画.     

剖分图的联图的距离矩阵相关谱

利用正则图的关联矩阵与其邻接矩阵及其线图的邻接矩阵间的关系,证明了两个正则图的剖分边边联图、剖分点点联图和剖分点边联图的距离谱、距离拉普拉斯谱和距离无符号拉普拉斯谱可表示为原图的邻接谱.