基于闭半环的若干图算法

摘要 闭半环是在半环上添加了传递闭包运算符而得到的代数结构．闭半环为计算机科学理论中多个看起来不相关的问题提供了统一的求解理论框架．有不少图算法问题可以通过对图的邻接矩阵在特定的闭半环上计算闭包而求解．本文分析了三个典型的问题：最可靠路径、最小生成树和到达定值数据流分析．其中到达定值数据流分析可采用两种闭半环求解．本文为这些问题提供了基于Haskell语言的算法实现，并为最小生成树问题证明了算法的正确性．