单圈图最小特征值的Sharp下界

设G是一个具有n个顶点的简单图，λn(G)为图G的最小特征值，而单圈图就是其边数等于点数的连通图，本文给出了单圈图最小特征值的一个Sharp下界，并同时给出达到这个下界的极图。     

有向Cayley图的直径

设Ｇ是一个有限Ａｂｅｌ群，Ｍ是Ｇ的一个二元生成集．Ｇ上的有向Ｃａｙｌｅｙ图Ｄ（Ｃ，Ｍ）是一个以Ｇ为顶点集的有向图，若ｘ，ｙ∈Ｇ，则存在ｘ到ｙ的弧当且仅当ｙ－ｘ∈Ｍ．Ｎ个顶点的所有这种有向Ｃａｙｌｅｙ图的最小直径和平均距离是多少？我们将此问题转化为一个几何问题并由此得到了直径的一个下－２和平均距离的一个下界．这两个界仅当Ｎ＝３ｘ２时可达，这里ｘ是任一自然数．     

一类3—连通图的周长

设G=(V,E)是一个n阶无向简单图,本文证明了:设G是一个3-连通图,若G的每一个最长圈是控制圈,则G的周长c(G)≥min{n,2NC_2}或G同构于Petersen图,其中NC_2={|N(u)∪N(v)||u,v∈V(G),d(u,v)=2}。     

基因组重排问题的一个近似算法

分子生物学中基因无方向的反向基因组重排问题在数学上已被证明是一个NP困难问题．基于断点图的概念，给出一个时间复杂性为O(max{b^(π)，nb(π)})，空间复杂性为0(n)的求其近似最优解的算法．其中n为基因组中基因个数，π=(π1,π2，…，πn)表示n个基因的一种排列，b(π)表示排列π中的断点数．数据实验的结果表明，该近似算法可以求得较好的结果．     

对称群上Cayley图的Hamilton性（Ⅱ）

对于每一个ｎ（≥３）阶连通简单图，都可定义一个相应的对称群上的Ｃａｙｌｅｙ图．本文继续文献［１］证明了每一个连通简单图对应的Ｃａｙｌｅｙ图都是一个Ｈａｍｉｌｔｏｎ图，从而在这方面的问题得到了圆满的解决．     

J._C.Bermond等的一个定理的注

Ｊ．—Ｃ．Ｂｅｒｍｏｎｄ等在［１］中断言：有限阿贝尔群上的连通四正则Ｃａｖｌｅｙ图可分解为两个哈密顿圈的并．但在证明这个结果时，他们漏掉了两种情况．本文将补充其证明．     

Brooks定理的附注

<正> 图的顶点的染色是图论中的重要问题之一。本文从讨论图的色数的上界问题,从而得出Brooks定理的又一证明。1.基本概念如果用颜色去染一个图G的顶点,使得任意有棱相连的两个顶点均有不同的颜色。这样     

关于旋转对称布尔函数性质之研究

旋转对称函数为特殊布尔函数,本文阐述了旋转对称函数的定义,提出了旋转对称函数的性质,并给出了相应的证明,讨论了该函数在k图、bj图、谱系数图中的特点.     

完全偶图的PCS-因子计数

图G的一个PCS-因子是G的一个支撑子图。其中每一个连通分支是路，圈或顶点数大于等于4的星．本文研究完全偶图Km,n的PCS-因子计数。给出了Km,n存在由k个分支构成的PCS-因子的充要条件。以及Km,n的PCS-因子的计数公式．     

无向和有向Euler环游变换图的直径

本文得到了无向和有向Ｅｕｌｅｒ环游交换图的直径的上界．（１）设Ｇ是一个无向Ｅｕｌｅｒ多重图．令Ｑ（Ｇ）＝｛ｖ∈Ｖ（Ｇ）｜ｄｖ的Ｅｕｌｅｒ环游（Ｋ－）变换图Ｅｕ（Ｇ）的直径ｄｉａｍ（Ｅｕ（Ｇ））≤λ（Ｃ）－３．（２）设Ｄ是一个有向Ｅｕｌｅｒ多重图，ｄ（ｖ）＝ｉｄ（ｖ）＝ｏｄ（ｖ），令Ｑ（Ｄ）＝｛ｖ∈Ｖ（Ｄ）｜ｄ（ｖ）≥２｝及。则Ｄ的有向Ｅｕｌｅｒ环游（Ｔ－）变换图Ｅｕ．（Ｄ）的直径我们给出例子说明这两个上界都是最佳可能的．     

基回数为3的自中心图的构造

本文将基回数为3的自中心图分为两类,并以简明的方式分别给出了它们的构造。     

直觉判断矩阵的弱传递性与加型一致性研究

定义了直觉判断矩阵的有向图和有向路概念,证明在一定的条件下直觉判断矩阵的有向图有唯一有向路.利用该结论给出一个简洁的排序方法,并指出这种方法的不足之处.通过反例说明了直觉判断矩阵已有的加型一致性概念与弱传递性概念之间没有必然强弱关系.根据直觉模糊数的得分值和精确度值,利用效用的思想给出直觉判断矩阵加型一致性的新定义,并证明了新定义的加型一致性具有弱传递性.针对一般的直觉判断矩阵, 运用新定义的加型一致性概念以及偏差函数的方法给出了求解直觉判断矩阵的直觉模糊数型权重的模型,并通过算例验证了决策方法的实用性.     

一种高生存性的车载自组网可信路由协议

针对目前车载自组网中路由安全问题,提出一种基于经验信任的可信路由模型.该模型从客观信任的角度引入经验信任的概念作为可信度量的标准,并给出了计算节点经验信任值和信誉度的推荐方法,根据节点的经验信任值设计一种新的动态包转发规则,从而实现车载自组网的可信路由.实验结果表明,该模型较贪婪周边无状态路由(greedy perimeter stateless routing,GPSR)协议具有较高的抵抗自私节点的能力.     

On Power Graphs of Cycles

1.IntrodtlctionAllgral)llsantidigraI7hst'onsi'lered11erearesiml)le.Notationsand(lefinitionsnotdefinedherecanbefoun'lin[ljI-etGbeafinitegroup;In(lSasubsetofGnotcontainingtheidentityelementof(j.We(lefinetheCayley(ligraphCoy(S,G)LZjasfollows.ThevenicesofC'ay(S,G)areelementsofG,andthereisanarcfromgtogswhereverA'6GandseS.IfSIsInversecolosed,thatisifS--l=S,thenthereisanarcfromgitogZifftheTeisanarcfromArZtogi.Inthiscase,any(S,G)IsactuallyagraphwhichiscalledaCayleygraph.Itiswellknownthat…     

一种优化的节点不相交多径路由策略

移动Ad Hoc网络是一种新型的不依赖于固定设施实现通信的无线移动网络,其节点兼具主机和路由器的功能,适用于Ad Hoc网络的路由策略是目前广泛研究的核心问题之一。通过深入研究移动Ad Hoc网络中多径路由协议,以AOMDV算法为基础,提出了一种优化的节点不相交多径路由策略ONDMRP,     

图嵌入算法研究进展

图嵌入算法是将高维网络信息映射至低维后用实数向量表示的一种方法,用于解决推荐系统、社区发现及节点分类等。近年来,随着科技的进步,图数据呈现海量、异构、高维、多模态等特点,机器学习等人工智能算法对高性能的图嵌入算法的需求日益增加,图嵌入已成为国内外人工智能领域的研究热点之一。对图嵌入算法的研究进展、技术原理及基础理论进行了综述,系统概述了已有的主流图嵌入算法,包括基于降维方法的图嵌入、基于矩阵分解的图嵌入、基于网络拓扑结构的图嵌入、基于神经网络的图嵌入、基于生成式对抗网络的图嵌入和基于超图网络的图嵌入,对这些算法进行了分析与比较,并给出了相应的应用场景;归纳总结了常用的测试数据集及其评价标准;最后,展望了图嵌入算法的研究趋势和方向。     

有向网络的复制机制及其相关网络分析

鉴于有向网络比无向网络包含了更多的内在信息, 而复杂网络中的基本统计量往往仅适用于无向网络, 使得有向网络的研究相对缺少, 由此提出了一个有向网络的统计量, 并分析该统计量在相关有向网络研究中的有效性. 考虑到复制是有向网络增长的一个主要动力, 定义了有向网络结点复制率和有向网络复制率的概念, 并利用结点入度分布和复制率研究了有向规则网络、复制模型网络及自然数网络. 结果显示, 完全复制模型和自然数网络的入度具有无标度特性, 其入度分布的幂律指数 都为2, 2个有向网络的复制率 , 而部分复制模型的复制率 . 因此, 有向网络的入度分布、复制率都能很好地解释完全复制模型与自然数网络的相关性, 可作为重要统计量广泛应用于有向网络研究中.     

L形通道布线的展开法

本文提出将L形通道展成直通道的布线方法，对展开后的直通道定义了水平约束、垂直约束、拐角约束、走线约束，利用赋权的混合图反映这四种约束、并逐步将图中的无向边转变成有向边，按照有向图的线网上下关系，完成直通道布线，再收缩冗余布线区变成L形通道布线.     

用Hopfield神经网络解哈密顿回路问题

设PN是一个圆的内接正N边形,圆的直径为1.将一个N个顶点的简单图G的每条边赋权,权重为PN的边长;对于图G中不邻接的各对顶点,先求出这对顶点最短路的长度,再赋予PN中同样长度的路的两端点的距离.如此,将图G的哈密顿回路问题转变成旅行商问题:周游回路最优解的长度是否等于正N边形的周长.为了用Hopfield神经网络方法得到正确的判定,简化了初始状态,引用了动态消元算法.     

神经网络在平面布线 中的应 用

Hopfield给出N个节点完全图K，中求最短Hamilton圈的神经网络方法，若将无自环图看做K，的子图，不难求出Hamilton图的Hamilton圈.不过当节点数增多时，解神经网络动态方程常得到次优解，和Hamilton圈差一两条边，称为准Hamilton圈.利用Hamilton圈和准Hamilton圈，可以画出一个平面图的平面化图，或者将一个非平面图分解为平面化子图，以便平面布线.