在Python中实现Hyber多维数据集的所有完美匹配

Question

我在研究超立方体。我目前在python中使用networX。我读到networkX是一个很好的图形库。我的问题是

1)构造了超立方体Q4和Q5的所有完美匹配。

2)那么，我要证明所有的完美匹配总是扩展到超立方体的哈密顿循环？

它已经证明了在超立方体中的所有完美匹配总是扩展到超立方体中的哈密顿循环。

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

我对蟒蛇很陌生。我写了一个构造超立方体的代码。

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构造所有完美匹配的代码。提前谢谢。

Answer 1

1)我要构造超立方体、Q4、和 Q5**.**的所有完美匹配。

我不知道有什么库可以直接找到一个图的所有完美匹配。然而，这个github存储库“包含一些函数来枚举双分叉图中的所有完美匹配和最大匹配。因为所有的完美匹配都是最大匹配，所以您可以使用它来获得所有的最大匹配，并丢弃那些不完美的匹配。下面是在python2.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个完美匹配，所以使用这段代码查找它们可能会很慢。