在Petersen子图中找到一个哈密尔顿路径 [英] Find an hamiltonian path inside the Petersen subgraph
问题描述
我开始使用IDE Jupyter&& Python 3.6出现了一个问题. 我必须通过彼得森子图中的哈密顿式路径IDE进行绘制，但是我不知道该怎么做.
I am starting to work with IDE Jupyter && Python 3.6 and a question has arisen. I have to draw through the IDE, a Hamiltonian path in the Petersen subgraph, but I do not know how to do it.
我显示了有关该图的信息:
I show information about said graph:
- 彼得森的图表: https://en.wikipedia.org/wiki/Petersen_graph
- 下汉密尔顿图: https://en.wikipedia.org/wiki/Hypohamiltonian_graph
- Graph of Petersen: https://en.wikipedia.org/wiki/Petersen_graph
- Hypohamiltonian graph: https://en.wikipedia.org/wiki/Hypohamiltonian_graph
关于如何发表评论的任何想法?
Any idea of how you can make the comments?
非常感谢您.
推荐答案
To compute the Hamiltonian graph in Petersen graph we can use the solution from this answer
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]}
我已经忘记了Petersen图是否对它们的任何顶点置换都是同构的，所以我假设它们不是同构的.因此，我们将搜索添加两个连接到原始图的每个顶点的新顶点，而不是搜索形成路径末端的成对顶点.因此，如果原始图形中存在哈密顿路径，则它将存在于此扩展图形中-只需切除两个额外的顶点(-1)和(-2).
I've forgotten whether or not Petersen graphs are isomorphic to any of their vertex permutations so I will assume they are not. Therefore, instead of searching for pairs of vertices which form the ends of the path we will add two new vertices connected to every vertex of the original graph. So if a Hamiltonian path exists in the original graph, it will exist in this extended graph -- just cut off the two extra vertices (-1) and (-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))
现在我们可以从帖子中应用算法了:
Now we can apply the algorithm from the post:
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]
...
由于此算法返回给定顶点之间的所有路径的列表，因此我们仅将其过滤为汉密尔顿路径，并切断多余的顶点.
Since this algorithm returns list of ALL paths between given vertices we will filter them only to Hamiltonian paths and cut off the extra vertices.
当然可以提高效率，但是我将优化留给您或其他人.在我看来，对于像Petersen这样的小图，它工作得足够快.
Surely, this can be more efficient, but I leave the optimizations to either you or someone else. For such a small graph as Petersen it works quickly enough in my opinion.
绘图
我们随机选择一个路径并将其存储在ham_path变量中.
We randomly choose one path and store it in ham_path variable.
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程序包绘制图形和选定的路径.
Then we will use the networkx package to draw the graph and the chosen path.
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图，汉密尔顿路径中的每个边将被染成红色和粗体.另一方面，每隔一条边将变薄和变黑.我们也不希望图形中有多余的顶点.
We create a networkx graph, and each edge that is in Hamiltonian path will be colored red and bold. On the other hand, every other edge will be thinner and black. We also do not want the extra vertices in our drawing.
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)
这篇关于在Petersen子图中找到一个哈密尔顿路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
