python - 在彼得森子图中找到一条哈密顿路径
问题描述
我开始使用 IDE Jupyter && Python 3.6 并且出现了一个问题。我必须通过 IDE 绘制彼得森子图中的哈密顿路径,但我不知道该怎么做。
我显示有关所述图表的信息:
- 彼得森图:https ://en.wikipedia.org/wiki/Petersen_graph
- 低汉密尔顿图:https ://en.wikipedia.org/wiki/Hypohamiltonian_graph
知道如何发表评论吗?
非常感谢。
解决方案
要计算彼得森图中的哈密顿图,我们可以使用这个答案的解决方案
petersen = {1: [2,5,6], 2: [3,1,7], 3: [4,2,8], 4: [5,3,9], 5: [1,4,10],
6: [1,8,9], 7:[2,9,10], 8: [3,10,6], 9: [4,6,7], 10: [5,7,8]}
我忘记了彼得森图是否与它们的任何顶点排列同构,所以我假设它们不是。因此,我们将添加两个连接到原始图的每个顶点的新顶点,而不是搜索形成路径末端的顶点对。因此,如果原始图中存在哈密顿路径,那么它将存在于这个扩展图中——只需将两个额外的顶点 (-1) 和 (-2) 剪掉即可。
# Add two new vertices (-1) and (-2)
for k in petersen:
petersen[k].append(-1)
petersen[k].append(-2)
petersen[-1] = list(range(1,11))
petersen[-2] = list(range(1,11))
现在我们可以应用帖子中的算法:
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not start in graph:
return []
paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
for path in find_all_paths(petersen, -1, -2):
if len(path) == len(petersen):
print(path[1:-1])
[1, 2, 3, 4, 5, 10, 7, 9, 6, 8]
[1, 2, 3, 4, 5, 10, 8, 6, 9, 7]
[1, 2, 3, 8, 6, 9, 4, 5, 10, 7]
[1, 2, 3, 8, 6, 9, 7, 10, 5, 4]
[1, 2, 7, 9, 6, 8, 3, 4, 5, 10]
[1, 2, 7, 9, 6, 8, 10, 5, 4, 3]
...
由于该算法返回给定顶点之间的所有路径列表,我们将仅将它们过滤到哈密顿路径并切断额外的顶点。
当然,这可能更有效,但我将优化留给您或其他人。对于像彼得森这样的小图,我认为它的运行速度足够快。
绘画
我们随机选择一条路径并将其存储在ham_path
变量中。
import random
ham_paths = [path[1:-1] for path in find_all_paths(petersen, -1, -2)
if len(path) == len(petersen)]
ham_path = random.choice(ham_paths)
然后我们将使用networkx
包来绘制图形和选择的路径。
import networkx
g = networkx.Graph()
for k, vs in petersen.items():
for v in vs:
if v in [-1, -2] or k in [-1, -2]:
continue
if abs(ham_path.index(k) - ham_path.index(v)) == 1:
g.add_edge(k,v, color='red', width=1.5)
else:
g.add_edge(k,v, color='black', width=0.5)
我们创建一个networkx
图,哈密顿路径中的每条边都将被涂成红色和粗体。另一方面,每隔一个边缘都会变薄和变黑。我们也不希望我们的绘图中有额外的顶点。
pos = networkx.circular_layout(g)
edges = g.edges()
colors = [g[u][v]['color'] for u,v in edges]
widths = [g[u][v]['width'] for u,v in edges]
networkx.draw(g, pos, edges=edges, edge_color=colors, width=widths)
推荐阅读
- php - 使用学说转置原始 SQL 查询
- python - 填充numpy数组时内存爆炸
- android - 例外:_InternalLinkedHashMap
' 不是类型转换中类型 'int' 的子类型 - powershell - CURL POST 返回令牌但 Invoke-RestMethod 不返回任何内容
- php - Laravel CSRF - 419 页面因向其他网站的发布请求而过期
- javascript - 如何使用 JS/JQuery 检测视频是否全屏?
- php - 为什么 $form->isValid() 总是返回 false?
- javascript - 使用 Javascript、Thymeleaf 使用 Bootstrap 使选项卡处于活动状态
- java - ZeroMQ 无法发布消息
- sql-order-by - 想要在第 3 位之后对列中的数据进行排序