Для вычисления гамильтонова графа в графе Петерсена мы можем использовать решение из этого ответа
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)
