含有一个6-圈的共轭圈问题

Yeo于1999年提出猜想:每一个至少有8个点的c-部(c≥4)正则竞赛图D包含一对不相交的长分别为t和｜V(D)｜-t的共轭圈,其中t∈｛3,4,…,｜V(D)｜-t｝。文章证明当c≥9时猜想对于t=6是成立的。     

2r-正则图连通圈网络的Hamilton分解

互连网络是超级计算机的重要组成部分。互连网络通常模型化为一个图,图的顶点代表处理机,图的边代表通信链路。2010年师海忠提出互连网络的正则图连通圈网络模型,设计出了多种互连网络,也提出了一系列猜想。文中证明了2r -正则图连通圈网络可分解为边不交的一个Hamilton圈和一个完美对集的并,从而证明了当原图为2r-正则连通图时,这一系列猜想成立。     

强竞赛图的强连通性

D=(V,A)为一个有向图,其中,V为顶点集,A为弧集,A中的元素是有序对(u,v),称为弧。设u和v是有向图D的两个顶点,若从u到v存在一条有向路,则称顶点v是从u可达的,或称从u可达v。若有向图D中任何两个顶点是互相可达的,则称D为强连通图。若有向图T中任意两个顶点之间恰有一条弧,则称T为竞赛图。一个强连通的竞赛图T称为强竞赛图。论文研究顶点个数大于的强竞赛图T的性质,并利用该性质给出了Moon定理的另外一种证明。     

关于冒泡排序连通圈网络猜想的一个注记

冒泡排序连通圈网络BSCC(n)是一类重要的互连网络,它是3正则的.2010年师海忠提出了如下猜想:冒泡排序连通圈BSCC(n)(n≥4)可分解为边不交的一个Hamilton圈和一个完美对集的并.在本文中证明了当nn==5,4时猜想成立,另外,给出了BSCC(6)的一个圈分解.     

无向哈密顿图的一个充分必要条件及计算公式

哈密顿图的判定问题是一个NP完全问题,是图论理论中尚未解决的主要问题之一。1968年,Grinberg证明了一个必要条件,提高了判定非哈密顿可平面图的效率,由此产生了很多3-正则3-连通非哈密顿可平面图的研究成果。根据无向哈密顿图的特征,提出了基本圈的分解、合并、单条公共边连通,原子圈等概念。任何一个简单连通无向图G是哈密顿图,当且仅当,哈密顿圈要么其本身就是一个包含所有顶点的原子圈;要么总是可以分解成若干个原子圈,这些原子圈按照某种次序以单条公共边连通。根据这个充分必要条件,推导出了一个必要条件计算公式。它不仅能处理平面图,也能处理非平面图;甚至能处理某些Grinberg条件不能处理的平面图。此外,对一些实际案例的测试结果验证了充分必要条件和计算公式的有效性。     

循环赛排名问题的程序实现

讨论了使用竞赛图及特征向量法计算循环比赛的排名问题，它适用于当n4且G是双向连通有向图时，经过推广给出了一般的排名问题的算法。并给出了部分源程序。该程序在Turbo C环境调试通过。该程序在各项赛事中有着很强的实用价值。     

有序势博弈及其在智能体无线网络中的应用

有序势博弈具有广泛的应用,势有向图中不含单向圈是判定有序势博弈的一个充分必要条件.利用矩阵半张量积和置换矩阵,通过博弈的支付矩阵求取势有向图的邻接矩阵.通过收缩势有向图中的双向圈,将单向圈的存在性问题转化为判断收缩后的图中圈的存在性问题.此外,分析有序势函数的一些基本性质,并给出有序势函数的具体计算方法.最后结合线性规划讨论了有序势博弈在延长智能体无线网络系统寿命的应用.     

程序静态分析的通用方法

本文旨在为程序静态分析提供一个通用方法,为此,作者提出了有向图的投影图概念和算法,定义了正则与非正则控制流、数据流,论述了怎样利用“投影”来分析程序。最后,扼要介绍了基于投影方法实现的一个静态工具:FATAS。 本文所提的方法统一、灵活、简单,对解决其他用有向图描述的问题也有裨益。     

多部图的匹配算法研究

本文给出了一个多部图的商匹配问题的定义,提出了求解多部图商匹配问题的一个算法。该算法使用圈与割集中偶图的交相结合的方法,利用求二部图的最大匹配算法,求解多部图的最大商匹配问题。     

你能通过吗?——1999年全国计算机等级考试三级(B)笔试试题摘录

(1)以下数据结构中哪一个是线性结构? A)有向图 B)栈 C)线索二叉树 D)B树 正确答案为B (2)下面关于图的存储的叙述中正确的是 A)用相邻矩阵法存储图,占用的存储空间大小只与图中结点个数有关,而与边数无关     

每条弧都在Hamilton-路上的半完全多部有向图

用一条弧或一对方向相反的弧代替完全多部无向图的每一条边所得到的有向图被称为是半完全多部有向图。2002年L. Volkmann [6]提出这样一个问题：给出半完全多部有向图中每一条弧都在Hamilton-路上的充分条件。本文将针对此问题给出一个新的充分条件,并举例说明该充分条件的独立性以及它在某种意义下的最佳可能性。     

Observing the state with componentwise exponentially decaying error

The componentwise exponential asymptotically stable (CWEAS) observer is defined. Its estimation error is componentwise and absolutely bounded by prespecified decaying exponentials. Using the notion of CWEAS introduced earlier, an existence condition for such an observer is proved. Via eigenvalues location and convexity of certain functions one states the maximization problem of the damping factor of the above exponentials and introduces and characterizes the CWEAS detectability. This is an explicit property of the observability pair (A, C), which, under a certain condition involving the pair (B, D), suffices for strong^* detectability and therefore for the existence of a strong observer.     

m序列频谱免疫度的研究

频谱免疫度是度量周期序列抵抗离散傅里叶频谱攻击的重要指标。周期序列的频谱免疫度越大,抵抗离散傅里叶频谱攻击的能力越强。通过搜索[m]序列的零化子,计算其频谱重量,提出猜想：[n]级[m]序列的零化子最低频谱重量是[n+1],而该[m]序列的补序列恰恰是其一个最低频重零化子。研究了[m]序列零化子及其补序列的性质,从理论上证明了该猜想。分析了[m]序列补序列的零化子性质,得出结论：[n]级[m]序列的频谱免疫度为[n];说明了[m]序列难以抵抗离散傅里叶频谱攻击。     

AN ENHANCED ANT COLONY OPTIMIZATION METAHEURISTIC FOR THE MINIMUM DOMINATING SET PROBLEM

This paper proposes an enhanced Ant Colony Optimization (ACO) metaheuristic called ACO-TS to attack the minimum dominating set (MDS) problem. One of the recognized difficulties faced by ACO in its original form is premature convergence, which produces less satisfactory solutions. We propose a way to encourage a higher degree of exploration of the search space by incorporating a technique based on a concept borrowed from genetic algorithms called tournament selection. Instead of always following the standard mechanism for selecting the next solution component, an ant would make its decision based on the outcome of a tournament between randomly selected allowable components. The frequency of the tournament selection is controlled by a probability measure. The use of tournament selection is coupled with an iteration-best pheromone update. To evaluate the enhanced ACO, we consider the MDS problem formulated from ad hoc network clustering. A comparison with its original form shows that the enhanced ACO produces better solutions using fewer number of cycles. We also empirically demonstrate that the proposed ACO produces better solutions than a genetic algorithm. Finally, we argue, based on empirical results, why the tournament selection approach is preferable to a pure random selection method.     

Global and componentwise extrapolations for accelerating training of Bayesian networks and conditional random fields

The triple jump extrapolation method is an effective approximation of Aitken’s acceleration that can accelerate the convergence of many algorithms for data mining, including EM and generalized iterative scaling (GIS). It has two options—global and componentwise extrapolation. Empirical studies showed that neither can dominate the other and it is not known which one is better under what condition. In this paper, we investigate this problem and conclude that, when the Jacobian is (block) diagonal, componentwise extrapolation will be more effective. We derive two hints to determine the block diagonality. The first hint is that when we have a highly sparse data set, the Jacobian of the EM mapping for training a Bayesian network will be block diagonal. The second is that the block diagonality of the Jacobian of the GIS mapping for training CRF is negatively correlated with the strength of feature dependencies. We empirically verify these hints with controlled and real-world data sets and show that our hints can accurately predict which method will be superior. We also show that both global and componentwise extrapolation can provide substantial acceleration. In particular, when applied to train large-scale CRF models, the GIS variant accelerated by componentwise extrapolation not only outperforms its global extrapolation counterpart, as our hint predicts, but can also compete with limited-memory BFGS (L-BFGS), the de facto standard for CRF training, in terms of both computational efficiency and F-scores. Though none of the above methods are as fast as stochastic gradient descent (SGD), careful tuning is required for SGD and the results given in this paper provide a useful foundation for automatic tuning.     

Scheduling Sport Tournaments using Constraint Logic Programming

We tackle the problem of scheduling the matches of a round robin tournament for a sport league. We formally define the problem, state its computational complexity, and present a solution algorithm using a two-step approach. The first step is the creation of a tournament pattern and is based on known graph-theoretic results. The second one is an assignment problem and it is solved using a constraint-based depth-first branch and bound procedure that assigns actual teams to numbers in the pattern. The procedure is implemented using the finite domain library of the constraint logic programming language \eclipse. Experimental results show that, in practical cases, the optimal solution of the assignment problem (which is not necessarily optimal for the overall problem) can be found in reasonable time, despite the fact that the problem is NP-complete. In addition, a local search procedure has been developed in order to provide, when necessary, an approximate solution in shorter time.     

Color image encryption based on DNA encoding and pair coupled chaotic maps

Information security has become a significant issue in encryption due to the rapid progress of internet and network. Therefore, the development of the encryption algorithm is a growing and significant problem. In this study, a new color image encryption was introduced based on DNA complementary rules and pair coupled chaotic maps. At first, the plain color image was divided into three components (R, G, B) being converted into three DNA matrices using DNA encoding rules. Secondly, DNA addition for R, G and B components was implemented and scrambled the elements position of three DNA sequence via the pair coupled chaotic maps. Three gray coded images obtained and RGB encrypted image was achieved by restructuring R, G, B components. The simulation of experimental result and security analysis showed that this algorithm had larger secret key space and strong secret key sensitivity and it had excellent ability to resist against statistical and differential attacks.