python-3.x - 在 Python 中获取 Hybercubes 的所有完美匹配

Question

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

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

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

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

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

我是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)))

输出

Nodes in Q_4 : 16

Edges in Q_4 : 32

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

Answer 1

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

我不知道有什么库可以直接找到图形的所有完美匹配。然而，this github repository “包含在二分图中枚举所有完美和最大匹配的函数。”由于所有完美匹配都是最大匹配，您可以使用它来获取所有最大匹配并丢弃那些不完美的。下面是一些在 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 个完美匹配，因此使用此代码找到它们可能会很慢。