等距图及其性质

连通性是图的一个重要概念.本文利用文献[2]中提出的表征图的连通性的新概念联系数,研究了一类特殊的图:k-等距图,即图的半径和直径均为k的图,得到的主要结果有:k-等距图是块;k-等距图最大度和团数的上界;k-等距图生成树的半径是k.     

电流变阀外置的汽车双筒液力减振器的理论及试验研究

介绍了电流变阀外置的新型汽车减振器的理论、结构及试验研究。阐述了电流变液体减振器阻尼力和电场的关系,其阻尼力由两部分组成:一部分是由粘性阻尼引起的牛顿力,无电场作用时,作为普通的减振器用;另一部分是由所加电场引起的切应力,它与所加电场强度成正比。试验结果表明:所设计的新型汽车电流变液体减振器具有阻尼力变化大、响应快、控制容易、结构简单和能源消耗低等特点,满足了汽车工程的实际需要,具有重要工程实用价值。     

An analysis of parameter adaptation in reactive tabu search

On‐line parameter adaptation schemes are widely used in metaheuristics. They are sometimes preferred to off‐line tuning techniques for two main reasons. First, they promise to achieve good performance even on new instance families that have not been considered during the design or the tuning phase of the algorithm. Second, it is assumed that an on‐line scheme could adapt the algorithm's behaviour to local characteristics of the search space. This paper challenges the second hypothesis by analysing the contribution of the parameter adaptation to the performance of a state‐of‐the‐art reactive tabu search () algorithm for the maximum clique problem. Our experimental analysis shows that this on‐line parameter adaptation scheme converges to good instance‐specific settings for the parameters, and that there is no evidence that it adapts to the local characteristics of the search space. The insights gained from the analysis are confirmed by further experiments with an algorithm for the quadratic assignment problem. Together, the results of the two algorithms shed some new light on the reasons behind the effectiveness of .     

基于极大团的边缘云节点聚合算法

组合多个边缘云可以向用户提供更强大的云计算服务,在大量边缘云节点集合中选择适当的节点进行组合是一项具有挑战性的任务。该问题被建模成由云节点作为顶点、节点之间的链路作为边的资源拓扑图。云组合的构建过程等同于在该图中选择子图的过程,这是一个NP完全问题。子图的选择策略是决定云组合性能的重要因素,现有的minStar算法贪心地选择节点之间通信延迟最小的子图,将最优资源分配给当前用户,导致了局部最优和全局性能不良的问题。鉴于此,提出基于极大团的边缘云资源分配算法,提取图中的极大团并将其划分为若干互不重叠的规模较小的完全子图,以子图为单位构建资源块,以资源块为单位进行资源的分配。实验结果表明,与minStar算法相比,新算法将全局最大通信延迟降至原来的50%。     

一种求解最大团问题的自适应过滤局部搜索算法

提出了一种求解最大团问题的自适应过滤局部搜索算法AF-RLS(adaptive filtered-reactive local search).该算法通过构建独立集约束,优选出有希望的邻域移动方向来提高局部搜索趋向最优解的概率;并在比较分析两种不同逃逸策略的逃逸能力和逃逸代价的基础上,提出了基于问题解空间结构自适应设置...     

基于三角环的顶点着色问题解法

图的着色问题是一个NP难问题,本文着重探讨无向图的顶点的三色问题,提出了用构造三角环的极大独立集方法判断并尝试给出顶点三色问题的可行解,解决了顶点三色的可满足性问题,克服了以前图遍历过程中的回溯问题,以及由此推论顶点四色和五色问题的极大独立集。     

一种基于邻居信息的最大派系过滤算法

最大派系问题(Maximal Clique Problem, MCP)是组合优化中经典而重要的问题之一,在信息抽取、信号传输、计算机视觉、社会网络及生物信息学等众多领域有着重要的应用。学者们根据不同的思想策略,提出了许多方法求解最大派系问题,如分支定界、遗传算法、模拟退火、交又嫡及DNA方法等。现根据派系的部居信息提出一种基于派系邻接顶点和邻接边的派系过滤算法。算法从一个已知派系(初始为一个单独顶点)出发,每次考察派系的部接顶点,并以派系的邻接边为基础,扩展已有派系而得到更大的派系。用两个大规模的科学家合作网络对提出的算法进行了分析,并讨论了大规模社会网络中的派系分布情况。实验表明,提出的算法可有效地抽取网络中的最大派系。     

两元指纹向量聚类问题的复杂性与改进启发式算法

证明丢失值位数不超过2的指纹向量聚类问题为NP-Hard,并给出Figueroa等人指纹向量聚类启发式算法的改进算法.主要改进了算法的实现方法.以链表存储相容顶点集合,并以逐位扫描指纹向量的方法产生相容点集链表,可将产生相容点集的时间复杂性由O(m·n·2p)减小为O(m·(n·p 1)·2p),可使划分一个唯一极大团或最大团的时间复杂性由O(m·p·2p)减小为O(m·2p).实际测试显示,改进算法的空间复杂性平均减少为原算法的49%以下,平均可用原算法20%的时间求解与原算法相同的实例.当丢失值位数超过6时,改进算法几乎总可用不超过原算法11%的时间计算与原算法相同的实例.     

团数为5的零因子图对应的有限交换局部环

零因子图主要是利用图论的语言和工具来研究并解决代数中的一些难题。对于任意的有限交换局部环, 其代数结构一直是研究难点。通过对零因子图团数的分类, 讨论了当团数为5时, 对应的有限交换局部环R的代数性质, 刻画了环R的极大理想的幂零指数。特别是, 当极大理想的幂零指数为5时, 对极大理想的代数结构及极小生成元集进行了具体刻画。     

Correlation in mobile call networks from structure perspective

Researchers have done considerable work on the structure of social network recently, but mostly neglected the correlation between two connected nodes. In this paper, our primary goal is to acquire users’ structural properties in mobile call networks. We take a novel perspective-structure correlation between two connected users perspective to study the structural properties. To investigate the structural properties in static and dynamic mobile call networks, we define some metrics which are based on the clique size vectors of mobile call users. By exploring several real-world mobile call networks, which contain hundreds of thousands of mobile call users respectively, we find that people tend to communicate with the one who has a similar structure in static mobile call networks. Moreover, It is found that the connected people have similar structural changes on the whole in dynamicmobile call networks, and the structures of some two connected persons both have growing or shrinking trends. We use a visualization toolkit to give a view of the growing or shrinking scenarios temporally.