2

我试图找到一种快速算法来获得所有连接的子图，形成一个子图长度受限的无向图。简单的方法，例如每个顶点的 BFS 或 DFS 会生成大量相等的子图，因此在每次算法迭代中，我们都必须修剪子图集。我在俄罗斯数学论坛上发现了一个算法：

Procedure F(X,Y)
//X set of included vertices 
//Y set of forbidden vertices to construct new subgraph
1.if |X|=k, then return;
2.construct a set T[X] of vertices that adjacent to vertices from X (If X is a empty set, than T[X]=V), but not belong to the sets X,Y;
3.Y1=Y;
4.Foreach v from T[X] do:
__4.1.X1=X+v;
__4.2.show subgraph X1;
__4.3.F(X1,Y1);
__4.4.Y1=Y1+v;

Initial call F(X,Y):
X, Y = empty set;
F(X,Y);

该算法的主要思想是使用“禁止集”，因此不需要剪枝，该算法的作者说它比基于剪枝等于子图的解决方案快 300 倍。但是我还没有找到任何证据证明这个算法是正确的。

更新：在这里找到了更有效的解决方案

4

2 回答 2

2

这是我认为是您的原始算法的 Python 实现：

from collections import defaultdict

D=defaultdict(list)
def addedge(a,b):
    D[a].append(b)
    D[b].append(a)

addedge(1,2)
addedge(2,3)
addedge(3,4)

V=D.keys()
k=2

def F(X,Y):
    if len(X)==k:
        return
    if X:
        T = set(a for x in X for a in D[x] if a not in Y and a not in X)
    else:
        T = V
    Y1=set(Y)
    for v in T:
        X.add(v)
        print X
        F(X,Y1)
        X.remove(v)
        Y1.add(v)

print 'original method'
F(set(),set())

F 生成大小 <=k 的所有连接子图，其中子图必须包含 X 中的顶点（连接子图本身），并且不得包含 Y 中的顶点。

我们知道要在子图中包含另一个顶点，我们必须使用连接顶点，以便我们可以基于最终子图中的第一个连接顶点 v 的标识进行递归。禁止集意味着我们确保不能生成子图的第二个副本，因为该副本必须使用 v，但 v 在禁止集中，因此不能再次使用。

所以在这个表面的分析层面上，这个算法看起来是有效和正确的。

于 2013-09-16T21:33:46.017 回答
0

你没有很好地描述算法。我们不知道这个算法中的 k 是什么或 V 是什么。我只是假设 k 是子图上的限制长度，而 V 是某个根顶点。

如果这是真的，那么在我看来这个算法是不正确的。假设我们有一个图，只有两个连接的顶点 v1、v2 和子图 k = 1 上的限制。

在第一次迭代中：X, Y = empty, T(X) = {v1}, X1 = {V1}, Y1 = empty 我们显示 X1。

  • 然后我们递归调用 F(X1, Y1)，它应该立即返回，因为 |X| = |{v1}| = 1

现在回到第一次迭代 Y(1) = v1。循环结束，初始调用也到此结束。所以我们只打印出 X1。我们假设打印出 X1，X2。

顺便说一句，不要“测试”算法——没有办法测试它（可能的测试用例的数量是无限的）。你确实应该正式证明它。

于 2013-09-16T21:16:18.783 回答