3

私は有向ハミルトニアンサイクルを持っています:

[..., a, b, ... , c, d, ..., e, f, ...]

、b = next(a)、d = next(c)およびf = next(e)。

エッジ (a、b)、(c、d)、および (e、f) を削除するとします。

質問: グラフがハミルトニアン サイクルのままになるように、グラフの可能なすべての再結合を生成するにはどうすればよいですか (方向を修正するために、断片の 1 つの順序を逆にする必要がある場合があることに注意してください)。

私が知っていること

n エッジを削除することによって到達可能な新しいハミルトニアン サイクルの数は であることを知っていdouble-factorial(n-1)ます。また、2 つの連続するエッジを削除すると、重複したソリューションが得られることもわかっています (これで問題ありません...それらは、一意のサイクルに対して最小限である必要があり、結果のコードがクリーンに保たれます)。

私が試したこと（大まかな擬似コード）

これについて考える 1 つの方法は、生成されたハミルトニアン サイクルのいずれかが、新しい部分にジャンプする前に切断されたグラフの部分に沿って移動する必要があるというプロパティを保持する必要があるということです。

というわけで、例えば上記のサイクル（どこで）を考えるとn = 3、以下の3つになります。

[b, ..., c]
[d, ..., e]
[f, ..., a]

それでは、私の新しいソリューションが次のように始まるとしましょう。

[..., a, d, ...]

e は、終端頂点のリストから次に来る必要がある頂点であることを知っています。

したがって、その考えを使用すると、Python は次のようになります。

from itertools import permutations

def hamiltonian_cycles(l, s=None, r=None):
    if s is None:
        s = [l[0]]
    if r is None:
        r = l[1:]
    if not r:
        yield s
    else:
        for permutation in permutations(r):
            s1 = s[:] + [permutation[0]]
            for cycle in hamiltonian_cycles(l, s1, permutation[1:]):
                yield cycle
            s2 = s[:] + [(permutation[0][1], permutation[0][0])]
            for cycle in hamiltonian_cycles(l, s2, permutation[1:]):
                yield cycle

>>> l = [('f', 'a'), ('b', 'c'), ('d', 'e')]
>>> for cycle in hamiltonian_cycles(l):
...    print(cycle)
[('f', 'a'), ('b', 'c'), ('d', 'e')]
[('f', 'a'), ('b', 'c'), ('e', 'd')]
[('f', 'a'), ('c', 'b'), ('d', 'e')]
[('f', 'a'), ('c', 'b'), ('e', 'd')]
[('f', 'a'), ('d', 'e'), ('b', 'c')]
[('f', 'a'), ('d', 'e'), ('c', 'b')]
[('f', 'a'), ('e', 'd'), ('b', 'c')]
[('f', 'a'), ('e', 'd'), ('c', 'b')]

ただし、これは醜く見え、過去の動作を停止n=3します。したがって、質問です。

BFS/DFS を使用したくない理由

合計エッジ数と頂点数ではなく、削除されたエッジ数に線形のジェネレーターが必要です。

4

2 に答える 2

1

可能なすべてのハミルトニアン サイクルを生成します。試してみる

印刷やstuff.uなどのマトリックス操作を自分で納得できるように作成されたMatrixOperationsモジュールは、通常のprintステートメントで試すことができます 
from matrix import MatrixOperations
A=[[0,1,0,1,1,0,0],[1,0,1,0,0,0,0],[0,1,0,1,0,0,1],[1,0,1,0,1,0,1],[1,0,0,1,0,1,0],[0,0,0,0,1,0,1],[0,0,1,1,0,1,0]]
print("THE ADJACENCY MATRIX\n");MatrixOperations.PrintMatrix(A)
n=len(A)
X=[]
vis=[0 for i in range(n)]
def hamiltonian(vis,A,i):
    vis[i]=1
    if(len(X)==n-1 and A[i][0]==1):
        print (X)   
    for j in range(0,n):
        if (vis[j]==0 and A[i][j]==1):
            X.append(j)

            #print(X) this print shows the whole tracing process
            hamiltonian(vis,A,j)
            
    if(len(X)>0):
        del X[-1]
        vis[i]=0
print("\nPossible Hamiltonian cycles")
hamiltonian(vis,A,0)
于 2017-06-12T10:00:46.767 に答える