生成有向图的所有树形图的新算法

本算法生成一个直积-直和表达式,用来表示有向图G中所有以指定结点r为根的树形图之集∑_r~ (G)。该表达式正是一种“符号网络函数”,且其形式非常适合生成树形图问题的实际应用。算法的基础是两种新的分解:图的直积分解与图的直和分解。本文还提出逆弧概念和删除逆弧算法,作为下一步改进的着眼点。复杂性:时间O(VEK),空间O(E),其中K为直和分解次数加1。