私は有向ハミルトニアンサイクルを持っています:
[..., 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 を使用したくない理由
合計エッジ数と頂点数ではなく、削除されたエッジ数に線形のジェネレーターが必要です。