图的广义p-邻域完整度

当网络中一个节点失效后,邻点受其影响也以某个概率p失效。基于此,提出图的广义p-邻域完整度的概念,将完整度与邻域完整度统一起来。通过参数值的计算、与失效概率p的关系分析以及若干同阶图的比较,表明该参数能够更精确地度量网络抗毁性。     

图的顶点赋权邻域粘连度

将邻域抗毁性该参数推广到顶点赋权图中,提出图的顶点赋权邻域粘连度概念.通过构造组合星图,建立数学规划模型,研究了几类图的顶点赋权邻域粘连度的极值问题.     

图的赋权邻域坚韧度

将邻域坚韧度引入赋权图中,提出图的赋权邻域坚韧度概念。在给出一些基本图的赋权邻域坚韧度的基础上,着重研究几类图的赋权邻域坚韧度的极值问题。结果表明,参数值与图的结构、权值大小和赋权方式均有关系,因而能更为准确地刻画网络的抗毁性。     

图的几种N(p,q)标号问题

本文给出了图的两个关于点的邻域限制标号的定义:非完全邻域限制标号SN(p,q)与完全邻域限制标号TN(p,q)。SN(p,q)标号是仅对图的大度点的邻域做限制的正常标号;TN(p,q)标号是对图的所有点的邻域做限制的正常标号。图G的非完全邻域限制标号数与完全邻域限制标号数分别记为SL_p,q(G),TL_p,q(G)。本文主要给出了某些图G的SL_p,q(G),TL_p,q(G)的界。     

一些图的下完美邻域数上界

研究了图G的一类特殊控制数:下完美邻域数G.证明了在n阶连通图G中,若G不含圈或仅含点不交的圈,则Gn3.同时对n阶t叉树T分层,证明了其下完美邻域数上界Tt2+nt+1.     

无标度网络级联失效模型的负载重分配

受实时网络中节点失效传播效应的影响,为防止失效情况的传播,有效避免网络崩溃现象的发生,提出一种改进的介数模型,并基于可控系数α定义节点的初始负载,同时由度和介数理论推导得出网络抗毁性相对较好的点α=0.6。通过在无标度网络上建模,比较在α0.6以及α0.6的条件下节点遭受攻击后的仿真结果,得出在α0.6的情况下,初始负载小的节点受到攻击,相应网络的生存性较攻击初始负载大的节点低。在α0.6的情况下,结果正好相反。而对于α=0.6的仿真情况,此时无论攻击哪种节点,网络都表现出较好的生存性。由此可以得出结论:在现实网络的规划中,将节点初始负载控制在α=0.6附近,可以保证网络在面对节点失效时,最大限度增强网络生存性和提高网络的抗毁性。     

完全图的广义Mycielski图的邻点可区别的全色数

对图G的一个k-正常全染色法,若满足相邻点的点染色和关联边的色集合不同时,称该染色法为邻点可区别全染色,其所用小染色数k称为G的邻点可区别全色数.得到了完全图Km的广义Mycieski图Mn(Km)(n≥1,m≥3)的邻点可区别全色数.     

一类二部图生成的广义格子图的邻点可区别边染色

定义了一类2维广义格子图H2(G,n,m;k1,k2),且通过从图的结构出发,利用构造染色的方法,得到了图H2(Kp,p,n,m;p,p)的邻点可区别边色数.     

基于复杂网络理论的中国航路网络抗毁性分析

为有效评估航路点或航段失效对中国航路网络的影响,运用复杂网络理论建立的网络抗毁性测度方法,对中国航路网络模型的结构、运行特性及其抗毁性进行了实证分析.结合航路网络结构特性,以最大连通子图尺寸、聚集系数、整体效能下降率为测度指标,采用不同的攻击策略,对中国航路网络的抗毁性进行仿真分析:航路网络的抗毁性由少数航路点和航段维系的,无论节点攻击还是边攻击,网络总体表现出对随机攻击策略的鲁棒性及蓄意攻击的脆弱性,且边的抗毁性高于节点的抗毁性.其中,对网络模型连通性影响最大航路点是恩施、南充、天门等介数值较大的航路点;针对度及介数进行的蓄意攻击,攻击航路点数量达到6%时,就能使中国航空网络效率下降至50%左右;同时基于边介数策略攻击效果最好,表现出脆弱性.     

城市复杂地铁网络级联失效抗毁性分析

为全面分析了解地铁网络抗毁性问题,保障地铁网络安全平稳运行。采用复杂网络级联失效理论对城市地铁网络抗毁性进行研究。以北京地铁网络为例,构建北京地铁网络级联失效模型,通过MATLAB软件实现级联失效模型的仿真运算,对比分析不同节点攻击策略北京地铁网络抗毁性。仿真结果表明:随机攻击策略对地铁网络破坏性相对较小,而面临节点重要度和介数的两种蓄意攻击策略时,地铁网络抗毁性较弱。并进一步为地铁网络建设以及运营管理提供理论支持。     

关于图的叉数的一个注记

本文改进了完全二分图的叉数的已知下界,并证明了,在已知的完全图的叉数上界μ(K_p)≤1/4[p/2][(p-1)/2][(p-2)/2][(p-3)/2]中,如果对奇数p等号成立,邸么对下一个偶数p+1也有等号成立。     

邻域数的依概率ρ—级发散性

本文先提出了随机变量序列依概率ρ－级发散的概念，讨论了这种发散与通常的依概率发散的关系；在第二节，定义了d－维总体的邻域数，并给出了它作为一维离散型随机变量依概率ρ－级发散的条件，该条件不依赖于总体的分布，因此定理对一切总体均成立。     

图的邻域复形

一个图G的邻域复形是以G的顶点为顶点,以G的具有公共邻接顶点的顶点子集为单形的抽象复形.本文研究图的邻域复形的性质,复形的嵌入数以及邻域复形与图的关系等,并提出一些可供进一步研究的问题.     

基于改进人工鱼群算法的软硬件划分方法

将人工鱼群算法应用于软硬件划分,从而提出一种软硬件划分方法．针对人工鱼群算法在应用于离散型问题时普遍存在的最优解出现概率低、收敛速度慢等问题,采用随机步长来改善鱼的游走行为,使用邻域搜索来获得邻域内的更优状态,并根据无效迭代次数来提前终止迭代、提高算法效率．在对不同结点数的随机 DAG 图划分实验中,改进后算法的平均耗时约为原算法的6.5%～34.5%,而最优解出现概率则为原算法的5～7倍．因此,改进后算法在寻优能力和收敛速度上均优于原始算法,可更高效地完成软硬件划分任务．     

仙人掌图的邻域同调分类

仙人掌图是一个简单连通图，其每个块或者是一条边，或者是一个圈．如果两个国的邻城复形的各阶同调群分别同构，则称这两个图是邻城同调的．本文研究了仙人掌的邻域同调群的性质，给出了仙人掌图邻城同调分类的一个充要条件．     

几类特殊图的邻点可区别全染色

图的邻点可区别全染色,相对于图的正常全染色有更强的要求,因为它要求相邻顶点具有不同的颜色集合.本文刻画了两类特殊的完全多部图、广义圈和广义Mycielski图的邻点可区别全色数.     

基于混合离散人工蜂群算法的置换流水车间调度

针对以最小化最大完成时间为调度目标的置换流水车间调度问题,提出了混合离散人工蜂群算法.初始化种群采用NEH和随机方法.在算法的雇佣蜂阶段和侦查蜂阶段分别采用离散差分进化策略和变邻域搜索的变体产生邻域个体,为了兼顾算法的全局搜索和局部搜索能力,雇佣蜂阶段接受新个体采用模拟退火的概率突跳机制,而选择利用锦标赛方法,并对跟随的个体按一定概率进行局部搜索.此外,在侦查蜂阶段对锦标赛选择的个体执行破坏重建操作,用新产生的个体代替较差的个体.利用正交实验法调节算法参数,通过与其他算法的仿真实验结果比较,验证了算法的有效性.     

一类Pm×Cn图的邻点强可区别全染色

图的一个正常的全染色满足相邻点的点及其关联边染色的色集不同时,称为邻点强可区别全染色,其所用最少染色数称为邻点强可区别全色数。经证明得到了一类积图Pm×Cn的邻点强可区别色数。     

递增型二色图K22（3,7）及K27（3,8）的生成

n个顶点的完全图K_s,其边着色红或蓝,得K_n的二色图.当二色图既不包含蓝色团K_s,又不包含红色团K_y,则记作K_n(3,p).如果把K_n(3,p)成立的最大n值记为R(3,p),那未形如K_(n(3,p)(3,p)的一系列二色图与形为r(3,p)的一系列Ramsey数相关,已知R(3,p)=r(3,p)-1[1].本文讨论两个问题:(1)当p≤7时,给出二色图K_(R(3,p))(3,p)的递增性质,即K_(R(3,p))(3,p)可在K_(R(3,p-1))(3,p-1)上生成;(2)在二色图K_(22)(3,7)上生成K_(27)(3,8).从而知R(3,8)≥27,随知Ramsey数r(3,8)≥28.     

离散Bayes网诱导的概念类VC维数的下界

考虑一般Bayes网中每个随机变量取任意有限值时,其诱导的概念类VC(Vapnik-Chervonenkis)维数的下界.通过分析网络中可自由设定的参数个数与相应VC维数的关系,证明任意离散非完全Bayes网的可自由设定参数个数加1后,是相应VC维数的一个下界.