环形拓扑的网络化极大–加系统的捷径与周期性能  

Shortcuts and periodicity of networked max-plus system with ring topology

作　　者：郭孟然 陶跃钢[2] 蔡炳苓[1] 张子龙[1,3] 

机构地区：[1]河北师范大学数学与信息科学学院,石家庄050024 [2]河北工业大学控制科学与工程学院,天津300130 [3]河北省计算数学与应用重点实验室,石家庄050024

出　　处：《中国科学：信息科学》2016年第2期228-243,共16页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:60774007;61305101;11271108);河北师范大学青年基金(批准号:L2012Q01)资助项目

摘　　要：研究环形拓扑的网络化极大–加系统在添加捷径后周期长度和周期时间的特性.给出系统添加k条起始点相同的捷径后周期长度为1的概率的一个下界表达式和周期时间不变的一个充分必要条件,发现两个维数分别为素数与其方幂的系统添加捷径后周期长度为1的概率的下界是一致的.讨论系统添加起始点不相同的捷径的若干特殊情形,给出系统添加k条互不相交的捷径后周期长度为1的概率的一个下界表达式.所用的代数与组合方法具有构造性.由此给出检验系统添加k条起始点相同的捷径后周期时间保持不变的算法,并证明这一算法是多项式算法.同时还给出一个关于周期长度的数值例子.This paper investigates the characteristics of cyclicity and cycle time after adding shortcuts to the networked max-plus system with ring topology. Both the lower bound expression of the probability of cyclicity being one and the sufficient and necessary condition for the cycle time being unchanged are established after adding k shortcuts with the same starting point. For two systems with the dimensions of a prime number and its power, it is discovered that the lower bounds of the probability of cyclicity being one is consistent after adding the shortcuts. The paper also investigates some situations of adding shortcuts under conditions with different starting points. The lower bound expression of the probability of cyclicity being one is given after adding k shortcuts with mutual disjoint. The method for algebra and combinatorics is constructive. The algorithm of the cycle time remaining unchanged is given after adding k shortcuts with the same starting point. It is proven that such algorithm has a polynomial bound. At the same time, the numerical example for cyclicity is also given.

关 键 词：极大–加系统 环形拓扑 网络化系统 捷径 周期时间 周期长度 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]