加法幂等半环和坡代数在网络路径优化问题中的应用

Application of Additively Idempotent Semiring and Incline Algebra in the Optimization Problems of Network Paths

对加法幂等半环上矩阵幂收敛的条件,以及加法幂等半环和坡代数赋权图路径优化问题与伴随矩阵幂的关系进行了研究,优化问题是在加法诱导的偏序≤下考虑的.特别,证明了对于选择的加法幂等半环E上的n阶赋权图G,如果其伴随矩阵A满足aij=e,且对G的任一基本回路p,权w(p)≤e,e是E的乘法幺元,则An-1的(i,j)分量表示从顶点i到j的所有路径的权在偏序≤下的最大元,且最大元一定在某一基本路径上取得.坡代数赋权图的结果作为特例得到.最后给出了几个应用的实例.说明加法幂等半环赋权图的这类广义路径优化问题仍可用矩阵幂的方法来解.

The convergent conditions for the powers of a matrix over an additively idempotent semiring and the relationship between the path optimization problem and the adjoint matrix powers for a weighted graph over an additively idempotent semiring and an incline algebra are investigated. The optimization problem is considered under the partial order ≤ induced by addition. In particular, it is proved that for an n-th order weighted graph G over a selective and additively idempotent semiring E, if its adjoint matrix A satisfies au =e and the weight w（p）≤e for any elementary circuit p of G, where e is the multiplicative identity, then the （i,j） entry of A（n-i） denotes the greatest element of weights of all the paths from vertex i to j under the partial order 4,and the greatest element is achieved on some elementary path. The results for a weighted graph over incline algebra are obtained as special cases. Finally, some application examples are given. It is indicated that the generalized path optimization problem for a weighted graph over an additively idempotent semiring can still be solved by using the methods of matrix powers.