4

我正在研究超立方体。我目前在 python 中使用networX。我读到 networkX 是一个非常好的处理图表的库。我的问题是

1）我想构造超立方体Q4和的所有完美匹配Q5。

2）然后我想验证所有完美匹配总是延伸到超立方体的哈密顿循环？

PS：它已经证明了超立方体中的所有完美匹配总是延伸到超立方体中的哈密顿循环。

我想通过计算机程序验证这两项任务。

我是 python 新手。我写了一个构建超立方体的代码。

import networkx as nx

graphSize = 4
hypercube = nx.hypercube_graph(graphSize)
print("Nodes in Q_" + str(graphSize) + " : " + str(nx.Graph.number_of_nodes(hypercube)))
print("Edges in Q_" + str(graphSize) + " : " + str(nx.Graph.number_of_edges(hypercube)))

输出

Q_4 中的节点：16

Q_4 中的边：32

这运行得很好。但我找不到任何库或函数networkX来获取所有完美匹配的列表。有人可以告诉我任何 python 库中是否有任何函数可用于在图形中获得所有完美匹配，或者有人有只为Q4和构建所有完美匹配的代码Q5。提前致谢。

4

1 回答 1

1

1）我想构造超立方体Q4和的所有完美匹配Q5。

我不知道有任何库可以直接找到图形的所有完美匹配。然而，这个 github 存储库“包含枚举二分图中所有完美匹配和最大匹配的函数。” 由于所有完美匹配都是最大匹配，因此您可以使用它来获取所有最大匹配并丢弃那些不完美的匹配。下面是在 python 2.7 中执行此操作的一些代码。

import networkx as nx

graph_size = 4
hypercube = nx.hypercube_graph(graph_size)

# Set the 'bipartite' attribute of the nodes, as required by bipartitematching.py
bottom_nodes, top_nodes = nx.bipartite.sets(hypercube)
bipartite_attributes = {node: 0 for node in bottom_nodes}
bipartite_attributes.update({node: 1 for node in top_nodes})
nx.set_node_attributes(hypercube, bipartite_attributes, "bipartite")

# Now find all of the maximum bipartite matchings
from bipartitematching import enumMaximumMatching
matchings = enumMaximumMatching(hypercube)

# Finally, find those maximum matchings that are perfect
perfect_matchings = []
for matching in matchings:
    if len(matching) == nx.number_of_nodes(hypercube)/2:
        perfect_matchings.append(matching)

# How many were there?
print(len(perfect_matchings))

我已经验证此代码为 4d 超立方体生成 272，但我没有足够的耐心让它为 5d 超立方体完成。根据OEIS，5d 超立方体应该有 589185 个完美匹配，因此使用此代码找到它们可能会很慢。

于 2019-07-30T01:17:37.763 回答