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

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

研究环形拓扑的网络化极大–加系统在添加捷径后周期长度和周期时间的特性.给出系统添加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.