且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

检测图中周期

更新时间:2022-01-11 22:22:54

从以上来看数学角度:

输入:图G =(V,E)

Input: Graph G=(V,E)

  1. 假设你的图形是不是不相交的(有每两个顶点之间存在路径)

  1. Assume that your graph is not disjoint (there exists a path between every two vertices)

计算生成树图形的T(也有容易的算法做这一点)

Compute the spanning tree T of the graph (there are easy algorithms to do that)

让E'是E的一个子集,不属于生成树T.对于在电子商务各边e',它除了树创建完全是一个单周期。让我们把所有这些周期为集合B。

Let E' be a subset of E, that don't belong to the spanning tree T. For each edge e in E', its addition to the tree creates exactly a single cycle. Let's put all those cycles into set B.

我们定义了一个双循环空间了在图形周期。在该空间中,两个周期可以增加。加入只是在边缘的独家总和。

We define a binary cycle space over cycles in your graph. In that space, two cycles can be added. The addition is simply an exclusive sum over the edges.

这组循环B是一个周期的基础。在图中每个周期可形成为周期的B的线性组合。

The set of cycles B is a "cycle basis". Every other cycle in your graph can be formed as a linear combination of the cycles B.

此方式,您获得您的图表中的所有可能的周期。

This way you obtain all possible cycles in your graph.

警告::如果您的输入图形具有的 v 的顶点和电子的边缘则有2 ^(电子的 - v 的+1)-1不同的周期!这是相当多的 - 你可能不想明确写入所有的人

Warning: if your input graph has v vertices and e edges then there are 2^(e - v +1)-1 different cycles! That's quite a lot - you might not want to explicitly write all of them.