识别无向图中所有周期基的算法

Question

我有一个带有Vertex V和Edge 的无向图E.我正在寻找一种算法来识别该图中的所有循环基础.

我认为Tarjans算法是一个好的开始.但我的参考是关于找到所有周期,而不是周期基(根据定义,它是不能通过其他周期的并集构建的周期).

例如,看看下面的图表:

因此,算法会有所帮助.如果有一个现有的实现(最好是在C#中),那就更好了!

Answer 1

据我所知,不仅是Brian的预感点,而是一个更强大的命题:不在最小生成树中的每个边缘都会添加一个新的"基本周期".

为了看到这一点,让我们看看当你添加一个不在MST中的边E时会发生什么.让我们做最喜欢的数学方法来复杂化并添加一些符号;)调用原始图G,添加E G'之前的图形,以及添加E G'之后的图形.所以我们需要弄清楚"基本周期计数"如何从G'变为G'.

添加E必须至少关闭一个周期(否则E将首先在G的MST中).所以显然它必须在G'中已经存在的至少一个"基本周期".但是它增加了多个吗？

它不能添加两个以上,因为没有边可以是两个以上基本周期的成员.但是如果E是两个基本周期的成员,那么这两个基本周期的"联合"必须是G'中的基本周期,所以我们再次得到周期数的变化仍为1.

因此,对于不在MST中的每个边缘,您将获得新的基本周期.所以"计数"部分很简单.找到每个基本周期的所有边缘有点棘手,但按照上面的推理,我认为这可以做到(在伪Python中):

for v in vertices[G]:
    cycles[v] = []

for e in (edges[G] \ mst[G]):
    cycle_to_split = intersect(cycles[e.node1], cycles[e.node2])
    if cycle_to_split == None:
        # we're adding a completely new cycle
        path = find_path(e.node1, e.node2, mst[G])
        for vertex on path:
            cycles[vertex].append(path + [e]) 
        cycles
    else:
        # we're splitting an existing base cycle
        cycle1, cycle2 = split(cycle_to_split, e)
        for vertex on cycle_to_split:
            cycles[vertex].remove(cycle_to_split)
            if vertex on cycle1:
                cycles[vertex].append(cycle1)
            if vertex on cycle2:
                cycles[vertex].append(cycle2)

base_cycles = set(cycles)

编辑:代码应该在图中找到所有基本周期(base_cycles设置在底部).假设你知道如何:

• 找到图的最小生成树(mst [G])
• 找到两个列表之间的区别(edge\mst [G])
• 找到两个列表的交集
• 找到MST上两个顶点之间的路径
• 通过向其添加额外边缘将一个循环分成两个(分割函数)

它主要遵循上面的讨论.对于不在MST中的每个边缘,您有两种情况:要么带来一个全新的基本周期,要么将现有的一个分割为两个.为了跟踪两者中的哪一个,我们跟踪顶点所属的所有基本周期(使用循环字典).