饱和图是极大-加矩阵前趋图的一个子图, 关键回路是前趋图中平均 权重最大的回路. 运用饱和图来寻找前趋图中的全部关键回路, 证明前趋图中的一个回路是关键回路当且仅当它是饱和图中的一个回路, 并给出极大-加矩阵关键图 的一个绘制方法. 引入极大-加矩阵的关键矩阵概念, 以分析和优化系统周期性能, 指出关键矩阵与原矩阵具有相同的特征值, 并且关键矩阵的特征向量集包含了原矩阵的特 征向量集. 同时, 给出关键图和关键矩阵在缩短交通系统运行周期中的一个应用.

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.