识别无向图中所有循环基的算法 [英] Algorithms to Identify All the Cycle Bases in a UnDirected Graph

问题描述

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

我认为 Tarjans算法是一个好的开始。但是我的参考资料是关于找到所有 周期 ，而不是 循环库 （其中，根据定义是不能由其他周期的联合构建的周期。）

例如，看看下面的图：

所以，一个算法会有帮助。如果有一个现有的实现（最好在C＃中），它甚至更好！

解决方案

据我所知，布赖恩的预感不错，但更强硬的观点认为：每个不在最小生成树中的边缘恰恰增加了一个新的基本周期。

为了看到这一点，我们来看看当添加一个不在MST中的边E时会发生什么。让我们做最喜欢的数学方法来使事情复杂化并添加一些符号;）在添加E G'之前调用原始图G，添加E G之后调用图。所以我们需要找出基本周期盘点数是如何从G'变为G'的。

添加E必须至少关闭一个周期（否则E会首先在G的MST中）。所以很明显，它必须在G'中已有的至少增加一个基本周期。但它是否添加了多个？

它不能加两个以上，因为没有边可以是多于两个基周期的成员。但是如果E是两个基本周期的成员，那么这两个基本周期的联合一定是G'中的一个基本周期，所以我们再次得到周期数的变化仍然是1。 p>

，对于每个不在MST中的边缘，都会得到一个新的基准周期。所以计数部分很简单。寻找每个基周期的所有边是有点棘手的，但根据上面的推理，我认为这可以做到这一点（在伪Python中）：

对于顶点[G]：
 cycles [v] = [] 
 
（边[G] \ mst [G]）中的v： b $ b cycle_to_split =相交（cycles [e.node1]，cycles [e.node2]）
如果cycle_to_split == None：
＃我们正在添加一个全新的循环
 path = find_path（e.node1，e.node2，mst [G]）
用于路径顶点：$ b​​ $ b cycles [vertex] .append（path + [e]）
 cycles 
 else：
＃我们正在分割现有的基本循环
 cycle1，cycle2 = split（cycle_to_split，e）
用于cycle_to_split上的顶点：$ b​​ $ b cycles [vertex] .remove（cycle_to_split ）
如果在cycle1上的顶点：$ b​​ $ b cycles [vertex] .append（cycle1）
如果在cycle2上的顶点：$ b​​ $ b cycles [vertex] .append（cycle2）
 
基数_cycles = set（cycles）
  

编辑：代码应该找到所有图中的基本循环（base_cycles设置在底部）。假设你知道如何：
$ b $ ul

找到图的最小生成树（mst [G]）

查找两个列表之间的差异（边缘\ mst [G]）

查找两个列表的交集

查找MST上的两个顶点之间的路径通过向其添加额外的边（分割函数）将一个周期分成两部分（
$ b

）。
$ b

它主要遵循上面的讨论。对于不在MST中的每条边，有两种情况：要么带来一个全新的基本周期，要么将现有的一个分成两部分。为了追踪这两种情况中的哪一种，我们跟踪一个顶点所属的所有基本周期（使用周期字典）。

I have an undirected graph with Vertex V and Edge E. I am looking for an algorithm to identify all the cycle bases in that graph.

I think Tarjans algorithm is a good start. But the reference I have is about finding all of the cycles, not cycle base ( which, by definition is the cycle that cannot be constructed by union of other cycles).

For example, take a look at the below graph:

So, an algorithm would be helpful. If there is an existing implementation (preferably in C#), it's even better!

解决方案

From what I can tell, not only is Brian's hunch spot on, but an even stronger proposition holds: each edge that's not in the minimum spanning tree adds exactly one new "base cycle".

To see this, let's see what happens when you add an edge E that's not in the MST. Let's do the favorite math way to complicate things and add some notation ;) Call the original graph G, the graph before adding E G', and the graph after adding E G''. So we need to find out how does the "base cycle count" change from G' to G''.

Adding E must close at least one cycle (otherwise E would be in the MST of G in the first place). So obviously it must add at least one "base cycle" to the already existing ones in G'. But does it add more than one?

It can't add more than two, since no edge can be a member of more than two base cycles. But if E is a member of two base cycles, then the "union" of these two base cycles must've been a base cycle in G', so again we get that the change in the number of cycles is still one.

Ergo, for each edge not in MST you get a new base cycle. So the "count" part is simple. Finding all the edges for each base cycle is a little trickier, but following the reasoning above, I think this could do it (in pseudo-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)

Edit: the code should find all the base cycles in a graph (the base_cycles set at the bottom). The assumptions are that you know how to:

• find the minimum spanning tree of a graph (mst[G])
• find the difference between two lists (edges \ mst[G])
• find an intersection of two lists
• find the path between two vertices on a MST
• split a cycle into two by adding an extra edge to it (the split function)

And it mainly follows the discussion above. For each edge not in the MST, you have two cases: either it brings a completely new base cycle, or it splits an existing one in two. To track which of the two is the case, we track all the base cycles that a vertex is a part of (using the cycles dictionary).

这篇关于识别无向图中所有循环基的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！