关于强边着色猜想的最优图问题

著名图论专家Erd(o)s和Ne(s)et(r)il对图的强边着色数上界提出了一个猜想:当△为偶数时,x's(G)≤5/4△2;当△为奇数时,x's(G)≤1/4(5△2-2△+1),他们给出了当△=4的时的最优图.此处构造了一族图,并以此证明了当△为偶数时,如果Erd(o)s和Ne(s)et(r)il提出的强边着色猜想成立,则猜想中的上界是最优的.     

New mixed broadcast scheduling approach using neural networks and graph coloring in wireless sensor network

Due to the mutual interference and sharing of wireless links in TDMA wireless sensor networks, conflicts will occur when data messages are transmitting between nodes. The broadcast scheduling problem (BSP) is aimed to schedule each node in different slot of fixed length frame at least once, and the objective of BSP is to seek for the optimal feasible solution, which has the shortest length of frame slots, as well as the maximum node transmission. A two-stage mixed algorithm based on a fuzzy Hopfield neural network is proposed to solve this BSP in wireless sensor network. In the first stage, a modified sequential vertex coloring algorithm is adopted to obtain a minimal TDMA frame length. In the second stage, the fuzzy Hopfield network is utilized to maximize the channel utilization ratio. Experimental results, obtained from the running on three benchmark graphs, show that the algorithm can achieve better performance with shorter frame length and higher channel utilizing ratio than other exiting BSP solutions.     

图的2-距离着色

简单图G(V,E)的2-距离着色是正常的顶点着色且距离不大于2的任意两个顶点着不同的颜色,给出了网格的2-距离色散,并通过运用线图构造了一类特殊图,从而证明了最大度为△的图G的二距离色数的界为16/5△2+8/3△+16/5≤x2d(G)≤min{△2+1,n}     

对启发式算法实现图着色的优化

针对传统教科书中的图着色算法进行了分析研究,通过对算法执行步骤的跟踪分析,提出了两点改进方法,从而省去了大量的重复计算,大大提高了算法的效率.     

恰含有一个偶圈的单圈图的着色游戏

令f是一个把任意图H映射到非负整数且满足f(H)≤V(H)的图函数.定义图函数f为f(K2)=2,f(P8)=3,f(C2n)=3,其余未定义的子图满足f(H)=0.证明了恰含有一个偶圈的单圈图的f-无圈游戏色数不超过9.     

灰度图像平滑处理及着色方法

加权有向平滑滤波算法既能有效地滤除灰度图像中的噪声,又能很好保护图像的边缘和细节,弥补了常用空域平滑滤波算法不能兼顾去噪和保持图像细节的不足。采用四叉树技术对灰度图像进行分块;在每个子块中随机选取若干像素点,分别查找与其最匹配的样本点并传递颜色信息;接着,把这些像素点作为参考样本点,完成子块中其他像素点的着色。     

基于CPN的可信路由器发现协议建模与仿真分析

为了保证终端设备能够可信高效地通过接入路由器访问互联网,提出一种可信路由器发现协议,实现安全、高效的接入路由器身份认证过程,并基于着色Petri网(Colored Petri Nets,CPNs)为该协议建立关联的功能验证模型和性能分析模型,有效集成协议的安全性验证与性能分析过程,以确认该协议在保证安全能力的基础上可以有效提升接入路由器身份认证过程的性能。基于着色Petri网的安全性验证与性能评价集成分析方法为安全类协议的性能改进分析提供了一种更加便捷、有效的协议仿真分析方法。     

用影响网分析复杂系统关键事件

为分析复杂系统关键事件,将系统事件序列图转换为影响网图,通过着色Petri网进行建模和仿真,采用影响网分析系统事件的敏感性并搜索关键事件集合. 统计着色Petri网模型的仿真输出结果,得出事件发生的条件概率和基准概率,将影响强度与条件概率值的关系线性化,从而推算出影响强度. 该方法避免了影响强度、基准概率等参数由专家指定存在的主观性. 以弹道导弹防御系统为例进行分析,结果表明所述方法直观实用,对复杂系统的决策有一定的参考价值.     

中国展览馆问题与平图的4着色

提出了中国展览馆问题,目的就在于解决：①任意图的4着色问题;②任意图的生成树的构造与计数问题。阐明了解决对偶图4着色问题和任意C（p,q）的生成树的构造与计数问题的基本思路．提出了基于森林E分解的对偶图的顶点4着色方法和基于2颗被分解的对偶树T^A和T^B进行任意图的生成树构造的方法．介绍了森林Fi的3种分解方法．     

极化曲线法比较彩色不锈钢在硫酸介质中的耐蚀性

通过化学着色法对304HC,316,316L不锈钢进行了着金黄色及其热水固膜后处理,运用动态极化曲线扫描法测定了其点蚀击穿电位,结果表明,3种不锈钢着色后的点蚀击穿电位提高80-100mV,耐蚀性能明显提高;热水固膜处理后的彩色不锈钢。304HC不锈钢的点蚀击穿电位又提高了80mV,耐腐蚀进一步增强。