将所有循环组合在一起的算法

Question

我有很多周期(例如,由数值表示,1-2-3-4对应于一个周期,有4个边,边1是{1:2},边2是{2:3},边3是{3,4},边4是{4,1},等等).

如果一个循环共享一个且只有一个边缘,则称该循环连接到另一个循环.

举例来说,假设我有两个周期1-2-3-4和5-6-7-8,那么有两种循环组,因为这两个周期未连接到对方.如果我有两个周期1-2-3-4和3-4-5-6,然后我只有一个周期组中,因为这两个循环共享相同的边缘.

下图应该可以说明我的观点:

的R1,R2到R7是我所谓的"周期".在上图中,只有一个包含所有R1to的循环组R7.

查找所有循环组的最有效方法是什么？

Answer 1

首先找到图中的所有循环并标记它们，例如 A、B、C 等。现在创建一个新图，其中在图中找到的每个循环都将转换为新图中的单个节点。如果相应的循环在旧图中“连接”，请使用您的（相当不寻常的）连接定义，将新图中的节点与边连接起来。

“循环组”的数量就是新图中连接组件的数量。