Как сгенерировать все возможные графы по переданным вершинам?

Question

Пусть есть 3 (хоть 10) вершины графа.

как сгенерировать все возможные соединения этих точек при таком условии, что точки должны быть соединены все?

То еть, не может быть такого, что какая-то вершина без соединения с кем-либо.

Answer 1

Вам нужны все комбинации пар вершин:

from itertools import combinations

# вершины
nodes = list('ABCDEFG')

# ребра
edges = list(combinations(nodes, 2))

результат:

In [96]: edges
Out[96]:
[('A', 'B'),
 ('A', 'C'),
 ('A', 'D'),
 ('A', 'E'),
 ('A', 'F'),
 ('A', 'G'),
 ('B', 'C'),
 ('B', 'D'),
 ('B', 'E'),
 ('B', 'F'),
 ('B', 'G'),
 ('C', 'D'),
 ('C', 'E'),
 ('C', 'F'),
 ('C', 'G'),
 ('D', 'E'),
 ('D', 'F'),
 ('D', 'G'),
 ('E', 'F'),
 ('E', 'G'),
 ('F', 'G')]

Можно использовать специально предназначенную для работы с графами библиотеку networkx:

import networkx as nx

G = nx.complete_graph(nodes)

результат:

nx.draw_networkx(G, pos=nx.circular_layout(G))

Answer 2

from itertools import permutations

nodes = list("abc")
print(*permutations(nodes), sep = "\n")

вывод:

('a', 'b', 'c')
('a', 'c', 'b')
('b', 'a', 'c')
('b', 'c', 'a')
('c', 'a', 'b')
('c', 'b', 'a')

БЛОГ НА HUSL

Как сгенерировать все возможные графы по переданным вершинам?

Ответы (2 шт):