关于整正则有向图的补图与联图

把补图与联图这两种二元运算应用于正则有向图,发现无向正则图中的一些定理在有向图中亦成立,使定理的应用范围更加宽广,在此基础上进一步探讨了其成为整谱图的条件,从而得到了构造整谱有向图的新方法,可以用来构造新的整谱有向图.     

用循环矩阵构造整谱有向图

通过研究循环图的结构特征与其谱之间的关系,得到循环图是整谱图的条件,并由此获得了一种全新的构造整有向图的方法,可以找到了一些新的整有向图.     

(aKa,b)类整谱图

图G是一个简单图,图G的补图记为(G),如果G的谱完全由整数组成,我们就说G是整谱图.G=Ka,b是完全二部图,本文确定了图类(aKa,b)中的所有的整谱图.     

用广义线图构造整谱图

线图在图的谱理论研究中起着重要的作用.对一些整谱图,运用一种全新的广义线图算子方法,构造出了一系列无穷多个新的整谱图.     

^- αKα,b 类整谱图

图G是一个简单图,图G的补图记为^- G ,如果G的谱完全由整数组成,我们就说G是整谱图.G=Ka,b是完全二部图,本文确定了图类^- αKα,b 中的所有的整谱图.     

几类整谱图

研究二部半正则图的补图、二部补图的特征多项式公式，给出几个特殊图类的谱，得到几类整谱图的充要条件及一些新的整谱图类。     

^—αKaUβKb,b类整图

设图G是一个简单图,图G的补图记为G.如果G的谱完全由整数组成,就称G是整谱图.讨论了当u1=a+b且a-1>b时,aKa U(3B+2)Kb,b不是整谱图;当u1=a+b且a≤b时,aKa UBKb,b(a=1,B=1,a=3或2,b=6)是整谱图.     

循环图的Kirchhoff指标

图G的Kirchhoff指标定义为G中所有点对之间的电阻距离之和,记为Kf(G).图G为循环图,如果图G的邻接矩阵是循环矩阵;图G为整谱图,若它的特征值全为整数.该文利用循环图的Laplacian谱,讨论了循环图的Kirchhoff指标下界;借助Ramanujan和,利用Euler函数和Mobius函数,得到了一个关于整循环图的Kirchhoff指标的简便计算公式.这样无须求出整循环图的特征值,也可求整循环图的Kirchhoff指标.     

广义核-卫星图的无符号拉普拉斯谱

广义核-卫星图是一种特殊的连图,是很多图类的自然推广.借助矩阵的数值特征理论刻画了核-卫星图和广义核-卫星图的无符号拉普拉斯谱.利用所得结果构造了几类无符号拉普拉斯整谱图,推广了几个现有的相关结果.     

一类新的整谱图

设是一个简单的连通图,若的邻接矩阵的特征值全为整数,则称为整谱图.利用移接变形的方法,构造了一些新的整谱图.运用矩阵理论,证明了下列结论:若是由顶点为3的完全图通过复制次后,将其中每个图的一个顶点粘接在一起而成的图,这样具有个顶点.则是整谱图当且仅当i=k(k-1)/2,k∈Z+.     

基于核的有向强连通图计算机随机生成算法

针对图论算法研究和算法测试对随机生成有向强连通图的需求,在深入研究有向强连通图和极小有向强连通图的结构组成的基础上,提出了有向强连通图核的概念。参考有向连通图的随机生成算法,给出了一种有向强连通图的随机生成算法,并对该算法进行了测试。对具有上千个节点及上万条弧的强连通图的随机生成,采用该算法时间都在1 s以内,生成的结果能很好地应用于图论研究,以作为图论算法的随机测试用例。     

七点有向θ图的图设计

设Kv是一个v点的有向完全图,G是一个简单有向图,Kv的一个G-设计,记为(v,G,1)-GD,是指一个二元组(X,B),其中X为Kv的点集,B为Kv的一些子图(也称为区组)构成的集合,使得任一子图(区组)与G同构,且Kv的任意两个不同点组成的有向边恰在B的一个区组中出现。研究了七点有向图的图设计的存在性问题。     

“虚工件”中刀具排列优化算法

针对柔性制造系统中一块托板上装夹几个相同或不同工件组成的一个实体——“虚工件”的工艺安排中的刀具排序问题,提出了一个新的算法.利用这一算法,可以很方便地从“虚工件”工艺安排的相同刀具中找出一个共用刀具数最多的序列,从而实现刀具排序最优化的目的.     

无收点的有向图代数

对于有向图代数的研究通常是假定图是无收点的，对于一个有收点（没有任何边以其为起点的顶点）的有向图E往往要把它处理成无收点的图F，而且使得C^*（E）与C^*(F）间有良好的关系。据此给出一种方法，并且证明了C^(E)是C^*(F)的C^*－子代数，随之给出几个比较有趣的推论。     

具有第3大Wiener指数的有向图

通过有向图的Wiener指数,可以给有向网络的平均距离和节点的中介中心性赋有限的值,进而应用于大规模网络的分析.在所有n阶有向图中,有向圈C^→_n能取到极大Wiener指数,C^→+_n能取到第2大Wiener指数,利用反证法及分类讨论法对有向图的Wiener指数进行研究,得出了具有第3大Wiener指数的有向图,并刻画了相应的极图.     

一类特殊的双色有向图的本原性

文章研究了只有两个圈C1,C2的双色有向图,给出了这类双色有向图本原的充分必要条件.     

一种并行的网格资源协同分配方法

针对网格系统中资源协同分配的实时性问题,分析了现有的基于有向无环图的资源映射方法,提出了一种并行资源协同分配算法.该算法采用有向无环图表示每个应用,然后,将所得到的这些图合并成一个有向无环图并对其进行分层,最后,对每层中应用任务的资源分配问题并行处理.分析表明,该并行资源协同分配算法降低了系统中资源调度时间,提高了资源分配的效率,从而能够满足系统实时性要求.