在 Python 中获得所有 Hybercubes 的完美匹配

Question

我正在研究超立方体。我目前在 python 中使用 networX。我读到 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 "contains functions to enumerate all perfect and maximum matchings in bipartited graph." 由于所有的完美匹配都是最大匹配，所以可以用这个得到所有的最大匹配，把不完美的丢掉。下面是在 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个完美匹配，所以使用这段代码找到它们可能会很慢。

在 Python 中获得所有 Hybercubes 的完美匹配

Get all perfect matchings of Hybercubes In Python

python-3.x

graph

networkx

hypercube