串并有向图的判定算法及应用实例

串并有向图常作为单机排序问题研究中的约束条件，针对目前并未有一个确切算法判定任意一个有向图是否为串并有向图的问题，提出了串并有向图的判定算法H。算法H利用数学中的递归法，对有向图进行逐层递归分解，对分解结果进行分析判定该有向图是否为串并有向图。结果表明：该问题能在多项式内可解，属于组合优化中的P问题。算法H普遍适用于任意有向图，解决了串并有向图的判定问题。