生成有向图中全部简单回路的一种有效算法

在研究有向图中全部简单回路现有算法的基础上,综合各算法的优点提出一种新的算法。算法的主要思想是对图中顶点进行深度优先搜索,在搜索过程中采取措施避免同一回路的重复出现,同时记录有用信息避免对顶点的重复访问,从而提高算法的效率,还给出了算法的证明和实例应用。算法结构清晰简单,方便转化为计算机程序。

生成有向图中全部简单回路的一种新算法

提出了生成有向图中全部简单回路的一种新算法.算法的主要思想是对图中顶点进行缩减,在缩减过程中巧妙地利用字符串标记保存图中原有信息,不断减少图中顶点的数量,最终将图缩为一点,逐步得到全部简单回路.这种缩减过程隐藏在矩阵运算中,在运算中不断简化矩阵,从而降低了运算复杂度,提高运算效率.此算法生成的回路中不包含重复的回路,算法结构清晰,易转化为计算机程序.文中给出了算法的详细证明和实例应用.

回路1、2-弦图的逆M矩阵完备及其算法设计

对已定元均不为零的部分逆M矩阵,通过变换使其对角线上元素均为1后,根据其所对应图形的特点,得到结果如下:(a)若其所对应图形为简单有向回路或回路1-弦图,具有逆M矩阵完备式当且仅当所有简单有向回路的回路积均小于1.(b)若其所对应图形为回路2-弦图,具有逆M矩阵完备式当所有简单有向回路满足回路积小于1,且对其中依次在两个顶点处相交的有向回路标明层次后,任一有向回路的回路积均小于与其相连接的上一层的有向回路的回路积.