摘要
饱和图是极大-加矩阵前趋图的一个子图,关键回路是前趋图中平均权重最大的回路.运用饱和图来寻找前趋图中的全部关键回路,证明前趋图中的一个回路是关键回路当且仅当它是饱和图中的一个回路,并给出极大-加矩阵关键图的一个绘制方法.引入极大-加矩阵的关键矩阵概念,以分析和优化系统周期性能,指出关键矩阵与原矩阵具有相同的特征值,并且关键矩阵的特征向量集包含了原矩阵的特征向量集.同时,给出关键图和关键矩阵在缩短交通系统运行周期中的一个应用.
The saturation graph is a subgraph of the precedence graph of a max-plus matrix, and a circuit of the precedence graph is called critical if it has the maximum average weight. This paper finds out all critical circuits in a precedence graph by using the saturation graph. It is proven that a circuit in the precedence graph is critical if and only if it is a circuit in the saturation graph. Based on this, a method for plotting the critical graph of a max-plus matrix is provided. This paper introduces the critical matrix of a max-plus matrix to analyze and to optimize the periodicity of a system. It is pointed out that the critical matrix has the same eigenvalues with the original matrix, and the set of eigenvectors of the critical matrix contains that of the original matrix. At the same time, this paper presents an application of the critical graph in the cycle time reduction for traffic systems.
作者
王彩璐
陶跃钢
WANG Cailu;TAO Yuegang(School of Control Science and Engineering, Hebei University of Technology, Tianjin 300130)
出处
《系统科学与数学》
CSCD
北大核心
2018年第3期272-284,共13页
Journal of Systems Science and Mathematical Sciences
基金
国家自然科学基金(60774007,61741307)资助课题
关键词
极大-加矩阵
关键图
饱和图
关键矩阵
周期优化
交通系统
Max-plus matrix, critical graph, saturation graph, critical matrix, period optimization, traffic system.
