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 倍高速であると述べています。しかし、このアルゴリズムが正しいという証拠はまったく見つかりませんでした。

更新:より効率的な解決策が見つかりました here

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 は、サブグラフが X に頂点を含む必要があり (接続されたサブグラフ自体)、Y に頂点を含めてはならない、サイズ <=k のすべての接続されたサブグラフを生成します。

サブグラフに別の頂点を含めるには、接続された頂点を使用する必要があることがわかっているため、最終的なサブグラフ内にある最初の接続された頂点 v の ID に基づいて再帰できます。禁止セットは、サブグラフの 2 番目のコピーが v を使用する必要があるため生成できないことを保証することを意味しますが、v は禁止セットに含まれているため、再度使用することはできません。

したがって、この表面的な分析レベルでは、このアルゴリズムは効率的で正しいように見えます。

于 2013-09-16T21:33:46.017 に答える